Построение FIRST и FOLLOW

2014-09-11T12:02:08Z

89.113.128.32: /* Пример */

Для данной [[LL(k)-грамматики, множества FIRST и FOLLOW#defLLK | LL(1)-грамматики]] оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator] </ref>.

Чтобы написать парсер для LL(1)-грамматики, необходимо построить [[LL(k)-грамматики, множества FIRST и FOLLOW#deffirst | множества]] <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex>, после чего по ним можно составить таблицу синтаксического анализатора.
== Построение FIRST ==
Для построения <tex> \mathrm{FIRST} </tex> воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть <tex> \alpha, \beta </tex> {{---}} цепочки из терминалов и нетерминалов, <tex> c </tex> {{---}} символ из алфавита.
{{Лемма
|id=lemmafirst1
|author=1
|statement=<tex> \mathrm{FIRST}(\alpha \beta) = \mathrm{FIRST}(\alpha) \cup (\mathrm{FIRST}(\beta)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha)) </tex>
}}
Рассмотрим лемму подробней. Пусть правило из нетерминала <tex> A </tex> имеет вид <tex> A \to X_1 X_2 \dots X_k </tex>, где <tex> X_i,\ (1 \leqslant i \leqslant k) </tex> {{---}} произвольный терминал или нетерминал. Тогда по лемме в <tex> \mathrm{FIRST}[A] </tex> нужно добавить <tex> \mathrm{FIRST}(X_i) </tex>, если для всех <tex> 1 \leqslant j < i </tex> верно, что <tex> X_j \Rightarrow^* \varepsilon </tex>.
{{Лемма
|id=lemmafirst2
|author=2
|statement=
<tex> \mathrm{FIRST}(c \alpha) = \{c\}</tex> <br>
<tex> \mathrm{FIRST}(\varepsilon) = \{\varepsilon \}</tex>
}}
=== Псевдокод ===
Алгоритм строит для каждого терминала грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> отображение в множество символов. Перед запуском алгоритма необходимо избавиться от [[Удаление бесполезных символов из грамматики | бесполезных символов]]. Изначально каждое правило отображается в пустое множество.
<code>
'''function''' constructFIRST():
'''for''' <tex>( A \in N )</tex>
<tex>\mathrm{FIRST}[A] = \varnothing </tex>
changed = ''true''
'''while''' changed
changed = ''false''
'''for''' <tex>( A \to \alpha \in P )</tex>
<tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex>
changed = ''true'' '''if''' <tex> \mathrm{FIRST}[A] </tex> изменился
</code>
{{Утверждение
|id=proposalfirstcorrect
|statement=Приведённый алгоритм правильно строит множество <tex> \mathrm{FIRST} </tex> для данной грамматики.
|proof=

<tex> \Leftarrow </tex>

Алгоритм на каждом шаге использует [[#lemmafirst1 | леммы]], чтобы построить списки <tex> \mathrm{FIRST} </tex> для каждого нетерминала. Поэтому он добавит только те терминалы, которые на самом деле лежат в <tex> \mathrm{FIRST} </tex>.

<tex> \Rightarrow </tex>

Покажем, что алгоритм найдёт все символы из множества <tex> \mathrm{FIRST} </tex>.

Предположим, что в грамматике возможен вывод <tex> A \Rightarrow^* c \gamma </tex>, и алгоритм не включил <tex> c </tex> в <tex> \mathrm{FIRST}[A] </tex>. Докажем индукцией по числу шагов <tex> \mathrm{while} </tex>, что этого не может быть.

Пусть за <tex> k </tex> шагов алгоритм добавит символы <tex> c </tex> в множество <tex> \mathrm{FIRST} </tex> для каждого нетерминала <tex> A </tex>, если <tex> A \Rightarrow^k c \gamma </tex>. База индукции для числа шагов <tex> 0 </tex> верна, если считать, что для всех терминалов нам известны <tex> \mathrm{FIRST} </tex>. Если алгоритм корректно отрабатывает на <tex>(k-1)</tex>-ом шаге, то он правильно отработает их на <tex>k</tex>-ом шаге, потому что

<tex> A \Rightarrow \beta \Rightarrow^{k-1} c \gamma </tex>

Для <tex> \beta </tex> алгоритм правильно построил <tex> \mathrm{FIRST} </tex> по предположению индукции, а для <tex> A </tex> он правильно построит по [[#lemmafirst1 | леммам]], следовательно, переход доказан.

К тому же, алгоритм завершится за конечное число шагов, так как в <tex> \mathrm{FIRST} </tex> для каждого нетерминала не может добавиться больше символов, чем есть в алфавите.
}}

== Построение FOLLOW ==
Сформулируем похожие утверждения для построения <tex> \mathrm{FOLLOW} </tex>.
{{Лемма
|id=lemmafollow1
|author=3
|statement=Для каждого правила <tex> A \to \alpha B \beta </tex> верно, что <tex>(\mathrm{FIRST}(\beta) \setminus \{\varepsilon\}) \subset \mathrm{FOLLOW}(B) </tex>
}}
{{Лемма
|id=lemmafollow2
|author=4
|statement=Для каждого правила вида <tex> A \to \alpha B </tex> или <tex> A \to \alpha B \beta,\ \varepsilon \in \mathrm{FIRST}(\beta)</tex> верно, что <tex>\mathrm{FOLLOW}(A) \subset \mathrm{FOLLOW}(B) </tex>
}}
=== Псевдокод ===
Реализация построения <tex> \mathrm{FOLLOW} </tex> получается сразу из [[#lemmafollow1 | лемм]]. Для алгоритма сначала требуется выполнить построение <tex> \mathrm{FIRST} </tex> для грамматики.
<code>
'''function''' constructFOLLOW():
'''for''' <tex>( A \in N )</tex>
<tex>\mathrm{FOLLOW}[A] = \varnothing </tex>
<tex>\mathrm{FOLLOW}[S] = \{\$\} </tex> <font color=green> // в стартовый терминал помещается символ конца строки </font>
changed = ''true''
'''while''' changed
changed = ''false''
'''for''' <tex>( A \to \alpha \in P )</tex>
'''for''' <tex>( B : \alpha = \beta B \gamma)</tex>
<tex> \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FIRST}(\gamma) \setminus \{\varepsilon\} </tex>
'''if''' <tex> \varepsilon \in \mathrm{FIRST}(\gamma) </tex>
<tex> \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FOLLOW}[A]</tex>
changed = ''true'' '''if''' <tex> \mathrm{FOLLOW}[B] </tex> изменился
</code>
Корректность данного алгоритма доказывается точно так же, как и корректность алгоритма конструирования <tex> \mathrm{FIRST} </tex>.

== Пример ==
Рассмотрим, как будут строиться множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> на примере грамматики арифметических выражений. Ограничимся только операциями сложения, умножения и наличием скобок. Числа будем обозначать одной буквой <tex> n </tex> для простоты. Интуитивная грамматика для арифметических выражений выглядит следующим образом:

<tex> E \to E + E \mid E \times E \mid (E) \mid n </tex>

Однако данная грамматика содержит [[Устранение левой рекурсии | левую рекурсию]], [[LL(k)-грамматики, множества FIRST и FOLLOW#Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW | правое ветвление]] и является [[Существенно неоднозначные языки#defambigous |неоднозначной]]. Чтобы избавиться от данных проблем неявно, можно придумать более удачную грамматику для рассматриваемого языка. Например, она может иметь следующий вид:

<tex>
E \to T + E \mid T \\
T \to F \times T \mid F \\
F \to n \mid (E)
</tex>

Данная грамматика содержит только правое ветвление, от которого можно избавиться левой факторизацией, после чего грамматика примет вид:

<tex>
E \to TE' \\
E' \to +E \mid \varepsilon \\
T \to FT' \\
T' \to \times T \mid \varepsilon \\
F \to n \mid (E)
</tex>

А затем для простоты анализирования раскрыть нетерминалы <tex> E </tex> и <tex> T </tex> в правилах для <tex> E' </tex> и <tex> T' </tex>.

<tex>
E \to TE' \\
E' \to +TE' \mid \varepsilon \\
T \to FT' \\
T' \to \times FT' \mid \varepsilon \\
F \to n \mid (E)
</tex>

=== Конструирование FIRST для арифметических выражений ===
Рассмотрим, как будет выглядеть множество <tex> \mathrm{FIRST} </tex> после очередной итераций цикла <tex> \mathrm{while} </tex>.

'''После 1ой итерации:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FIRST
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \varepsilon\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|}
'''После 2ой итерации:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FIRST
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \varepsilon\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|}
'''После 3eй итерации:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FIRST
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \varepsilon\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|}
Далее никаких изменений происходить не будет, и на этом алгоритм завершит свою работу.
=== Конструирование FOLLOW для арифметических выражений ===
Теперь рассмотрим построение таблицы <tex> \mathrm{FOLLOW} </tex> после каждой итераций цикла <tex> \mathrm{while} </tex>. Стартовым нетерминалом будет <tex> E </tex>, поэтому в него добавим сразу <tex> \$ </tex>.

'''До цикла while:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FOLLOW
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$ \ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
|}
'''После 1ой итерации:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FOLLOW
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$ \ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ \} </tex>
|}
'''После 2ой итерации:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FOLLOW
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ \} </tex>
|}
'''После 3ей итерации:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FOLLOW
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ ,\ )\ \} </tex>
|}
На этом построение множества <tex> \mathrm{FOLLOW} </tex> для грамматики закончится.

=== Итоговая таблица ===
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FIRST
!style="background-color:#EEE"| FOLLOW
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \varepsilon\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ ,\ )\ \} </tex>
|}

Используя [[LL(k)-грамматики, множества FIRST и FOLLOW#Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW | теорему]], можно убедиться, что грамматика арифметических выражений на самом деле является LL(1)-грамматикой.

== См. также ==
* [[LL(k)-грамматики, множества FIRST и FOLLOW]]
== Примечания ==
<references/>
== Источники информации ==
* [http://en.wikipedia.org/wiki/LL_parser Wikipedia {{---}} LL parser]
* [http://citforum.ru/programming/theory/serebryakov/4.shtml СitForum {{---}} Синтаксический анализ]
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. ISBN 5-8459-0189-8

[[Категория: Методы трансляции]]
[[Категория: Нисходящий разбор]]

Викиконспекты - Вклад участника [ru]

Построение FIRST и FOLLOW