12.tex

\setcounter{section}{11}

\section{Побудова \texorpdfstring{$LL(1)$}{LLk}-синтаксичного аналізатора}

\subsection{Побудова \texorpdfstring{$LL(1)$}{LLk}-синтаксичного аналізатора}

Повернемось до умови, при якій граматика $G$ буде $LL(k)$-граматикою, а саме: для довільного виведення $S \Rightarrow^\star \omega_1 A \omega_2$ та правила $A \mapsto \alpha \mid \beta$ маємо $\text{First}_l(\alpha \cdot L) \cap \text{First}_k(\beta \cdot L) = \varnothing$, де $L = \text{First}_k(\omega_2)$. \medskip

Оскільки $L \subseteq \Sigma^{\star k}$ --- конструктивна множина, спробуємо побудувати всілякі множини $L$, які задовольняють попередньо сформульованій умові.

\subsubsection{\texorpdfstring{$\text{Local}_k(S, A)$}{LocalkSA}}

Визначимо наступну множину:
\begin{equation}
	\text{Local}_k(S, A) = \left\{ L \mid \exists x, \omega: S \Rightarrow^\star xA\omega, L = \text{First}_k(\omega) \right\}.
\end{equation}

Опишемо алгоритм пошуку цієї множини:
\begin{enumerate}
\item $\delta_0(S, S) = \{\{\varepsilon\}\}$, в інших випадках --- невизначено.
\item $\delta_1(S, A_i) = \delta_0(S, A_i) \cup \left\{ L \mid S \mapsto \omega_1 A_i \omega_2, L = \text{First}_k (\omega_2) \right\}$, в інших випадках --- невизначено.
\item 
\begin{multline*}
	\delta_n(S, A_i) = \delta_{n - 1}(S, A_i) \cup \\
	\cup \left\{ L \mid A_j \mapsto \omega_1 A_i \omega_2, L = \text{First}_k (\omega_2) \oplus_k L_p, L_p \in \text{Local}_k(S, A_j) \right\},
\end{multline*}
в інших випадках --- невизначено.
\item $\delta_m(S, A_i) = \delta_{m + 1}(S, A_i) = \ldots$, $\forall A_i \in N$.
\end{enumerate}

Тоді $\text{Local}_k(S, A_i) = \delta_m(S, A_i)$. \medskip

Виходячи з означення $\text{Local}_k(S, A_i)$, умови для $LL(k)$-граматики будуть наступними: для довільного $A$-правила вигляду $A \mapsto \omega_1 \mid \omega_2 \mid \ldots \mid \omega_p$ маємо: \[\text{First}_k (\omega_i \cdot L_m) \cap \text{First}_k(\omega_j \cdot L_m) = \varnothing, \quad i \ne k, \quad L_m \in \text{Local}_k(S, A).\]

Як наслідок, з алгоритму пошуку $\text{Local}_k(S, A_i)$ видно, що \[ \text{Follow}_k(A_i) = \bigcup_{j = 1}^m L_j, \quad L_j \in \text{Local}_k(S, A_i).\]

\subsubsection{Таблиці керування}

Для побудови синтаксичного аналізатора для $LL(k)$-граматики $(k > 1)$ необхідно побудувати множину таблиць, що забезпечать нам безтупиковий аналіз вхідного ланцюжка $w$ (програми) за час $O(n)$, де $n = \vert w\vert$. \medskip

Побудову множини таблиць для управління $LL(k)$-аналізатором почнемо з таблиці, яка визначає перший крок безпосереднього виводу $w$ в граматиці $G$: $T_0 = T_{S, \{\varepsilon\}}(u) = (T_1\alpha_1T_2\alpha_2\ldots T_p\alpha_p, n)$, де $n$ --- номер правила вигляду
\begin{equation}
    S\mapsto A_1\alpha_1A_2\alpha_2\ldots Ap\alpha_p,
\end{equation}
а $A_i \in N$, $\alpha_i \in \Sigma^\star$, і $u = \text{First}_k(A_1\alpha_1A_2\alpha_2\ldots A_p\alpha_p)$, і нарешті $i = \overline{1..p}$. Зрозуміло, що в інших випадках (якщо такого правила немає абощо) $T_0$ не визначена. \medskip

Неформально, коли в магазині автомата знаходиться аксіома $S$, то нас цікавить перших $k$ термінальних символів, які можна вивести з $S$ (аксіома --- поняття ``програма'') при умові, що після неї (програми) буде досягнуто EOF. \medskip

