Зміст:

• Синтаксичний аналіз на основі \(LL(1)\)-граматик

  • Приклад

  • Алгоритм

  • Майже \(LL(1)\)-граматики

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

Синтаксичний аналіз на основі \(LL(1)\)-граматик

Згідно визначення \(LL(1)\)-граматики, граматика \(G\) буде \(LL(1)\) граматикою тоді і тільки тоді, коли для кожного \(A\)-правила вигляду \(A \mapsto \omega_1 \mid \omega_2 \mid \ldots \mid \omega_p\) виконуються умови

• \(\text{First}_1 (\omega_i) \cap \text{First}_1 (\omega_j) = \varnothing\) для довільних \(i \ne j\).

• якщо \(\omega_i \Rightarrow^\star \varepsilon\) для якогось \(i\), то \(\text{First}_1(\omega_j) \cap \text{Follow}_1 (A) = \varnothing\) для усіх \(j \ne i\).

Таблиця \(M(a, b)\) де \(a \in (N \cup \Sigma \cup \{\varepsilon\})\), \(b \in (\Sigma \cup \{\varepsilon\})\) керування \(LL(1)\)-синтаксичним аналізатором визначається наступним чином:

1. \(M(A, b)\) — номер правила вигляду \(A \mapsto \omega_i\) такого, що \(\{b\} = \text{First}_1(\omega_i \cdot \text{Follow}_1 (A))\).

2. \(M(a, a)\) містить інструкцію pop для аналізатора яка позначає необхідність перенести символ \(a\) з пам’яті аналізатору у поле результату.

3. \(M(\varepsilon, \varepsilon)\) містить інструкцію accept для аналізаторп яка позначає що опрацьоване слово необхідно допустити (повернути true абощо).

4. В інших випадках \(M(a, b)\) невизначено, чи радше містить інструкцію reject для аналізатора яка позначає що опрацьоване слово необхідно недопустити (повернути false абощо).

Приклад

Розглянемо вже добре відому нам граматику зі схемою

\[\begin{align*} S &\mapsto BA, \\ A &\mapsto +BA \mid \varepsilon, \\ B &\mapsto DC, \\ C &\mapsto \times DC \mid \varepsilon, \\ D &\mapsto (S) \mid a. \end{align*}\]

і пронумеруємо її правила таким чином:

\[\begin{align} S &\mapsto BA, \\ A &\mapsto +BA, \\ A &\mapsto \varepsilon, \\ B &\mapsto DC, \\ C &\mapsto \times DC, \\ C &\mapsto \varepsilon, \\ D &\mapsto (S), \\ D &\mapsto a. \end{align}\]

Нагадаємо що для цієї граматики \(\text{First}_1 (S) = \text{First}_1 (B) = \text{First}_1 (D) = \{(, a\},\) \(\text{First}_1 (A) = \{+, \varepsilon\},\) \(\text{First}_1 (A) = \{\times, \varepsilon\},\) а також \(\text{Follow}_1 (S) = \text{Follow}_1 (A) = \{ \varepsilon, )\},\) \(\text{Follow}_1 (B) = \text{Follow}_1 (C) = \{+, \varepsilon, )\},\) \(\text{Follow}_1 (D) = \{+, \times, \varepsilon, )\}.\)

Знайдемо множини \(\text{First}_1(\omega_i \cdot \text{Follow}_1 (A))\) як \(\text{First}_1(\omega_i) \oplus_1 \text{Follow}_1 (A))\) використовуючи результати минулої лекції.

При побудові таблиці \(M(a,b)\) керування \(LL(1)\)-синтаксичним аналізатором достатньо лише побудувати першу її частину, тобто ту яка з \(N \times (\Sigma \cup \{\varepsilon\})\), оскільки решта таблиці визначається стандартно:

	\(a\)	\((\)	\()\)	\(+\)	\(\times\)	\(\varepsilon\)
\(S\)	1	1
\(A\)			3	2		3
\(B\)	4	4
\(C\)			6	6	5	6
\(D\)	8	7

Алгоритм

Побудуємо \(LL(1)\)-синтаксичний аналізатор на основі таблиці керування \(M(a,b)\):

1. Прочитаємо поточну лексему з вхідного файла, у стек магазинного автомата занесемо аксіому \(S\).

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

   • Якщо на вершині стека знаходиться нетермінал \(A_i\), то активізувати рядок таблиці, позначений \(A_i\). Елемент \(M(A_i, \langle\text{поточна лексема}\rangle)\) визначає номер правила, права частина якого заміняє \(A_i\) на вершині стека.

   • Якщо на вершині стека лексема \(a_i = \langle\text{поточна лексема}\rangle\), то з вершини стека зняти \(a_i\) та прочитати нову поточну лексему.

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

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

Майже \(LL(1)\)-граматики

У деяких випадках досить складно (а інколи й принципово неможливо побудувати \(LL(1)\)-граматику для реальної мови програмування. При цьому \(LL(1)\)-властивість задовольняється майже для всіх правил — лише декілька правил створюють конфлікт, але для цих правил задовольняється сильна \(LL(2)\)-властивість. Тоді таблиця \(M(a,b)\) визначається в такий спосіб:

• \(M(A,b) = \langle\text{номер правила}\rangle\) вигляду \(A_i \mapsto \omega_i\), такого, що \(b \in \text{First}_1(\omega_i \cdot \text{Follow}_1(A))\)

• \(M(A,b) = \langle\text{ім'я допоміжної програми}\rangle\) за умови, що

  \[b \in \text{First}_1(\omega_i \cdot \text{Follow}_1(A)) \cap b \in \text{First}_1(\omega_j \cdot \text{Follow}_1(A)), \quad i \ne j\]

Програма, яка виконує додатковий аналіз вхідного ланцюжка, повинна:

• прочитати додатково одну лексему;

• на основі двох вхідних лексем вибрати необхідне правило або сигналізувати про синтаксичну помилку;

• у випадку, коли правило вибрано, необхідно повернути додатково прочитану лексему у вхідний файл.

Звичайно, необхідно модифікувати алгоритм \(LL(1)\)-синтаксичного аналізатора.

При цьому підпрограма аналізу конфліктної ситуації повинна додатково прочитати нову вхідну лексему, далі скориставшись контекстом з двох лексем, визначити номер правила, яке замість нетермінала на вершині стека та повернути додатково прочитану лексему у вхідний файл.

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

1. Які дві умови повинна задовольняти граматика щоб бути \(LL(1)\)-граматикою?

2. Що таке таблиця керування синтаксичного аналізатора на основі \(LL(1)\)-граматики?

3. Який автомат і яка таблиця використовуються в алгоритмі роботи \(LL(1)\)-синтаксичного аналізатора?

4. Опишіть алгоритм роботи \(LL(1)\)-синтаксичного аналізатора.

5. Як необхідно модифікувати таблицю керування для сильної \(LL(2)\)-граматики яка є майже \(LL(1)\)-граматикою?

6. Як необхідно модифікувати алгоритм роботи синтаксичного аналізатора для сильної \(LL(2)\)-граматики яка є майже \(LL(1)\)-граматикою?

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

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

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