LL(k)-грамматики, множества FIRST и FOLLOW

Наибольший интерес в построении синтаксических анализаторов (парсеров) представляют LL(1)-грамматики, так как для них возможно построение нисходящих парсеров без возврата, то есть без корректировки выбранных правил в грамматике. LL(1)-грамматики являются подмножеством КС-грамматик. Однако для достаточно большого количества формальных языков можно построить LL(1)-грамматику, например, для языка арифметических выражений и даже для некоторых языков программирования, в частности можно и для языка Java.

LL(k)-грамматика

Дадим теперь формально определение LL(k)-грамматики.

Определение:

Пусть $\Gamma =\langle \Sigma, N, S, P \rangle$ — КС-грамматика. Рассмотрим два произвольных левосторонних вывода слова $w$ в этой грамматике: $S \Rightarrow^* p A \beta \Rightarrow p \alpha \beta \Rightarrow^* p y \eta$ $S \Rightarrow^* p A \beta \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi$ где $p$ и $y$ — цепочки из терминалов, уже разобранная часть слова $w$, $A$ — нетерминал грамматики, в которой есть правила $A \to \alpha$ и $A \to \alpha'$, причём $\alpha, \alpha', \beta, \eta, \xi$ — последовательности из терминалов и нетерминалов. Если из выполнения условий, что $|y| = k$ или $|y| \lt k, \eta = \xi = \varepsilon$, следует равенство $\alpha = \alpha'$, то $\Gamma$ называется LL(k)-грамматикой.

LL(1)-грамматика является частным случаем. Её определение почти такое же, только вместо строки $y$ один символ $c \in \Sigma \cup \{\varepsilon\}$.

Неформально это означает, что, посмотрев на очередной символ после уже выведенной части слова, можно однозначно определить, какое правило из грамматики выбрать.

FIRST и FOLLOW

Ключевую роль в построении парсеров для LL(1)-грамматик играют множества $\mathrm{FIRST}$ и $\mathrm{FOLLOW}$.

Пусть $c$ — символ из алфавита $\Sigma$, $\alpha,\ \beta$ — строки из нетерминалов и терминалов (возможно пустые), $S,\ A$ — нетерминалы грамматики (начальный и произвольный соответственно), $\$$ — символ окончания слова. Тогда определим $\mathrm{FIRST}$ и $\mathrm{FOLLOW}$ следующим образом:

Определение:

$\mathrm{FIRST}(A) = \{c \mid A \Rightarrow^* c \beta \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \}$

Определение:

$\mathrm{FOLLOW}(A) = \{c \mid S \Rightarrow^* \alpha A c \beta \} \cup \{ \$ \ \mathrm{if}\ S \Rightarrow^* \alpha A \}$

Другими словами, $\mathrm{FIRST}(A)$ — все символы (терминалы), с которых могут начинаться всевозможные выводы из $\alpha$, а $\mathrm{FOLLOW}(A)$ — всевозможные символы, которые встречаются после нетерминала $A$ во всех небесполезных правилах грамматики.

Замечание: более общим случаем множества $\mathrm{FIRST}$ является множество $\mathrm{FIRST}_k$, однако в данном конспекте оно не используется.

Определение:

$\mathrm{FIRST}_k(A) = \{w \mid A \Rightarrow^* w \beta,\ |w| \leqslant k \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \}$

Примеры

Множества $\mathrm{FIRST}$ и $\mathrm{FOLLOW}$ могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.

• $A \to (A)A \mid \varepsilon$
• $B \to BB \mid (B) \mid \varepsilon$

