Предиктивный анализ. 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}(α)\) возможно по следующему принципу: \[\begin{align} \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} \\ \end{align}\]

Это определение может уходить в бесконечную рекурсию, если при вычислении \(\mathrm{FIRST}(X)\) нам снова встретится \(\mathrm{FIRST}(X)\). Однако понятно, что добавление \(\mathrm{FIRST}(X)\) к \(\mathrm{FIRST}(X)\) не изменит результата, поэтому мы можем просто пропускать такую рекурсию (т.е. при вычислении \(\mathrm{FIRST}(X)\) полагать рекурсивные \(\mathrm{FIRST}(X)=\varnothing\))

Для вычисления \(\mathrm{FOLLOW}(A)\), используем следующий принцип: \[\begin{align} \mathrm{FOLLOW}(S) & = \{\$\} \\ \mathrm{FOLLOW}(B) & = \{\mathrm{FIRST}(β) \setminus \{ε\} | A \to α B β\} \\ & \cup \{\mathrm{FOLLOW}(A) | A \to α B β, ε \in \mathrm{FIRST}(β)\} \end{align}\]

Опять же, в этом определении возможна бесконечная рекурсия, но мы можем использовать тот же приём, что и для \(\mathrm{FIRST}\). Отдельно отметим, что \(β\) может быть равно \(ε\), т.е. продукции вида \(A \to α B β\) включают продукции вида \(A \to α B\).

Если грамматика на основе функций \(\mathrm{FIRST}\) и \(\mathrm{FOLLOW}\) позволяет однозначно определить, какую продукцию необходимо выбрать на каждом шаге нисходящего синтаксического анализа, то такая грамматика называется \(LL(1)\)-грамматикой. Первый \(L\) означает разбор слева-направо. Второй \(L\) соответствует построению левого порождения. \(1\) означает, что для однозначного выбора достаточно “подсматривать” ровно один символ из входящего потока.

Собственно, кроме \(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\), выбирается продукция \(A \to α\), если текущий входной символ \(c\) входит в \(\mathrm{FRIST}(α)\) или, если \(ε \in \mathrm{FIRST}(α)\), то в \(\mathrm{FOLLOW}(A)\). Из этого несложно установить формальные требования для \(LL(1)\) грамматики:

Для любой из продукций \(A \to α_i\), \(α_i \neq α_j, i\neq j\) выполняются следующие условия:

  1. \(\forall i\neq j, \, \mathrm{FIRST}(α_i) \cap \mathrm{FIRST}(α_j) = \varnothing\)
  2. Если \(ε \in \mathrm{FIRST}(α_i)\), то \(\forall j \neq i,\,\mathrm{FIRST}(α_j) \cap \mathrm{FOLLOW}(A) = \varnothing\)

Словами это можно описать следующим образом:

  1. Не существует терминала \(t\) такого, что тела любой пары продукций одного нетерминала порождают строки, начинающиеся начинающуюся с \(t\).
  2. Пустую строку порождает только одно тело продукций нетерминала.
  3. Если одно из тел продукций нетерминала \(A\) порождает \(ε\), то другие тела продукций не порождают строк, начинающихся на терминал, который может следовать за \(A\).

Класс \(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() вернёт $.

Управляющая таблица для \(LL(1)\)-грамматики тоже строится достаточно легко. Для каждой продукции \(A \to α\) выполняются действия:

  1. \(\forall t \in (\mathrm{FIRST}(α)\setminus \{ε\}), M[A,t] = (A\to α)\)
  2. Если \(ε \in \mathrm{FIRST}(α)\), то \(\forall c \in \mathrm{FOLLOW}(A), M[A,c] = (A\to α)\)

Отметим, что \(\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 T E' \\ E' & \to + T E' | ε \\ T & \to F T' \\ T' & \to * F T' | ε \\ F & \to ( E ) | val \\ \end{align}\]

Вычислим функции \(\mathrm{FIRST}\) и \(\mathrm{FOLLOW}\) для каждой продукции:

\[\begin{align} \mathrm{FIRST}(F) & = \{(, val\} \\ \mathrm{FIRST}(T) & = \{(, val\} \\ \mathrm{FIRST}(E) & = \{(, val\} \\ \mathrm{FIRST}(E') & = \{+, ε\} \\ \mathrm{FIRST}(T') & = \{*, ε\} \\ \hline \mathrm{FIRST}(TE') & = \{(, val\} \\ \mathrm{FIRST}(+TE') & = \{+\} \\ \mathrm{FIRST}(FT') & = \{(, val\} \\ \mathrm{FIRST}(*FT') & = \{*\} \\ \mathrm{FIRST}((E)) & = \{(\} \\ \mathrm{FIRST}(val) & = \{val\} \\ \end{align}\]

\[\begin{align} \mathrm{FOLLOW}(E) & = \{\$, )\} \\ \mathrm{FOLLOW}(T) & = \{+, \$, )\} \\ \mathrm{FOLLOW}(F) & = \{*, +, \$, )\} \\ \mathrm{FOLLOW}(E') & = \{\$, )\} \\ \mathrm{FOLLOW}(T') & = \{+, \$, )\} \\ \end{align}\]

Несложно проверить, что эта грамматика является \(LL(1)\)-грамматикой. Построим управляющую \(LL(1)\) таблицу

\(val\) \(+\) \(*\) \((\) \()\) \(\$\)
\(E\) \(TE'\) \(TE'\)
\(E'\) \(+TE'\) \(ε\) \(ε\)
\(T\) \(FT'\) \(FT'\)
\(T'\) \(ε\) \(*FT'\) \(ε\) \(ε\)
\(F\) \(val\) \((E)\)

Рассмотрим теперь (в качестве примера) строку val+val*val, и как эта строка будет разбираться автоматом.

Вход Стек Действие Вывод
val+val*val$ E$ TE’ E → TE’
val+val*val$ TE’$ FT’ T → FT’
val+val*val$ FT’E’$ val F → val
val+val*val$ val T’E’$ !val
+val*val$ T’E’$ ε T’ → ε
+val*val$ E’$ +TE’ E’ → +TE’
+val*val$ +TE’$ !+
val*val$ TE’$ FT’ T → FT’
val*val$ FT’E’$ val F → val
val*val$ val T’E’$ !val
*val$ T’E’$ *FT’ T’ → *FT’
*val$ *FT’E’$ !* T’ → *FT’
val$ FT’E’$ val F → val
val$ val T’E’$ !val
$ T’E’$ ε T’ → ε
$ E’$ ε E’ → ε
$ $ !$ end

Здесь !t для терминала t означает снятие этого терминала со стека и входной строки.