63
правки
Изменения
м
Нет описания правки
'''Выводом слова''' <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности. Терминальные символы "(" и ")", нетерминал <tex>S</tex>, он же стартовый нетерминал, правила:<br>
<tex>S\rightarrow (S)S</tex><br>
<tex>S\rightarrow S(S)</tex><br>
<tex>S\rightarrow \varepsilon</tex><br>
Выведем слово "(()(()))()":<br>
<tex>\boldsymbol{S}\rightarrow (S)\boldsymbol{S} \rightarrow (S)(\boldsymbol{S})S\rightarrow(S)()\boldsymbol{S}\rightarrow(\boldsymbol{S})()\rightarrow(\boldsymbol{S}(S))()\rightarrow(S(S)(\boldsymbol{S}))()\rightarrow(S(S)(\boldsymbol{S}(S)))()\rightarrow (S(\boldsymbol{S})((S)))()\rightarrow(\boldsymbol{S}()((S)))()\rightarrow(()((\boldsymbol{S})))()\rightarrow(()(()))()</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=
'''Кроной''' дерева разбора называется множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева из в глубину корня.
}}
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.<br>Рассмотрим, как будет выглядеть дерево разбора нашей скобочной последовательности.<br>[[Файл:[[Файл:Example.jpg]]]]
{{Определение
|definition=
