Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора — различия между версиями
Строка 28: | Строка 28: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Деревом разбора''' называется дерево, | + | '''Деревом разбора грамматики''' называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. |
}} | }} | ||
{{Определение | {{Определение |
Версия 01:25, 23 января 2012
Определение: |
Контекстно-свободной грамматикой называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. Язык, задаваемый контекстно-свободной грамматикой называется контекстно-свободным языком. |
Определение: |
Выводом слова | называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и последней строкой в последовательности является слово .
Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности. Терминальные символы "(" и ")", нетерминал , он же стартовый нетерминал, правила:
Выведем слово "(()(()))()":
Определение: |
Левосторонним выводом слова | называется его вывод такой, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил.
Аналогичным образом определяется правосторонний вывод.
Рассмотрим левосторонний вывод нашей скобочной последовательности:
Определение: |
Деревом разбора грамматики называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. |
Определение: |
Кроной дерева разбора называется множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. |
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
Рассмотрим, как будет выглядеть дерево разбора няшной скобочной последовательности.
Определение: |
Грамматика называется однозначной, если у каждого слова имеется не более одного дерева разбора в этой грамматкие. |
Утверждение: |
Пусть - однозначная грамматика. Тогда у существует ровно один левосторонний (правосторонний) вывод. |
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то и левосторонний вывод, выводящий это слово, существует только один |
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.