Для данной LL(1)-грамматики оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик[1].
Чтобы написать парсер для LL(1)-грамматики, необходимо построить множества [math] \mathrm{FIRST} [/math] и [math] \mathrm{FOLLOW} [/math], после чего по ним можно составить таблицу синтаксического анализатора.
Для построения [math] \mathrm{FIRST} [/math] воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть [math] \alpha, \beta [/math] — цепочки из терминалов и нетерминалов, [math] c [/math] — символ из алфавита.
| Лемма (1): |
[math] \mathrm{FIRST}(\alpha \beta) = \mathrm{FIRST}(\alpha) \cup (\mathrm{FIRST}(\beta)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha)) [/math] |
Данная лемма означает, что в множество [math] \mathrm{FIRST} [/math] правила [math] A \to X_1 X_2 \dots X_k [/math], где [math] X_i,\ (1 \leqslant i \leqslant k) [/math] — произвольный терминал или нетерминал, — нужно добавить [math] \mathrm{FIRST}(X_i) [/math], если для всех [math] 1 \leqslant j \lt i [/math] верно, что [math] X_j \Rightarrow^* \varepsilon [/math].
| Лемма (2): |
[math] \mathrm{FIRST}(c \alpha) = \{c\}[/math]
[math] \mathrm{FIRST}(\varepsilon) = \{\varepsilon \}[/math] |
Псевдокод
Алгоритм строит для каждого терминала грамматики [math]\Gamma = \langle \Sigma, N, S, P \rangle[/math] отображение в множество символов. Перед запуском алгоритма необходимо избавиться от бесполезных символов. Изначально каждое правило отображается в пустое множество.
function constructFIRST():
for [math]( A \in N )[/math]
[math]\mathrm{FIRST}[A] = \varnothing [/math]
changed = true
while changed
changed = false
for [math]( A \to \alpha \in P )[/math]
[math] \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) [/math]
changed = true if [math] \mathrm{FIRST}[A] [/math] изменился
| Утверждение: |
Приведённый алгоритм правильно строит множество [math] \mathrm{FIRST} [/math] для данной грамматики. |
| [math]\triangleright[/math] |
|
[math] \Leftarrow [/math]
Алгоритм на каждом шаге использует леммы, чтобы построить списки [math] \mathrm{FIRST} [/math] для каждого нетерминала. Поэтому он добавит только те терминалы, которые на самом деле лежат в [math] \mathrm{FIRST} [/math].
[math] \Rightarrow [/math]
Покажем, что алгоритм найдёт все символы из множества [math] \mathrm{FIRST} [/math].
Предположим, что в грамматике возможен вывод [math] A \Rightarrow^* c \gamma [/math], и алгоритм не включил [math] c [/math] в [math] \mathrm{FIRST}[A] [/math]. Докажем индукцией по числу шагов [math] \mathrm{while} [/math], что этого не может быть.
Пусть за [math] k [/math] шагов алгоритм добавит символы [math] c [/math] в множество [math] \mathrm{FIRST} [/math] для каждого нетерминала [math] A [/math], если [math] A \Rightarrow^k c \gamma [/math]. База индукции для числа шагов [math] 0 [/math] верна, если считать, что для всех терминалов нам известны [math] \mathrm{FIRST} [/math]. Если алгоритм корректно отрабатывает на [math](k-1)[/math]-ом шаге, то он правильно отработает их на [math]k[/math]-ом шаге, потому что
[math] A \Rightarrow \beta \Rightarrow^{k-1} c \gamma [/math]
Для [math] \beta [/math] алгоритм правильно построил [math] \mathrm{FIRST} [/math] по предположению индукции, а для [math] A [/math] он правильно построит по леммам, следовательно, переход доказан.
К тому же, алгоритм завершится за конечное число шагов, так как в [math] \mathrm{FIRST} [/math] для каждого нетерминала не может добавиться больше символов, чем есть в алфавите. |
| [math]\triangleleft[/math] |
Построение FOLLOW
Сформулируем похожие утверждения для построения [math] \mathrm{FOLLOW} [/math].
| Лемма (3): |
Для каждого правила [math] A \to \alpha B \beta [/math] верно, что [math](\mathrm{FIRST}(\beta) \setminus \{\varepsilon\}) \subset \mathrm{FOLLOW}(B) [/math] |
| Лемма (4): |
Для каждого правила вида [math] A \to \alpha B [/math] или [math] A \to \alpha B \beta,\ \varepsilon \in \mathrm{FIRST}(\beta)[/math] верно, что [math]\mathrm{FOLLOW}(A) \subset \mathrm{FOLLOW}(B) [/math] |
Псевдокод
Реализация построения [math] \mathrm{FOLLOW} [/math] получается сразу из лемм. Для алгоритма сначала требуется выполнить построение [math] \mathrm{FIRST} [/math] для грамматики.
function constructFOLLOW():
for [math]( A \in N )[/math]
[math]\mathrm{FOLLOW}[A] = \varnothing [/math]
[math]\mathrm{FOLLOW}[S] = \{\$\} [/math] // в стартовый терминал помещается символ конца строки
changed = true
while changed
changed = false
for [math]( A \to \alpha \in P )[/math]
for [math]( B : \alpha = \beta B \gamma)[/math]
[math] \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FIRST}(\gamma) \setminus \{\varepsilon\} [/math]
if [math] \varepsilon \in \mathrm{FIRST}(\gamma) [/math]
[math] \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FOLLOW}[A][/math]
changed = true if [math] \mathrm{FOLLOW}[B] [/math] изменился
Корректность данного алгоритма доказывается точно так же, как и корректность алгоритма конструирования [math] \mathrm{FIRST} [/math].
Пример
Рассмотрим, как будут строиться множества [math] \mathrm{FIRST} [/math] и [math] \mathrm{FOLLOW} [/math] на примере грамматики арифметических выражений. Ограничимся только операциями сложения, умножения и наличием скобок. Числа будем обозначать одной буквой [math] n [/math] для простоты. Интуитивная грамматики для арифметических выражений выглядит следующим образом:
[math] E \to E + E \mid E \times E \mid (E) \mid n [/math]
Однако данная грамматика содержит левую рекурсию, правое ветвление и является неоднозначной. Чтобы избавиться от данных проблем неявно, можно придумать более удачную грамматику для рассматриваемого языка. Например, она может иметь следующий вид:
[math]
E \to T + E \mid T \\
T \to F \times T \mid F \\
F \to n \mid (E)
[/math]
Данная грамматика содержит только правое ветвление, от которого можно избавиться левой факторизацией, после чего грамматика пример вид:
[math]
E \to TE' \\
E' \to +E \mid \varepsilon \\
T \to FT' \\
T' \to \times T \mid \varepsilon \\
F \to n \mid (E)
[/math]
А затем для простоты анализирования раскрыть нетерминалы [math] E [/math] и [math] T [/math] в правилах для [math] E' [/math] и [math] T' [/math].
[math]
E \to TE' \\
E' \to +TE' \mid \varepsilon \\
T \to FT' \\
T' \to \times FT' \mid \varepsilon \\
F \to n \mid (E)
[/math]
Конструирование FIRST для арифметических выражений
Рассмотрим, как будет выглядеть множество [math] \mathrm{FIRST} [/math] после очередной итераций цикла [math] \mathrm{while} [/math].
После 1ой итерации:
| Правило
|
FIRST
|
| [math]E[/math]
|
[math]\{\ \} [/math]
|
| [math]E'[/math]
|
[math]\{\ +,\ \varepsilon\ \} [/math]
|
| [math]T[/math]
|
[math]\{\ \}[/math]
|
| [math]T'[/math]
|
[math]\{\ \times,\ \varepsilon\ \} [/math]
|
| [math]F[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
После 2ой итерации:
| Правило
|
FIRST
|
| [math]E[/math]
|
[math]\{\ \} [/math]
|
| [math]E'[/math]
|
[math]\{\ +,\ \varepsilon\ \} [/math]
|
| [math]T[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
| [math]T'[/math]
|
[math]\{\ \times,\ \varepsilon\ \} [/math]
|
| [math]F[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
После 3eй итерации:
| Правило
|
FIRST
|
| [math]E[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
| [math]E'[/math]
|
[math]\{\ +,\ \varepsilon\ \} [/math]
|
| [math]T[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
| [math]T'[/math]
|
[math]\{\ \times,\ \varepsilon\ \} [/math]
|
| [math]F[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
Далее никаких изменений происходить не будет, и на этом алгоритм завершит свою работу.
Конструирование FOLLOW для арифметических выражений
Теперь рассмотрим построение таблицы [math] \mathrm{FOLLOW} [/math] после каждой итераций цикла [math] \mathrm{while} [/math]. Стартовым нетерминалом будет [math] E [/math], поэтому в него добавим сразу [math] \$ [/math].
До цикла while:
| Правило
|
FOLLOW
|
| [math]E[/math]
|
[math]\{\ \$ \ \} [/math]
|
| [math]E'[/math]
|
[math]\{\ \}[/math]
|
| [math]T[/math]
|
[math]\{\ \}[/math]
|
| [math]T'[/math]
|
[math]\{\ \}[/math]
|
| [math]F[/math]
|
[math]\{\ \}[/math]
|
После 1ой итерации:
| Правило
|
FOLLOW
|
| [math]E[/math]
|
[math]\{\ \$,\ )\ \} [/math]
|
| [math]E'[/math]
|
[math]\{\ \$ \ \} [/math]
|
| [math]T[/math]
|
[math]\{\ +,\ \$\ \}[/math]
|
| [math]T'[/math]
|
[math]\{\ +,\ \$\ \}[/math]
|
| [math]F[/math]
|
[math]\{\ \times, \ +,\ \$\ \} [/math]
|
После 2ой итерации:
| Правило
|
FOLLOW
|
| [math]E[/math]
|
[math]\{\ \$,\ )\ \} [/math]
|
| [math]E'[/math]
|
[math]\{\ \$,\ )\ \} [/math]
|
| [math]T[/math]
|
[math]\{\ +,\ \$\ \}[/math]
|
| [math]T'[/math]
|
[math]\{\ +,\ \$\ \}[/math]
|
| [math]F[/math]
|
[math]\{\ \times, \ +,\ \$\ \} [/math]
|
После 3ей итерации:
| Правило
|
FOLLOW
|
| [math]E[/math]
|
[math]\{\ \$,\ )\ \} [/math]
|
| [math]E'[/math]
|
[math]\{\ \$,\ )\ \} [/math]
|
| [math]T[/math]
|
[math]\{\ +,\ \$\ ,\ )\ \}[/math]
|
| [math]T'[/math]
|
[math]\{\ +,\ \$\ ,\ )\ \}[/math]
|
| [math]F[/math]
|
[math]\{\ \times, \ +,\ \$\ ,\ )\ \} [/math]
|
На этом построение множества [math] \mathrm{FOLLOW} [/math] для грамматики закончится.
Итоговая таблица
| Правило
|
FIRST
|
FOLLOW
|
| [math]E[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
[math]\{\ \$,\ )\ \} [/math]
|
| [math]E'[/math]
|
[math]\{\ +,\ \varepsilon\ \} [/math]
|
[math]\{\ \$,\ )\ \} [/math]
|
| [math]T[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
[math]\{\ +,\ \$\ ,\ )\ \}[/math]
|
| [math]T'[/math]
|
[math]\{\ \times,\ \varepsilon\ \} [/math]
|
[math]\{\ +,\ \$\ ,\ )\ \}[/math]
|
| [math]F[/math]
|
[math]\{\ n,\ (\ \} [/math]
|
[math]\{\ \times, \ +,\ \$\ ,\ )\ \} [/math]
|
См. такжеПримечанияИсточники информации