Імена інших таблиць $T_1, T_2, \ldots, T_p$ визначаються так: $T_i = T_{A_i, L_i}$, де
\begin{equation}
    L_i = \text{First}_k(\alpha_i A_{i + 1} \alpha_{i + 1} \ldots A_p \alpha_p), \quad i = \overline{1..p}.
\end{equation}

Наступні таблиці визначаються так:
\begin{equation}
    T_i = T_{A_i, L_i}(u) = (T_1\alpha_1T_2\alpha_2\ldots T_p\alpha_p, n)
\end{equation}
де $n$ --- номер правила вигляду $A_i\mapsto A_1\alpha_1A_2\alpha_2\ldots Ap\alpha_p$, а $A_j \in N$, $\alpha_j \in \Sigma^\star$, і $u = \text{First}_k(A_1\alpha_1A_2\alpha_2\ldots A_p\alpha_p) \oplus_k L_i$, і нарешті $j = \overline{1..p}$. Зрозуміло, що в інших випадках (якщо такого правила немає абощо) $T_i$ не визначена. \medskip

Імена інших таблиць $T_1, T_2, \ldots, T_p$ визначаються так: $T_j = T_{A_j, L_j}$, де
\begin{equation}
    L_j = \text{First}_k(\alpha_j A_{j + 1} \alpha_{j + 1} \ldots A_p \alpha_p) \oplus_k L_i, \quad j = \overline{1..p}.
\end{equation}

\subsubsection{Приклад}

Побудувати множину таблиць управління для $LL(2)$-граматики з наступною схемою правил:
\setcounter{equation}{0}
\begin{align}
	S &\mapsto abA, \\
	S &\mapsto \varepsilon, \\
	A &\mapsto Saa, \\
	A &\mapsto b.
\end{align}

Для вищенаведеної граматики множини $\text{First}_2(A_i)$, $A_i \in N$ будуть такі:
\begin{equation}
    \text{First}_2(S) = \{ab, \varepsilon\}, \quad \text{First}_2(A) = \{aa, ab, b\}
\end{equation}
а множини $\text{Local}_2(S, A_i)$, $A_i \in N$ будуть такі:
\begin{equation}
    \text{Local}_2(S, S) = \text{Local}_2(S, A) = \{\{\varepsilon\}, \{aa\}\}
\end{equation}

Побудуємо першу таблицю $T_0 = T_{S, \{\varepsilon\}}$. Для $S$-правила відповідні множини $u$ будуть такі:
\begin{itemize}
	\item $S \mapsto abA$, $u \in \text{First}_2(abA) = \{ab\}$.
	\item $S \mapsto \varepsilon$, $u \in \text{First}_2(\varepsilon) = \{\varepsilon\}$.
\end{itemize}

Таблиця $T_0$ визначається так:
\begin{table}[H]
	\centering
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
		\hline
		& $aa$ & $ab$ & $ba$ & $bb$ & $a$ & $b$ & $\varepsilon$ \\ \hline
		$T_0 = T_{S, \{\varepsilon\}}$ &  & $abT_1$, 1 &  &  &  &  & $\varepsilon$, 2 \\ \hline
	\end{tabular}
\end{table}

Нова таблиця управління $T_1 = T_{A, \{\varepsilon\}}$. Для $A$-правила відповідні множини $u$ будуть такі:
\begin{itemize}
	\item $A \mapsto Saa$, $u \in \text{First}_2(Saa) \oplus_2 \{\varepsilon\} = \{ab, aa\}$.
	\item $A \mapsto b$, $u \in \text{First}_2(b) \oplus_2 \{\varepsilon\} = \{b\}$.
\end{itemize}

Таблиця $T_1$ визначається так:
\begin{table}[H]
	\centering
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
		\hline
		 & $aa$ & $ab$ & $ba$ & $bb$ & $a$ & $b$ & $\varepsilon$ \\ \hline
		$T_1 = T_{A, \{\varepsilon\}}$ & $T_2aa$, 3 & $T_2aa$, 3 &  &  &  & $b$, 4 &  \\ \hline
	\end{tabular}
\end{table}

Нова таблиця управління $T_2 = T_{S, L}$ де $L = \text{First}_2 (aa) \oplus_2 \{\varepsilon\} = \{aa\}$. Для таблиці $T_2$ та $S$-правила множини $u$ будуть такі
\begin{itemize}
	\item $S \mapsto abA$, $u \in \text{First}_2(abA) \oplus_2 \{aa\} = \{ab\} \oplus_2 \{aa\} = \{ab\}$.
	\item $S \mapsto \varepsilon$, $u \in \text{First}_2(\varepsilon) \oplus_2 \{aa\} = \{aa\}$.
