Зміст:
Побудова \(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\}\]Опишемо алгоритм пошуку цієї множини:
-
\(\delta_0(S, S) = \{\{\varepsilon\}\}\), в інших випадках — невизначено.
-
\(\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\}\), в інших випадках — невизначено.
-
\(\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\}\), в інших випадках — невизначено.
-
\(\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).\)
-
Прочитати \(k\) лексем з вхідного файла програми (звичайно, інколи менше ніж \(k\)). В магазин занести таблицю \(T_0\).
-
Загальний крок:
-
Якщо на вершині магазина знаходиться таблиця \(T_i\), то елемент таблиці \(М(Т_i, \langle \text{k вхідних лексем}\rangle)\) визначає ланцюжок, який \(T_i\) заміщає на вершині магазина.
-
Якщо на вершині магазина \(a_i \in \Sigma\) перша поточна лексема з \(k\) прочитаних лексем рівна \(a_i\), то з вершини магазина зняти \(a_i\) та прочитати з вхідного файла додатково одну лексему (звичайно, якщо це можливо).
-
Якщо досягли кінця вхідного файла програми та магазин порожній, то програма не має синтаксичних помилок.
-
В інших випадках — синтаксична помилка.
-
Контрольні запитання
-
Наведіть визначення множини \(\text{Local}_k(S, A)\).
-
Опишіть алгоритм побудови \(\text{Local}_k(S, A)\).
-
Опишіть алгоритм побудови таблиць керування (або рядків великої результуючої таблиці керування).
-
Якою формулою визначається кількість рядків таблиці керування?
-
Опишіть алгоритм синтаксичного аналізу для \(LL(k)\)-граматики.
(традиційні відповіді можна переглянути у коментарях у вихідному коді цієї сторінки)