Алгоритм получения скобочной записи синтаксического дерева вывода

Линейная скобочная запись является терминальной цепочкой, вывод которой представлен соответствующим деревом, с выделенными в ней синтаксическими конструкциями. Для обозначения начала и конца каждой конструкции используются скобки. После левой и перед правой скобкой, которые ограничивают какую-либо выделяемую подцепочку, записывается породивший ее в данном выводе нетерминальный символ. Построение цепочки происходит путем приписывания справа символов к уже построенной части цепочки.

Будем считать, что в начальный момент времени обозревается корень дерева, помеченных дуг нет, а построенная часть цепочки пуста. При этих предположениях процесс построения цепочки описывается следующим алгоритмом:

1. Если обозреваемая вершина имеет выходящие из нее дуги, то переходим к шагу 2, иначе – к шагу 5.

2. Приписываем цепочке левую скобку и символ, соответствующий обозреваемой вершине. Переходим к шагу 3.

3. Если среди дуг, выходящих из обозреваемой вершины есть непомеченные, помечаем левую из них, т.е. ведущую в наименьшую вершину и переходим к шагу 1. В противном случае – к шагу 4.

4. Приписываем к цепочке символ, соответствующий обозреваемой вершине и правую скобку. Если в данную вершину входит дуга, обозреваем вершину из которой она выходит и переходим к шагу 3. Если входящей дуги нет – это корень.

5. приписываем цепочке соответствующий терминальный сим­вол, обозреваем предыдущую вершину, переходим к шагу 3.

Пример 11: Линейная скобочная запись дерева вывода, приведенная в примере 9 выглядит следующим образом:

(Ч+(Н(Д(Б(Б(Ц2Ц)Б) (Ц5Ц)Б) (М.(Б(Ц6Ц)Б)М)Д) (Пe (Ф-(Б(Ц2Ц)Б)Ф)П)Н)Ч).

F Определение: 1) Вывод в КС-грамматике будем называть левосторонним (правосторонним), если правило вывода применяется к самому левому (правому) вхождению нетерминальной цепочки вывода.

2) КС-грамматику, в которой существует более чем один левосторонний вывод некоторой терминальной цепочки, будем называть неоднозначной, а язык, порождаемый такой грамматикой, – синтаксически неоднозначным.

3) Язык, все порождающие КС-грамматики которого неоднозначны, будем называть существенно синтаксически неоднозначным.

При помощи КС-грамматик можно представить не все, а лишь часть синтаксических правил языков программирования. Те же правила, которые средствами КС-грамматик не описываются, называются контекстными условиями и задаются обычно неформально – при помощи английского, русского и других естественных языков.