3622
правки
Изменения
добавлен псевдокод FOLLOW
changed = ''true''
'''while''' changed
changed = ''truefalse''
'''for''' <tex>( A \to \alpha \in P )</tex>
<tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex>
|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>.
== Пример ==
== См. также ==
