Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
Версия от 15:05, 24 ноября 2014; Maryann (обсуждение | вклад)
Определение: |
Контекстно-свободной грамматикой (англ. сontext-free grammar) называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. |
Определение: |
Контекстно-свободный язык (англ. context-free language) — язык, задаваемый контекстно-свободной грамматикой. |
Определение: |
Выводом слова | называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово .
Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности.
Терминальные символы —
и ;— стартовый нетерминал;
Правила:
Выведем слово :
Определение: |
Левосторонним выводом слова | называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
Определение: |
Правосторонним выводом слова | называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
Рассмотрим левосторонний вывод нашей скобочной последовательности:
Определение: |
Деревом разбора грамматики (англ. parse tree) называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. |
Определение: |
Крона дерева разбора — множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. |
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
Рассмотрим, как будет выглядеть дерево разбора нашей скобочной последовательности.
Определение: |
Грамматика называется однозначной (англ. unambiguous grammar), если у каждого слова имеется не более одного дерева разбора в этой грамматике. |
Лемма: |
Пусть — однозначная грамматика. Тогда существует ровно один левосторонний (правосторонний) вывод . |
Доказательство: |
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова. |
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.