\end{itemize}

\begin{table}[H]
	\centering
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
		\hline
		 & $aa$ & $ab$ & $ba$ & $bb$ & $a$ & $b$ & $\varepsilon$ \\ \hline
		$T_2 = T_{S, \{aa\}}$ & $\varepsilon$, 2 & $abT_3$, 1 &  &  &  &  &  \\ \hline
	\end{tabular}
\end{table}

Наступна таблиця $T_3 = T_{A, L}$ де $L = \text{First}_2(\varepsilon) \oplus_2 \{aa\} = \{aa\}$. Для таблиці $T_3$ та $A$-правила множини $u$ будуть такі:
\begin{itemize}
	\item $A \mapsto Saa$, $u \in \text{First}_2(Saa) \oplus_2 \{aa\} = \{ab, aa\}$.
	\item $A \mapsto b$, $u \in \text{First}_2(b) \oplus_2 \{aa\} = \{ba\}$.
\end{itemize}

Таблиця $T_3$ визначається так:
\begin{table}[H]
	\centering
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
		\hline
		 & $aa$ & $ab$ & $ba$ & $bb$ & $a$ & $b$ & $\varepsilon$ \\ \hline
		$T_3 = T_{A, \{aa\}}$ & $T_2aa$, 3 & $T_2aa$, 3 & $b$, 4 &  &  &  &  \\ \hline
	\end{tabular}
\end{table}

Нова таблиця $T_4 = T_{S, L} = T_2$, оскільки $L = \text{First}_2(aa) \oplus_2 \{aa\} = \{aa\}$. \medskip

Ми визначили чотири таблиці-рядки (а їх кількість для довільної $LL(k)$-гра\-ма\-ти\-ки визначається як $\sum_{i = 1}^n n_i$, де $n_i$ --- кількість елементів множини $\text{Local}_k(S, A_i)$, $m = \vert N\vert$. \medskip

Об'єднаємо рядки-таблиці в єдину таблицю та виконаємо перейменування рядків:

\begin{table}[H]
	\centering
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
		\hline
		 & $aa$ & $ab$ & $ba$ & $bb$ & $a$ & $b$ & $\varepsilon$ \\ \hline
		$T_0$ &  & $abT_1$, 1 &  &  &  &  & $\varepsilon$, 2 \\ \hline
		$T_1$ & $T_2aa$, 3 & $T_2aa$, 3 &  &  &  & $b$, 4 &  \\ \hline
		$T_2$ & $\varepsilon$, 2 & $abT_3$, 1 &  &  &  &  &  \\ \hline
		$T_3$ & $T_2aa$, 3 & $T_2aa$, 3 & $b$, 4 &  &  &  &  \\ \hline
	\end{tabular}
\end{table}
\subsubsection{Алгоритм}

Синтаксичний аналізатор для $LL(k)$-граматики $(k > 1)$.
\begin{enumerate}
	\item Прочитати $k$ лексем з вхідного файла програми (звичайно, інколи менше ніж $k$). В магазин занести таблицю $T_0$.
	\item Загальний крок:
	\begin{itemize}
		\item Якщо на вершині магазина знаходиться таблиця $T_i$, то елемент таблиці $M(T_i, \langle \text{k вхідних лексем}\rangle)$ визначає ланцюжок, який $T_i$ заміщає на вершині магазина.
		\item Якщо на вершині магазина $a_i \in \Sigma$ перша поточна лексема з $k$ прочитаних лексем рівна $a_i$, то з вершини магазина зняти $a_i$ та прочитати з вхідного файла додатково одну лексему (звичайно, якщо це можливо).
		\item Якщо досягли кінця вхідного файла програми та магазин порожній, то програма не має синтаксичних помилок.
		\item В інших випадках --- синтаксична помилка.
	\end{itemize}
\end{enumerate}

\subsection{Контрольні запитання}
\begin{enumerate}
	\item Наведіть визначення множини $\text{Local}_k(S, A)$.
	\item Опишіть алгоритм побудови $\text{Local}_k(S, A)$.
	\item Опишіть алгоритм побудови таблиць керування (або рядків великої результуючої таблиці керування).
	\item Якою формулою визначається кількість рядків таблиці керування?
	\item Опишіть алгоритм синтаксичного аналізу для $LL(k)$-граматики.
\end{enumerate}