Предиктивный анализ. LL(1)-анализ.
- Предиктивный синтаксический анализ – метод синтаксического анализа, не использующий возврата.
- В простейшем варианте потребуется две функции, \(\mathrm{FIRST}\) и \(\mathrm{FOLLOW}\)
- Для функции \(\mathrm{FOLLOW}\) введём символ \(\$\), означающий конец входного потока.
- \(\mathrm{FIRST}(α)\)
- Множество всех терминалов, на которые может начинаться строка терминалов и нетерминалов α, или ε, если \(α \overset{*}\Rightarrow ε\)
\(\mathrm{FIRST}(α) = \{ t | t \in T, α \overset{*}\Rightarrow t β \} \cup \{ ε | α \overset{*}\Rightarrow ε \}\)
- \(\mathrm{FOLLOW}(A)\)
- Множество терминалов или \(\$\), которые могут следовать за нетерминалом \(A\) в каком-либо порождении.
Множество \(t \in T\), таких, что существует порождение \(S \overset{*}\Rightarrow α A t β\), и \(\$\), если существует порождение \(S \overset{*}\Rightarrow α A\).
\(\mathrm{FOLLOW}(A) = \{ t | t \in T, S \overset{*}\Rightarrow α A t β \} \cup \{ \$ | S \overset{*}\Rightarrow α A \}\)
Вычисление \(\mathrm{FIRST}(α)\) возможно по следующему принципу: \[\mathrm{FIRST}(X α) =\] \[\begin{cases} \mathrm{FIRST}(X), & ε \notin \mathrm{FIRST}(X) \\ (\mathrm{FIRST}(X) \setminus \{ε\}) \cup \mathrm{FIRST}(α), & \text{otherwise} \end{cases}\] \[\mathrm{FIRST}(X) =\] \[\begin{cases} X, & X \in T \cup \{ε\}\\ \bigcup \mathrm{FIRST}(β), & X \in N,\, \forall β \in \{β | (X \to β) \in P \} \end{cases}\]
Для вычисления \(\mathrm{FOLLOW}(A)\), используем следующий принцип: \[\mathrm{FOLLOW}(S) = \{\$\}\] \[\mathrm{FOLLOW}(B) =\] \[\{\mathrm{FIRST}(β) \setminus \{ε\} | A \to α B β\} \\ \cup \{\mathrm{FOLLOW}(A) | A \to α B β, ε \in \mathrm{FIRST}(β)\}\]
- Если грамматика на основе \(\mathrm{FIRST}\) и \(\mathrm{FOLLOW}\) позволяет однозначно определить продукцию на каждом шаге нисходящего синтаксического анализа, она называется \(LL(1)\)-грамматикой.
- Существует класс \(LL(k)\) грамматик, где \(k \in \mathbb N\).
- Класс \(LL(*)\) – размер предпросмотра не фиксирован, но при этом должен удовлетворять некому регулярному выражению.
- \(\forall k \in \mathbb N, LL(k) \subset LL(k+1) \subset LL(*)\)
Алгоритм выбора продукции на основе функций \(\mathrm{FIRST}\) и \(\mathrm{FOLLOW}\):
При разборе \(A\in N\), выбирается \(A \to α\), если текущий входной символ \(c \in \mathrm{FRIST}(α)\) или, если \(ε \in \mathrm{FIRST}(α)\), то в \(c\in\mathrm{FOLLOW}(A)\).
Из этого формальные требования для \(LL(1)\) грамматики:
\(\forall A \to α_i\), \(α_i \neq α_j, i\neq j\) выполняются:
- \(\forall i\neq j, \, \mathrm{FIRST}(α_i) \cap \mathrm{FIRST}(α_j) = \varnothing\)
- Если \(ε \in \mathrm{FIRST}(α_i)\), то \(\forall j \neq i,\,\mathrm{FIRST}(α_j) \cap \mathrm{FOLLOW}(A) = \varnothing\)
\(LL(k)\) включает только нелеворекурсивные однозначные грамматики.
Левая факторизация
- \(LL(k)\) можно преобразовать к эквивалентным \(LL(1)\) грамматикам
- Для этого – левая факторизация
- Добавлением нетерминалов исключить продукции, порождающие строки, начинающиеся с одинаковых терминалов.
- Продукции вида (\(γ\neq ε\)) \[A \to γ β_1 | γ β_2,\] делают грамматику не \(LL(1)\)
- можно переписать в виде \[\begin{align} A & \to γ A' \\ A' & \to β_1 | β_2 \end{align}\]
- В общем случае \[A \to γ β_1 | γ β_2 | \ldots | γ β_n,\]
- в виде \[\begin{align} A & \to γ A' \\ A' & \to β_1 | β_2 | \ldots | β_n \end{align}.\]
- для некоторых грамматик, левая факторизация может добавлять множество “лишних” нетерминалов.
- например \(A \to a b | a a b | a a a b | a a a a b\)
- после полной левой факторизации даст \[\begin{align} A & \to a A' \\ A' & \to b | a A'' \\ A'' & \to b | a A''' \\ A''' & \to b | a b \\ \end{align}.\]
Формальный алгоритм: для каждого нетерминала, для всех продукций этого нетерминала, ищется наиболее длинный префикс, общий для 2 или более альтернатив. Затем применяется один шаг замены. Для оставшихся продукций, процесс повторяется.
Нерекурсивный LL(1)-анализ
- класс однозначных контекстно-свободных грамматик соответствует детерминированным автоматам с магазинной памятью
- Программа автомата управляется таблицей, для символа (терминального или нетерминального) на вершине стека и текущего входного определяет следующее действие.
- “следующее действие”: помещение/снятие символов на стек, переход к следующему символу, ошибка
- основное решение программы автомата – какое тело продукции следует разбирать далее
- пусть управляющая таблица \(M[A, a]\) содержит в ячейках тело какой-то продукции для \(A\)
stack.push($);
stack.push(S);
X = stack.top(); // == S
a = getNextToken();
while(X != $) {
if (X == a) {
a = getNextToken();
stack.pop();
}
else if(X -- терминал)
reportError();
// далее X -- нетерминал
else if(M[X, a] == Y₁ Y₂ … Yₖ) {
print("X -> Y₁ Y₂ … Yₖ");
stack.pop();
if(M[X, a] != ε) {
for(l in k…1)
stack.push(Yₗ);
}
}
// нет записи M[X, a]
else reportError();
X = stack.top();
}$ – конец входной строки.
Вызовы getNextToken() после конца входной строки возвращают $
Управляющая таблица. \(\forall A \to α\):
- \(\forall t \in (\mathrm{FIRST}(α)\setminus \{ε\}), M[A,t] = (A\to α)\)
- Если \(ε \in \mathrm{FIRST}(α)\), то \(\forall c \in \mathrm{FOLLOW}(A), M[A,c] = (A\to α)\)
Отметим, \(\$ \in \mathrm{FOLLOW}(A)\).
Автомат, разбирающий \(LL(1)\)-грамматику, называется \(LL(1)\)-автоматом.
Пример
\[\begin{align} E & \to E + T | T \\ T & \to T * F | F \\ F & \to ( E ) | val \\ \end{align}\]
- Терминалы: \(\{+, *, (, ), val\}\)
- Нетерминалы: \(\{E, T, F\}\)
- Стартовый символ: \(E\).
\[\begin{align} E & \to E + T | T \\ T & \to T * F | F \\ F & \to ( E ) | val \\ \end{align}\]
Удалим левую рекурсию.
\[\begin{align} E & \to T E' \\ E' & \to + T E' | ε \\ T & \to F T' \\ T' & \to * F T' | ε \\ F & \to ( E ) | val \\ \end{align}\]
\[\begin{align} E & \to T E' \\ E' & \to + T E' | ε \\ T & \to F T' \\ T' & \to * F T' | ε \\ F & \to ( E ) | val \\ \end{align}\]
- \(\mathrm{FIRST}(F) = \{(, val\}\)
- \(\mathrm{FIRST}(T) = \{(, val\}\)
- \(\mathrm{FIRST}(E) = \{(, val\}\)
- \(\mathrm{FIRST}(E') = \{+, ε\}\)
- \(\mathrm{FIRST}(T') = \{*, ε\}\)
- \(\mathrm{FIRST}(TE') = \{(, val\}\)
- \(\mathrm{FIRST}(+TE') = \{+\}\)
- \(\mathrm{FIRST}(FT') = \{(, val\}\)
- \(\mathrm{FIRST}(*FT') = \{*\}\)
- \(\mathrm{FIRST}((E)) = \{(\}\)
- \(\mathrm{FIRST}(val) = \{val\}\)
- \(\mathrm{FOLLOW}(E) = \{\$, )\}\)
- \(\mathrm{FOLLOW}(T) = \{+, \$, )\}\)
- \(\mathrm{FOLLOW}(F) = \{*, +, \$, )\}\)
- \(\mathrm{FOLLOW}(E') = \{\$, )\}\)
- \(\mathrm{FOLLOW}(T') = \{+, \$, )\}\)
- является \(LL(1)\)-грамматикой
\[\begin{align} E & \to T E' \\ E' & \to + T E' | ε \\ T & \to F T' \\ T' & \to * F T' | ε \\ F & \to ( E ) | val \\ \end{align}\]
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | ||||||
| \(E'\) | ||||||
| \(T\) | ||||||
| \(T'\) | ||||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | |||||
| \(E'\) | ||||||
| \(T\) | ||||||
| \(T'\) | ||||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | ||||||
| \(T\) | ||||||
| \(T'\) | ||||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | |||||
| \(T\) | ||||||
| \(T'\) | ||||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | ||||
| \(T\) | ||||||
| \(T'\) | ||||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | ||||||
| \(T'\) | ||||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | \(FT'\) | |||||
| \(T'\) | ||||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | \(FT'\) | \(FT'\) | ||||
| \(T'\) | ||||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | \(FT'\) | \(FT'\) | ||||
| \(T'\) | \(*FT'\) | |||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | \(FT'\) | \(FT'\) | ||||
| \(T'\) | \(ε\) | \(*FT'\) | ||||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | \(FT'\) | \(FT'\) | ||||
| \(T'\) | \(ε\) | \(*FT'\) | \(ε\) | |||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | \(FT'\) | \(FT'\) | ||||
| \(T'\) | \(ε\) | \(*FT'\) | \(ε\) | \(ε\) | ||
| \(F\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | \(FT'\) | \(FT'\) | ||||
| \(T'\) | \(ε\) | \(*FT'\) | \(ε\) | \(ε\) | ||
| \(F\) | \((E)\) |
| \(val\) | \(+\) | \(*\) | \((\) | \()\) | \(\$\) | |
|---|---|---|---|---|---|---|
| \(E\) | \(TE'\) | \(TE'\) | ||||
| \(E'\) | \(+TE'\) | \(ε\) | \(ε\) | |||
| \(T\) | \(FT'\) | \(FT'\) | ||||
| \(T'\) | \(ε\) | \(*FT'\) | \(ε\) | \(ε\) | ||
| \(F\) | \(val\) | \((E)\) |
- \(\mathrm{FIRST}(TE') = \{(, val\}\)
- \(\mathrm{FIRST}(+TE') = \{+\}\)
- \(\mathrm{FIRST}(FT') = \{(, val\}\)
- \(\mathrm{FIRST}(*FT') = \{*\}\)
- \(\mathrm{FIRST}((E)) = \{(\}\)
- \(\mathrm{FIRST}(val) = \{val\}\)
- \(\mathrm{FOLLOW}(E) = \{\$, )\}\)
- \(\mathrm{FOLLOW}(T) = \{+, \$, )\}\)
- \(\mathrm{FOLLOW}(F) = \{*, +, \$, )\}\)
- \(\mathrm{FOLLOW}(E') = \{\$, )\}\)
- \(\mathrm{FOLLOW}(T') = \{+, \$, )\}\)