137
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
Терминальные символы {{---}} <tex>"("</tex> и <tex>")"</tex>;
{{Определение
|definition=
'''Левосторонним выводом Левосторонний вывод слова ''' (англ. ''leftmost derivation'')<tex>\alpha</tex>''' называется такой его {{---}} вывод, что где каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
}}
{{Определение
|definition=
'''Правосторонним выводом слова ''' (англ. '' rightmost derivation'') <tex>\alpha</tex>''' называется такой его {{---}} вывод, что где каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
<br>
Рассмотрим левосторонний вывод нашей скобочной последовательностииз примера:<br>
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>
{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, а дети являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, (в левой части которого стоит этот нетерминал, ) и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей.
}}
{{Определение
|definition=
'''Крона''' дерева разбора {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
{{Определение
|definition=
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод <tex>\omega</tex>.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний (правосторонний) вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний (правосторонний) вывод этого слова.
}}
==См. также==
* [[Формальные грамматики]]
* [[Иерархия Хомского формальных грамматик]]
* [[Замкнутость КС-языков относительно различных операций]]
== Литература ==
* Джон [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]* ''ХопкрофтД., Раджив МотваниР., Джеффри УльманД. '' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
