Разработка компиляторов

       

Луч


Лучом называется фрагмент, который, во-первых, является альтом, а во-вторых, обладает тем свойством, что произвольная его вершина, отличная от начальной и выходной, имеет одного предка и одного потомка, каждый из которых принадлежит лучу. Иными словами, луч - это линейная последовательность вершин.

Легко видеть, что в состав лучей могут входить только деревянные дуги.

Нумерация # называется правильной, если она приписывает вершинам произвольного луча последовательные номера.

Если # - правильная нумерация, а R - максимальный луч, то можно доказать следующие утверждения:

  • вершина p является начальной вершиной R тогда и только тогда, когда либо p=start либо #-1(#(p)-1) - выходная вершина некоторого максимального луча
  • вершина q является выходной вершиной R тогда и только тогда, когда либо p=stop либо #-1(#(p)+1) - начальная вершина некоторого максимального луча

Легко показать, что нумерации Pre и Post являются правильными.



Содержание раздела