Дерево разбора

Выводимые строки

Строки, порождаемые из начального символа грамматики, называются выводимыми строками.

Примечание.

1. Выводимые строки, левовыводимые строки, правовыводимые строки.

2. Язык образуют выводимые терминальные строки.

Дерево разбора – это один из способов представления порождения строки. Дерево разбора наглядно показывает, каким образом символы строки группируются в подстроки, каждая из которых принадлежит языку одной переменных грамматики.

Пусть - КС-грамматика.

Деревья разбора грамматики это деревья со следующими свойствами:

Каждый внутренний узел отмечен переменной из множества ;

Каждый лист отмечен либо переменной, либо терминалом, либо . При этом, если лист отмечен , он должен быть единственным сыном своего родителя;

Если внутренний узел отмечен , и его сыновья отмечены слева направо соответственно, то является правилом. Отметим, что может быть лишь в одном случае – если он отмечает единственного сына, и правило грамматики .

Пример. …