Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора — различия между версиями
Строка 19: | Строка 19: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Левосторонним выводом слова <tex>\alpha</tex>''' называется его вывод | + | '''Левосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил. |
}} | }} | ||
Аналогичным образом определяется ''правосторонний вывод''. | Аналогичным образом определяется ''правосторонний вывод''. | ||
Строка 45: | Строка 45: | ||
Пусть <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:29, 23 января 2012
Определение: |
Контекстно-свободной грамматикой называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. Язык, задаваемый контекстно-свободной грамматикой называется контекстно-свободным языком. |
Определение: |
Выводом слова | называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и последней строкой в последовательности является слово .
Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности. Терминальные символы "(" и ")", нетерминал , он же стартовый нетерминал, правила:
Выведем слово "(()(()))()":
Определение: |
Левосторонним выводом слова | называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил.
Аналогичным образом определяется правосторонний вывод.
Рассмотрим левосторонний вывод нашей скобочной последовательности:
Определение: |
Деревом разбора грамматики называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. |
Определение: |
Кроной дерева разбора называется множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. |
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
Рассмотрим, как будет выглядеть дерево разбора няшной скобочной последовательности.
Определение: |
Грамматика называется однозначной, если у каждого слова имеется не более одного дерева разбора в этой грамматкие. |
Утверждение: |
Пусть - однозначная грамматика. Тогда у существует ровно один левосторонний (правосторонний) вывод. |
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова. |
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.