390
правок
Изменения
м
Правила:<br>
<tex>S\rightarrow (S)S</tex><br>
<tex>S\rightarrow S(S)</tex><br>
<tex>S\rightarrow \varepsilon</tex><br>
Выведем слово <tex>"(()(()))()"</tex>:<br>
<br>Построим дерево разбора скобочной последовательности из примера.<br> [[Файл:ParsingTreeBracketsSequenceParsingTree1.png|350px]]
то продолжаем следующими порождениями. Для индукции предположим, что существует следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_{i–1}X_iX_{i+1}\ldots X_k</tex>
Результатом является порождение ::<tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dotsldots\omega_iX_{i+1}X_{i+2}\dots ldots X_k</tex>.
<br>
<br>
<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы; <tex>S</tex> {{---}} стартовый нетерминал; Правила:<br>1) #<tex>S\rightarrow (S)S</tex><br>2) #<tex>S\rightarrow \varepsilon</tex><br>
Исправил многоточия ещё
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется [[Формальные грамматики|грамматика]], у которой в левых частях всех правил стоят только одиночные нетерминалы.
}}
{{Определение
|id=lang
|definition=
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
Рассмотрим грамматику, выводящую все правильные скобочные последовательности.
:<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>
{{Определение
|definition=
'''Кронадерева разбора''' дерева разбора (англ. ''leaves of the parse tree'') {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
{{Теорема
Используем индукцию по высоте дерева.
'''Базис.База:''' Базисом является высота <tex>1</tex>, наименьшая из возможных для дерева разбора с терминальной кроной. :Поскольку это дерево является деревом разбора, <tex>A \rightarrow \omega</tex> должно быть продукцией. Таким образом, <tex>A \Rightarrow_{lm} \omega</tex> есть одношаговое левое порождение <tex>\omega</tex> из <tex>A</tex>.
'''Индукция.Индукционный переход:''' Существует корень с отметкой <tex>A</tex> и сыновьями, отмеченными слева направо <tex>X_1X_2 \dots ldots X_k</tex>. Символы <tex>X</tex> могут быть как терминалами, так и переменными.
# Если <tex>X_i</tex> — терминал, то определим <tex>\omega_i</tex> как цепочку, состоящую из одного <tex>X_i</tex>.
# Если <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим <tex>\omega_i</tex>. Заметим, что в этом случае высота поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, существует левое порождение <tex>X_i \Rightarrow^{*}_{lm} \omega_i</tex>.
Заметим, что <tex>\omega = \omega_1\omega_2 \dots ldots \omega_k</tex>.Построим левое порождение цепочки <tex>\omega</tex> следующим образом. ::Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2\dots ldots X_k</tex>. :Затем для <tex>i = 1, 2, \dotsldots, k\ </tex> покажем, что имеет место следующее порождение. : <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dotsldots\omega_iX_{i+1}X_{i+2}\dots X_k</tex> Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>. Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2\dots X_k</tex>. Для индукции предположим, что существует следующее порождение. <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dots\omega_{i–1}X_iX_{i+1}\dots ldots 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>i</tex>.Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>X_i \Rightarrow_{lm} \alpha_1 A \Rightarrow_{lm} X_1X_2\alpha_2\dots \Rightarrow_{lm} \omega_ildots X_k</tex>,.
# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>\omega_i</tex>. Таким образом, приходим к существованию следующего порождения. <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dotsldots\omega_omega_iX_{i–1i+1}X_iX_X_{i+12}\dots ldots X_k </tex># Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>\omega_i</tex> из <tex>X_i</tex> в контексте уже построенного порождения. Таким образом, если этим порождением является: <tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm}\alpha_2\ldots \Rightarrow_{lm} \omega_i</tex>, то продолжаем следующими порождениями:
::<tex>\omega_1\omega_2\dotsldots\omega_{i–1}\alpha_1X_X_iX_{i+1}\dots ldots X_k \Rightarrow_{lm}</tex>
::<tex>\omega_1\omega_2\dotsldots\omega_{i–1}\alpha_2X_alpha_1X_{i+1}\dots ldots X_k \Rightarrow_{lm}</tex>
::<tex>\dotsomega_1\omega_2\ldots\omega_{i–1}\alpha_2X_{i+1}\ldots X_k \Rightarrow_{lm}</tex>
::<tex>\omega_1\omega_2\dots\omega_iX_{i+1}X_{i+2}\dots X_kldots</tex>
Результатом является порождение <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>.
Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>\omega</tex> из <tex>A</tex>.
}}
|statement=Для каждой грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> и <tex>\omega</tex> из <tex>N^{*}</tex> цепочка <tex>\omega</tex> имеет два разных дерева разбора тогда и только тогда, когда <tex>\omega</tex> имеет два разных левых порождения из <tex>P</tex>.
|proof=
<tex>\RightarrowLongrightarrow</tex>
:Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве [[#t1|теоремы]]. В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными.
<tex>\LeftarrowLongleftarrow </tex>
:Хотя мы предварительно не описали непосредственное построение дерева разбора по левому порождению, идея его проста. Начнем построение дерева с корня, отмеченного стартовым символом. Рассмотрим порождение пошагово. На каждом шаге заменяется переменная, и эта переменная будет соответствовать построенному крайнему слева узлу дерева, не имеющему сыновей, но отмеченному этой переменной. По продукции, использованной на этом шаге левого порождения, определим, какие сыновья должны быть у этого узла. Если существуют два разных порождения, то на первом шаге, где они различаются, построенные узлы получат разные списки сыновей, что гарантирует различие деревьев разбора.
}}
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
{{Утверждение
|statement = Грамматика из примера не является однозначной.|proof =Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.
Например, оно будет выглядеть так:
[[Файл:Parsetree2BracketsSequenceParsingTree2.png|300px]]
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
{{Утверждение
|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.|proof =Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).
Рассмотрим грамматику:
:<tex>(</tex> и <tex>)</tex> {{---}} терминальные символы
:<tex>S</tex> {{---}} стартовый нетерминал
Покажем, что эта грамматика однозначна.
Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.
'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</tex> для него существует единственное дерево разбора.
'''ПереходИндукционный переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex>: <tex>\left\vert \upsilon \right\vert < n</tex> и <tex>\upsilon</tex> {{---}} правильная скобочная последовательность , у которой <tex>\exists!</tex> дерево разбора.
:Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0</tex> такой, что слово <tex>\omega[0..\ldots i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..\ldots i]=(\alpha)\ </tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и <tex>\beta=\omega[i+1..\ldots n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \beta \right\vert<n \Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора.
:Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и для каждого из них по предположению существуют единственные деревья разбора).
:Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..\ldots j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.
:Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..\ldots j]\ </tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0..\ldots i]=(\alpha)\ </tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.
:Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..\ldots i] \Rightarrow \omega\ </tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.
Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.
}}
Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|'''существенно неоднозначными'']]'.{{main|Существенно неоднозначные языки}}
==См. также==
