Определение

Контекстносвободная грамматика называется разделенной, если:

1. правая часть любого правила вывода начинается терминалом.
2. все альтернативны любого нетерминала начинаются разными терминалами

Замечание

МП-автомат задается не семеркой объектов, а четверкой: основной и вспомогательный алфавиты, множество команд и начальное содержимое стека. Обозначение МП-автомата как четверки объектов будет указывать на автомат именно такого типа.

пометка: если хотите посмотреть алгоритм построения, то его можно посмотреть на 109 странице в книге Замятин, Шур.

Определение

Контекстносвободная грамматика $G$ называется $LL(1)$-грамматикой, если множество для альтернатив не пересекается; $Select(A\to \alpha_1) \cap Select(A\to \alpha_2) = \varnothing$ $\forall A \to \alpha_1,\alpha_2$

Алгоритм построения нисходящего анализатора по LL(1)-грамматике

$G=(\Sigma, Г, P, S)$ $- LL(1)$ грамматика $M = \{\Sigma \cup \{\dashv\}, \widehat{Г}, \delta, S\}$

1. $\delta(A,a) = (\gamma, -); \ \ \forall A \in Г \ \ \forall a\in \Sigma \cup \{\dashv\}$ $a \in Select(A\to \gamma)$
2. $\delta(a,a)=(\varepsilon, \to); \ \ \forall a \in \Sigma$
3. $\delta(\nabla, \dashv) = V$

Теорема

<aside> 📌 $L(M) = L(G)$

</aside>

Доказательство:

$w \in L(M) \Leftrightarrow [S, w] \vDash^*[\varepsilon, \dashv]$

Пусть МП-автомат распознаёт $w$ за $k$ шагов

$\beta_i -$ содержимое стека на $i$ шаге

$w_i -$ обработанная часть цепочки

$(w_0 \beta_0, w_1 \beta_1, … , w_k \beta_k)$

Докажем, что по индукции по $k$, что это левосторонний вывод $w$

Б.И. $i = 0$ $w_0 = \varepsilon$ $\beta_0 = S$

Ш.И. П.И. $S \rArr^* w_i\beta_j$

  **Случай 1**

Пусть мы применили на $(i+1)$ шаге правило: $\delta(A, a)=(\gamma, -)$

$w_{i+1} = w_i$ $\beta_{i+1}=\gamma \beta'_i$ $A \to \gamma \in P$

$w_i\beta_i = A \beta_i'$ $\rArr w_{i+1} \gamma \beta_i'$ $= w_{i+1}\beta_{i+1}$

$S \rArr^* w_k\beta_k = w$; $w \in L(G)$

Случай 2

Пусть мы применили на $(i+1)$ шаге правило: $\delta(a,a) = (\varepsilon, \to)$

$w_{i+1} = w_ia$ $a\beta_{i+1} = \beta_i$

$w_{i+1}\beta_{i+1} = w_i\beta_i$

Доказательство (в обратную сторону):

$w \in L(G)$ $S = \alpha_0 \rArr \alpha_1 \rArr … \rArr \alpha_k = w$ $(*)$

Докажем, что $\exist$ $\alpha_i = w_i\beta_i$, где $w$ - обработанная часть цепочки, $\beta$ - содержимое стека $\alpha_k = w_k \beta_k$

Доказательсвто:

Б.И. $\alpha_0 = \varepsilon * S$

Ш.И.

П.И. $\exists$ $\alpha_i = w_i\beta_i$ $= w_ia_1…a_pA\beta_i'$

Знаем, что $[S, w] \vDash^$ $[a_1…a_pA\beta_i',a_1…a_pCU]$ $\vDash^{ (2)}$ $[A\beta_i',CU] \vDash^{} [\gamma\beta_i, CU]$, где В $()$ существует команда $\delta(A,C) = (\gamma, -)$ $\alpha_{i+1} = w_ia_1…a_p * \gamma\beta_i' = w_{i+1} * \beta_{i+1}$

На следующем шаге применяем $(A \to \gamma)$ в выводе $(*)$

$A\beta_0' \rArr \gamma\beta_i' \rArr^*CU$

Докажем, что $С \in Select(A\to \gamma)$

Случай 1

$\gamma \rArr^* CU \rArr C \in First(\gamma) \subset Select(A \to \gamma)$

Случай 2

$A\beta_i' \rArr^* ACU \rArr c \in Follow(A) \subset Select(A\to \gamma)$