Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора — различия между версиями
Строка 41: | Строка 41: | ||
Грамматика называется однозначной, если у каждого слова имеется не более одного дерева разбора в этой грамматкие. | Грамматика называется однозначной, если у каждого слова имеется не более одного дерева разбора в этой грамматкие. | ||
}} | }} | ||
− | {{ | + | {{Лемма |
+ | |id=lemma- | ||
|statement= | |statement= | ||
− | Пусть <tex>\Gamma</tex> - однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> у <tex>\omega</tex> существует ровно один левосторонний (правосторонний) вывод. | + | Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> у <tex>\omega</tex> существует ровно один левосторонний (правосторонний) вывод. |
|proof= | |proof= | ||
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова. | Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова. |
Версия 01:35, 23 января 2012
Определение: |
Контекстно-свободной грамматикой называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. Язык, задаваемый контекстно-свободной грамматикой называется контекстно-свободным языком. |
Определение: |
Выводом слова | называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и последней строкой в последовательности является слово .
Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности. Терминальные символы "(" и ")", нетерминал , он же стартовый нетерминал, правила:
Выведем слово "(()(()))()":
Определение: |
Левосторонним выводом слова | называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил.
Аналогичным образом определяется правосторонний вывод.
Рассмотрим левосторонний вывод нашей скобочной последовательности:
Определение: |
Деревом разбора грамматики называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. |
Определение: |
Кроной дерева разбора называется множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. |
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
Рассмотрим, как будет выглядеть дерево разбора няшной скобочной последовательности.
Определение: |
Грамматика называется однозначной, если у каждого слова имеется не более одного дерева разбора в этой грамматкие. |
Лемма: |
Пусть — однозначная грамматика. Тогда у существует ровно один левосторонний (правосторонний) вывод. |
Доказательство: |
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова. |
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.