1632
правки
Изменения
м
{{В разработке}}
Данная лемма означает, что в множество Рассмотрим лемму подробней. Пусть правило из нетерминала <tex> \mathrm{FIRST} 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>.
<code> '''function''' constructFOLLOW():
</code>
rollbackEdits.php mass rollback
Для данной [[LL(k)-грамматики, множества FIRST и FOLLOW#defLLK | LL(1)-грамматики]] оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator] </ref>.
|statement=<tex> \mathrm{FIRST}(\alpha \beta) = \mathrm{FIRST}(\alpha) \cup (\mathrm{FIRST}(\beta)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha)) </tex>
}}
{{Лемма
|id=lemmafirst2
}}
=== Псевдокод ===
Алгоритм строит для каждого терминала нетерминала грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> отображение в множество символов. Перед запуском алгоритма необходимо избавиться от [[Удаление бесполезных символов из грамматики | бесполезных символов]]. Изначально каждое правило отображается в пустое множество.<code> '''function''' constructFIRST():
'''for''' <tex>( A \in N )</tex>
<tex>\mathrm{FIRST}[A] = \varnothing </tex>
'''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
Для <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>
}}
{{Лемма
=== Псевдокод ===
Реализация построения <tex> \mathrm{FOLLOW} </tex> получается сразу из [[#lemmafollow1 | лемм]]. Для алгоритма сначала требуется выполнить построение <tex> \mathrm{FIRST} </tex> для грамматики.
'''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
<tex> \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FOLLOW}[A]</tex>
changed = ''true'' '''if''' <tex> \mathrm{FOLLOW}[B] </tex> изменился
Корректность данного алгоритма доказывается точно так же, как и корректность алгоритма конструирования <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>
</tex>
Данная грамматика содержит только правое ветвление, от которого можно избавиться левой факторизацией, после чего грамматика пример примет вид:
<tex>
=== Конструирование FOLLOW для арифметических выражений ===
Теперь рассмотрим построение таблицы <tex> \mathrm{FOLLOW} </tex> после каждой итераций цикла <tex> \mathrm{while} </tex>. Стартовым нетерминалом будет <tex> E </tex>, поэтому в него добавим сразу <tex> \$ </tex>.
'''До цикла while:'''
{| style="background-color:#CCC;margin:0.5px"
|}
На этом построение множества <tex> \mathrm{FOLLOW} </tex> для грамматики закончится.
=== Итоговая таблица ===
{| style="background-color:#CCC;margin:0.5px"
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ ,\ )\ \} </tex>
|}
Используя [[LL(k)-грамматики, множества FIRST и FOLLOW#Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW | теорему]], можно убедиться, что грамматика арифметических выражений на самом деле является LL(1)-грамматикой.
== См. также ==