Правило	FIRST	FOLLOW
$A$	$\{\ (,\ \varepsilon\ \}$	$\{\ ),\ \$\ \}$
$B$	$\{\ (,\ \varepsilon\ \}$	$\{\ (,\ ),\ \$\ \}$

Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW

Далее будет показано, как множества $\mathrm{FIRST}$ и $\mathrm{FOLLOW}$ связаны с понятием LL(1)-грамматики.

Теорема:

$\Gamma =\langle \Sigma, N, S, P \rangle$ — LL(1)-грамматика $\Leftrightarrow$ $A \to \alpha,\ A \to \beta, A \in N \ \Rightarrow \ \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing$ $A \to \alpha,\ A \to \beta, A \in N,\ \varepsilon \in \mathrm{FIRST}(\alpha) \ \Rightarrow \ \mathrm{FOLLOW}(A) \cap \mathrm{FIRST}(\beta) = \varnothing$

Доказательство:

$\triangleright$

$\Leftarrow$ Предположим, что данная грамматика не будет LL(1)-грамматикой. Значит, у какого-то слова $w$ существует два различных левосторонних вывода. $S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma$ $S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma$ Но это противоречит тому, что $\mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing$. Аналогично проверятся второе условие. Если, например, $\alpha \Rightarrow^* \varepsilon$, то $\varepsilon \in \mathrm{FIRST}(\alpha)$, и $\mathrm{FOLLOW}(A) \cap \mathrm{FIRST}(\beta) \ne \varnothing$ $\Rightarrow$ Предположим, что есть два различных правила $A \to \alpha$ и $A \to \beta$ таких, что $c \in \mathrm{FIRST}(A) \cap \mathrm{FIRST}(\beta)$. Тогда: $S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma$ $S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma$ Последний переход можно совершить, так как $c$ лежит в пересечении множеств $\mathrm{FIRST}$ двух правил вывода. Так как грамматика $\Gamma$ является LL(1)-грамматикой, то из определения следует, что $\alpha = \beta$. Это противоречит предположению, что $\alpha$ и $\beta$ — различные правила. Второе условие проверяется аналогичным образом.

$\triangleleft$

Следствия

Сформулируем несколько важных cледствий из теоремы.

Левая рекурсия

Утверждение (1):

Грамматика $\Gamma$ cодержит левую рекурсию $\Rightarrow \ \Gamma$ не является LL(1)-грамматикой.

$\triangleright$

Если грамматика содержит левую рекурсию, значит, в ней существует какой-то нетерминал $A$ с правилами $A \to A \alpha \mid \beta$, где $\beta$ — строка из терминалов и нетерминалов, не начинающаяся с $A$. Тогда понятно, что $\mathrm{FIRST}(A\alpha) \cap \mathrm{FIRST}(\beta) \ne \varnothing$, и это противоречит первому условию теоремы.

$\triangleleft$

Чтобы избавиться от левой рекурсии, можно воспользоваться алгоритмом устранения левой рекурсии.

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

Утверждение (2):

Грамматика $\Gamma$ cодержит правое ветвление $\Rightarrow \ \Gamma$ не является LL(1)-грамматикой.

$\triangleright$

Наличие в грамматике правого ветвления означает, что существует правило $A \to \alpha \beta \mid \alpha \gamma, \alpha \ne \varepsilon$. Очевидно, что $\mathrm{FIRST}(\alpha \beta) \cap \mathrm{FIRST}(\alpha \gamma) \ne \varnothing$. Поэтому грамматика не будет LL(1)-грамматикой по первому условию теоремы.

$\triangleleft$

Алгоритм устранения правого ветвленения

Чтобы избавиться от правого ветвления, нужно воспользоваться алгоритмом левой факторизации. Его суть заключается в следующем: для каждого нетерминала $A$ ищем самый длинный префикс, общий для двух или более правил вывода из $A$. Важно, чтобы как можно больше строк имело общий префикс, и можно было вынести части правил после общего префикса в отдельный нетерминал. Более формально, рассмотрим правила

$A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m$

Причём $\alpha \ne \varepsilon$, а наибольший общий префикс $\alpha$ и $\gamma_i\ (1 \leqslant i \leqslant m$) равен $\varepsilon$. Тогда изменим грамматику следующим образом, введя новый нетерминал $A'$:

$A \to \alpha A' \mid \gamma_1 \mid \ldots \mid \gamma_m$

$A' \to \beta_1 \mid \ldots \mid \beta_n$

Алгоритм завершится, когда в грамматике не будет правого ветвления. Он отработает конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным.

Замечание: отсутствие левой рекурсии и правого ветвления в грамматике не является достаточным условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.

См. также

• Нормальная форма Хомского
• Существенно неоднозначные языки

Источники информации

• Wikipedia — LL grammar
• LL(k)-грамматики и трансляция
• Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. ISBN 5-8459-0189-8