Зміст:

• Побудова $LL(k)$-синтаксичного аналізатора

  • $\text{Local}_k(S, A)$

  • Таблиці керування

  • Приклад

  • Алгоритм

• Контрольні запитання

Побудова $LL(k)$-синтаксичного аналізатора

Повернемось до умови, при якій граматика $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)$.

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

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

Визначимо наступну множину:

$$\text{Local}_k(S, A) = \left\{ L \mid \exists x, \omega: S \Rightarrow^\star xA\omega, L = \text{First}_k(\omega) \right\}$$

Опишемо алгоритм пошуку цієї множини:

1. $\delta_0(S, S) = \{\{\varepsilon\}\}$, в інших випадках — невизначено.

2. $\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\}$, в інших випадках — невизначено.

3. $\delta_n(S, A_i) = \delta_{n - 1}(S, A_i) \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\}$, в інших випадках — невизначено.

4. $\delta_m(S, A_i) = \delta_{m + 1}(S, A_i) = \ldots$, $\forall A_i \in N$.

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

Виходячи з означення $\text{Local}_k(S, A_i)$, умови для $LL(k)$-граматики будуть наступними: для довільного $А$-правила вигляду $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).$$

Таблиці керування

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

Побудову множини таблиць для управління $LL(k)$-аналізатором почнемо з таблиці, яка визначає перший крок безпосереднього виводу $w$ в граматиці $G$: $T_0 = T_{S, \{\varepsilon\}}(u) = (T_1\alpha_1T_2\alpha_2\ldots T_p\alpha_p, n),$ де $n$ — номер правила вигляду $S\mapsto A_1\alpha_1A_2\alpha_2\ldots Ap\alpha_p,$ а $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$ не визначена.

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

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

Наступні таблиці визначаються так: $T_i = T_{A_i, L_i}(u) = (T_1\alpha_1T_2\alpha_2\ldots T_p\alpha_p, n),$ де $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$ не визначена.

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

Приклад

Побудувати множину таблиць управління для $LL(2)$-граматики з наступною схемою правил:

$$\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$ будуть такі: $\text{First}_2(S) = \{ab, \varepsilon\},$ $\text{First}_2(A) = \{aa, ab, b\},$ а множини $\text{Local}_2(S, A_i),$ $A_i \in N$ будуть такі: $\text{Local}_2(S, S) = \text{Local}_2(S, A) = \{\{\varepsilon\}, \{aa\}\}.$

Побудуємо першу таблицю $T_0 = T_{S, \{\varepsilon\}}$. Для $S$-правила відповідні множини $u$ будуть такі:

• $S \mapsto abA,$ $u \in \text{First}_2(abA) = \{ab\}.$

• $S \mapsto \varepsilon,$ $u \in \text{First}_2(\varepsilon) = \{\varepsilon\}.$

Таблиця $T_0$ визначається так:

	$aa$	$ab$	$ba$	$bb$	$a$	$b$	$\varepsilon$
$T_0 = T_{S, \{\varepsilon\}}$		$abT_1$, 1					$\varepsilon$, 2

Нова таблиця управління $T_1 = T_{A, \{\varepsilon\}}$. Для $A$-правила відповідні множини $u$ будуть такі:

• $A \mapsto Saa,$ $u \in \text{First}_2(Saa) \oplus_2 \{\varepsilon\} = \{ab, aa\}.$

• $A \mapsto b,$ $u \in \text{First}_2(b) \oplus_2 \{\varepsilon\} = \{b\}.$

Таблиця $T_1$ визначається так:

	$aa$	$ab$	$ba$	$bb$	$a$	$b$	$\varepsilon$
$T_1 = T_{A, \{\varepsilon\}}$	$T_2aa$, 3	$T_2aa$, 3				$b$, 4

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

• $S \mapsto abA,$ $u \in \text{First}_2(abA) \oplus_2 \{aa\} = \{ab\} \oplus_2 \{aa\} = \{ab\}.$

• $S \mapsto \varepsilon,$ $u \in \text{First}_2(\varepsilon) \oplus_2 \{aa\} = \{aa\}.$

	$aa$	$ab$	$ba$	$bb$	$a$	$b$	$\varepsilon$
$T_2 = T_{S, \{aa\}}$	$\varepsilon$, 2	$abT_3$, 1

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

• $A \mapsto Saa,$ $u \in \text{First}_2(Saa) \oplus_2 \{aa\} = \{ab, aa\}.$

• $A \mapsto b,$ $u \in \text{First}_2(b) \oplus_2 \{aa\} = \{ba\}.$

Таблиця $T_3$ визначається так:

	$aa$	$ab$	$ba$	$bb$	$a$	$b$	$\varepsilon$
$T_3 = T_{A, \{aa\}}$	$T_2aa$, 3	$T_2aa$, 3	$b$, 4

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

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

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

	$aa$	$ab$	$ba$	$bb$	$a$	$b$	$\varepsilon$
$T_0$		$abT_1$, 1					$\varepsilon$, 2
$T_1$	$T_2aa$, 3	$T_2aa$, 3				$b$, 4
$T_2$	$\varepsilon$, 2	$abT_3$, 1
$T_3$	$T_2aa$, 3	$T_2aa$, 3	$b$, 4

Алгоритм

Синтаксичний аналізатор для $LL(k)$-граматики $(k > 1).$

1. Прочитати $k$ лексем з вхідного файла програми (звичайно, інколи менше ніж $k$). В магазин занести таблицю $T_0$.

2. Загальний крок:

   • Якщо на вершині магазина знаходиться таблиця $T_i$, то елемент таблиці $М(Т_i, \langle \text{k вхідних лексем}\rangle)$ визначає ланцюжок, який $T_i$ заміщає на вершині магазина.

   • Якщо на вершині магазина $a_i \in \Sigma$ перша поточна лексема з $k$ прочитаних лексем рівна $a_i$, то з вершини магазина зняти $a_i$ та прочитати з вхідного файла додатково одну лексему (звичайно, якщо це можливо).

   • Якщо досягли кінця вхідного файла програми та магазин порожній, то програма не має синтаксичних помилок.

   • В інших випадках — синтаксична помилка.

Контрольні запитання

1. Наведіть визначення множини $\text{Local}_k(S, A)$.

2. Опишіть алгоритм побудови $\text{Local}_k(S, A)$.

3. Опишіть алгоритм побудови таблиць керування (або рядків великої результуючої таблиці керування).

4. Якою формулою визначається кількість рядків таблиці керування?

5. Опишіть алгоритм синтаксичного аналізу для $LL(k)$-граматики.

(традиційні відповіді можна переглянути у коментарях у вихідному коді цієї сторінки)

Назад до лекцій

Назад на головну