299
правок
Изменения
→Дерево разбора
{{Теорема
|id=t01|about=5.14t1|statement=Пусть <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным <tex>A</tex>, и кроной <tex>w\omega</tex>, где <tex>w \omega \in N^{*}</tex>. Тогда в грамматике <tex>\Gamma</tex> существует левое порождение <tex>A \Rightarrow^{*}_{lm} w\omega</tex>
|proof=
Используем индукцию по высоте дерева.
'''Базис.''' Базисом является высота <tex>1</tex>, наименьшая из возможных для дерева разбора с терминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным <tex>A</tex>, и сыновьями, образующими цепочку <tex>w\omega</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...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\omega_1\omega_2...w_k\omega_k</tex>.Построим левое порождение цепочки <tex>w\omega</tex> следующим образом. Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2...X_k</tex>. Затем для <tex>i = 1, 2, ..., k</tex> покажем, что имеет место следующее порождение.
<tex>A \Rightarrow^{*}_{lm} w_1w_2\omega_1\omega_2...w_iX_\omega_iX_{i+1}X_{i+2}...X_k</tex>
Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>. Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2...X_k</tex>. Для индукции предположим, что существует следующее порождение.
<tex>A \Rightarrow^{*}_{lm} w_1w_2\omega_1\omega_2...w_\omega_{i–1}X_iX_{i+1}...X_k</tex>
# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>w_i\omega_i</tex>. Таким образом, приходим к существованию следующего порождения.<br><tex>A \Rightarrow^{*}_{lm} w_1w_2\omega_1\omega_2...w_iX_\omega_iX_{i+1}X_{i+2}...X_k</tex><br># Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>w_i\omega_i</tex> из <tex>X_i</tex> в контексте уже
построенного порождения. Таким образом, если этим порождением является
<tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2... \Rightarrow_{lm} w_i\omega_i</tex>,
то продолжаем следующими порождениями.
<tex>w_1w_2\omega_1\omega_2...w_\omega_{i–1}X_iX_{i+1}...X_k \Rightarrow_{lm}</tex>
<tex>w_1w_2\omega_1\omega_2...w_\omega_{i–1}\alpha_1X_{i+1}...X_k \Rightarrow_{lm}</tex>
<tex>w_1w_2\omega_1\omega_2...w_\omega_{i–1}\alpha_2X_{i+1}...X_k \Rightarrow_{lm}</tex>
<tex>...</tex>
<tex>w_1w_2\omega_1\omega_2...w_iX_\omega_iX_{i+1}X_{i+2}...X_k</tex>
Результатом является порождение <tex>A \Rightarrow^{*}_{lm} w_1w_2\omega_1\omega_2...w_iX_\omega_iX_{i+1}X_{i+2}...X_k</tex>.
Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>w\omega</tex> из <tex>A</tex>.
}}
|id=t0
|about=5.29
|statement=Для каждой грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> и <tex>w\omega</tex> из <tex>N^{*}</tex> цепочка <tex>w\omega</tex> имеет два разных дерева разбора тогда и только тогда, когда <tex>w\omega</tex> имеет два разных левых порождения из <tex>P</tex>.
|proof=
(Необходимость) Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве теоремы (5.14). В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными.
