Изменения
→Алгоритм устранения правого ветвленения: s/необходимым/достаточным/
}}
Другими словами, <tex> \mathrm{FIRST}(\alpha) </tex> {{---}} все символы (терминалы), с которых могут начинаться всевозможные выводы из <tex> \alpha </tex>, а <tex> \mathrm{FOLLOW}(A) </tex> {{---}} всевозможные символы, которые встречаются после нетерминала <tex> A </tex> во всех [[Удаление бесполезных символов из грамматики | небесполезных]] правилах грамматики.
'''Замечание:''' более общим случаем множества <tex> \mathrm{FIRST} </tex> является множество <tex> \mathrm{FIRST}_k </tex>, однако в данном конспекте оно не используется.
{{Определение
|id=deffirstk
|definition=
<tex> \mathrm{FIRST}_k(\alpha) = \{w \mid \alpha \Rightarrow^* w \beta,\ |w| \leqslant k \} \cup \{ \varepsilon\ \mathrm{if}\ \alpha \Rightarrow^* \varepsilon \} </tex>
}}
=== Примеры ===
Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.
!style="background-color:#EEE"| FOLLOW
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>A</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex>
|style="background-color:#FFF;padding:2px 40px"| <tex>\{\ ),\ \$\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>B</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ ),\ \$\ \} </tex>
<tex> A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m </tex>
Причём <tex> \alpha \ne \varepsilon </tex>, а наибольший общий префикс <tex> \alpha </tex> и <tex> \gamma_i,\ (1 \leqslant i \leqslant m</tex> ) равен <tex> \varepsilon </tex>. Тогда изменим грамматику следующим образом, введя новый нетерминал <tex> A' </tex>:
<tex> A \to \alpha A' \mid \gamma_1 \mid \ldots \mid \gamma_m </tex>
Алгоритм завершится, когда в грамматике не будет правого ветвления. Он отработает конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным.
'''Замечание:''' отсутствие левой рекурсии и правого ветвления в грамматике не является необходимым достаточным условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.
== См. также ==
