Разработка компиляторов
Луч
Лучом называется фрагмент, который, во-первых, является альтом, а во-вторых, обладает тем свойством, что произвольная его вершина, отличная от начальной и выходной, имеет одного предка и одного потомка, каждый из которых принадлежит лучу. Иными словами, луч - это линейная последовательность вершин.
Легко видеть, что в состав лучей могут входить только деревянные дуги.
Нумерация # называется правильной, если она приписывает вершинам произвольного луча последовательные номера.
Если # - правильная нумерация, а R - максимальный луч, то можно доказать следующие утверждения:
- вершина p является начальной вершиной R тогда и только тогда, когда либо p=start либо #-1(#(p)-1) - выходная вершина некоторого максимального луча
- вершина q является выходной вершиной R тогда и только тогда, когда либо p=stop либо #-1(#(p)+1) - начальная вершина некоторого максимального луча
Легко показать, что нумерации Pre и Post являются правильными.
