59
правок
Изменения
Нет описания правки
Рассмотрим грамматику, выводящую все правильные скобочные последовательности.
:<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы
:<tex>S</tex> {{---}} стартовый нетерминал
Правила::#<tex>"S\rightarrow ("S)S</tex> и :#<tex>"S\rightarrow S(S)"</tex> {{---}} терминальные символы; :#<tex>S\rightarrow \varepsilon</tex>
Выведем слово <tex>S"(()(()))()"</tex> {{---}} стартовый нетерминал; :
<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>
'''Правосторонним выводом слова''' (англ. ''rightmost derivation'') <tex>\alpha</tex> называется такой вывод слова <tex>\alpha</tex>, в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера:<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>
'''Крона дерева разбора''' (англ. ''leaves of the parse tree'') {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
[[Файл:ParsingTree.png|350px]]
Для индукции предположим, что существует следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dots\omega_{i–1}X_iX_{i+1}\dots X_k</tex>
# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>\omega_i</tex>. Таким образом, приходим к существованию следующего порождения.<br><tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dots\omega_iX_{i+1}X_{i+2}\dots X_k</tex><br>
# Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>\omega_i</tex> из <tex>X_i</tex> в контексте уже построенного порождения. Таким образом, если этим порождением является: <tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2\dots \Rightarrow_{lm} \omega_i</tex>, то продолжаем следующими порождениями:
