Предиктивный синтаксический анализ – это метод синтаксического анализа, не использующий возврата. В простейшем варианте, для реализации предиктивного анализа нам потребуется определить две функции, $\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$ выполняются следующие условия:

$\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$

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

Не существует терминала $t$ такого, что тела любой пары продукций одного нетерминала порождают строки, начинающиеся начинающуюся с $t$.
Пустую строку порождает только одно тело продукций нетерминала.
Если одно из тел продукций нетерминала $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 α$ выполняются действия:

$\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 α)$

Отметим, что $\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 означает снятие этого терминала со стека и входной строки.

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

Предиктивный анализ. LL(1)-анализ.

Левая факторизация

Нерекурсивный LL(1)-анализ

Пример