Изменения
→Псевдокод
}}
=== Псевдокод ===
Алгоритм строит для каждого терминала нетерминала грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> отображение в множество символов. Перед запуском алгоритма необходимо избавиться от [[Удаление бесполезных символов из грамматики | бесполезных символов]]. Изначально каждое правило отображается в пустое множество.<code> '''function''' constructFIRST():
'''for''' <tex>( A \in N )</tex>
<tex>\mathrm{FIRST}[A] = \varnothing </tex>
<tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex>
changed = ''true'' '''if''' <tex> \mathrm{FIRST}[A] </tex> изменился
{{Утверждение
|id=proposalfirstcorrect
=== Псевдокод ===
Реализация построения <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>
