Изменения

'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется [[Формальные грамматики|грамматика]], у которой в левых частях всех правил стоят только одиночные нетерминалы.

Правила:#<tex>"S\rightarrow ("S)S</tex> и #<tex>"S\rightarrow S(S)"</tex> {{---}} терминальные символы; #<tex>S\rightarrow \varepsilon</tex>

Выведем слово <tex>S(()(()))()</tex> {{---}} стартовый нетерминал; :

Рассмотрим левосторонний вывод скобочной последовательности из примера:<br> 

'''Кронадерева разбора''' дерева разбора (англ. ''leaves of the parse tree'') {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.

<br>Построим дерево разбора скобочной последовательности из примера.<br> [[Файл:ParsingTreeBracketsSequenceParsingTree1.png|350px]]

|id=t01|about=5.14t1|statement=Пусть <tex>G \Gamma = (V\langle \Sigma, N, TS, P, S)\rangle</tex> — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным <tex>A</tex>, и кроной <tex>w\omega</tex>, где <tex>w \omega \in TN^{*}</tex>. Тогда в грамматике <tex>G\Gamma</tex> существует левое порождение <tex>A \Rightarrow^{*}_{lm} w\omega</tex>

'''Базис.База:''' Базисом является высота <tex>1</tex>, наименьшая из возможных для дерева разбора с терминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным <tex>A</tex>, и сыновьями, образующими цепочку <tex>w</tex>. :Поскольку это дерево является деревом разбора, <tex>A \rightarrow w\omega</tex> должно быть продукцией. Таким образом, <tex>A \Rightarrow_{lm} w\omega</tex> есть одношаговое левое порождение <tex>w\omega</tex> из <tex>A</tex>.

'''Индукция.Индукционный переход:''' Если высота дерева равна <tex>n</tex>, где <tex>n > 1</tex>, то оно должно иметь вид, как на рис. 5.9. Таким образом, существует Существует корень с отметкой <tex>A</tex> и сыновьями, отмеченными слева направо <tex>X_1X_2...\ldots X_k</tex>. Символы <tex>X</tex> могут быть как терминалами, так и переменными.# Если <tex>X_i</tex> — терминал, то определим <tex>w_i\omega_i</tex> как цепочку, состоящую из одного <tex>X_i</tex>.# Если <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим <tex>w_i\omega_i</tex>. Заметим, что в этом случае высота поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, существует левое порождение <tex>X_i \Rightarrow^{*}_{lm} wi\omega_i</tex>.

Заметим, что <tex>w \omega = w_1w_2...w_k\omega_1\omega_2 \ldots \omega_k</tex>.Построим левое порождение цепочки <tex>w\omega</tex> следующим образом. ::Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2...\ldots X_k</tex>. :Затем для <tex>i = 1, 2, ...\ldots, k\ </tex> покажем, что имеет место следующее порождение.: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>

Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>.Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow^{*}_Rightarrow_{lm} w_1w_2...w_iX_{i+1}X_{i+2}...X_1X_2\ldots X_k</tex>.

Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>. Для базиса <tex>i = 0</tex> мы уже знаеминдукции предположим, что существует следующее порождение: <tex>A \Rightarrow_Rightarrow^{*}_{lm} X_1X_2...\omega_1\omega_2\ldots\omega_{i–1}X_iX_{i+1}\ldots X_k</tex>. Для индукции предположим, что существует следующее порождение.

# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>\omega_i</tex>. Таким образом, приходим к существованию следующего порождения. <tex>A \Rightarrow^{*}_{lm} w_1w_2...w_\omega_1\omega_2\ldots\omega_iX_{i–1i+1}X_iX_X_{i+12}\ldots X_k</tex># Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>\omega_i</tex> из <tex>X_i</tex> в контексте уже построенного порождения...X_kТаким образом, если этим порождением является: <tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2\ldots \Rightarrow_{lm} \omega_i</tex>, то продолжаем следующими порождениями:

# Если ::<tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>w_i</tex>. Таким образом, приходим к существованию следующего порождения.<br><tex>A \Rightarrow^omega_1\omega_2\ldots\omega_{*i–1}_{lm} w_1w_2...w_iX_X_iX_{i+1}X_\ldots X_k \Rightarrow_{i+2lm}...X_k</tex><br># Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>w_i</tex> из <tex>X_i</tex> в контексте ужепостроенного порождения. Таким образом, если этим порождением является

::<tex>X_i \Rightarrow_omega_1\omega_2\ldots\omega_{lmi–1} \alpha_1 \Rightarrow_alpha_1X_{lmi+1} \alpha_2... ldots X_k \Rightarrow_{lm} w_i</tex>,

::<tex>w_1w_2...w_{i–1}X_iX_{i+1}...X_k \Rightarrow_{lm}ldots</tex>

::<tex>w_1w_2...w_{i–1}\alpha_1X_omega_1\omega_2\ldots\omega_iX_{i+1}...X_k \Rightarrow_X_{lmi+2}\ldots X_k</tex>

Результатом является порождение <tex>w_1w_2...w_A \Rightarrow^{*}_{i–1lm}\alpha_2X_omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>...X_k Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>\Rightarrow_{lm}omega</tex> из <tex>A</tex>.}}

{{Теорема|id=t2|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>\Longrightarrow</tex>

<tex>w_1w_2:Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве [[#t1|теоремы]].В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными..w_iX_{i+1}X_{i+2}...X_k</tex>

Результатом является порождение <tex>A \Rightarrow^{*}_{lm} w_1w_2...w_iX_{i+1}X_{i+2}...X_kLongleftarrow </tex>.

Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>w</tex> из <tex>A</tex>.}} {{Теорема|id=t0|about=5.29|statement=Для каждой грамматики <tex>G = (V, T, P, S)</tex> и <tex>w</tex> из <tex>T^{*}</tex> цепочка <tex>w</tex> имеет два разных дерева разбора тогда и только тогда, когда <tex>w</tex> имеет два разных левых порождения из <tex>S</tex>.|proof=(Необходимость) Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве теоремы (5.14). В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными.(Достаточность) :Хотя мы предварительно не описали непосредственное построение дерева разбора по левому порождению, идея его проста. Начнем построение дерева с корня, отмеченного стартовым символом. Рассмотрим порождение пошагово. На каждом шаге заменяется переменная, и эта переменная будет соответствовать построенному крайнему слева узлу дерева, не имеющему сыновей, но отмеченному этой переменной. По продукции, использованной на этом шаге левого порождения, определим, какие сыновья должны быть у этого узла. Если существуют два разных порождения, то на первом шаге, где они различаются, построенные узлы получат разные списки сыновей, что гарантирует различие деревьев разбора.

|statement = Грамматика из примера не является однозначной.|proof =Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.

[[Файл:Parsetree2BracketsSequenceParsingTree2.png|300px]]

|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.|proof =Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;  <tex>S</tex> {{---}} стартовый нетерминал;  Правила:<br>1) #<tex>S\rightarrow (S)S</tex><br>2) #<tex>S\rightarrow \varepsilon</tex><br>

'''ПереходИндукционный переход:''' Пусть <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|Существенно неоднозначные языки}}