1632
правки
Изменения
м
rollbackEdits.php mass rollback
|id=deffirst
|definition=
<tex> \mathrm{FIRST}(\alphaA) = \{c \mid \alpha A \Rightarrow^* c \beta \} \cup \{ \varepsilon\ \mathrm{if}\ \alpha A \Rightarrow^* \varepsilon \} </tex>
}}
{{Определение
<tex> \mathrm{FOLLOW}(A) = \{c \mid S \Rightarrow^* \alpha A c \beta \} \cup \{ \$ \ \mathrm{if}\ S \Rightarrow^* \alpha A \} </tex>
}}
Другими словами, <tex> \mathrm{FIRST}(\alphaA) </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(A) = \{w \mid A \Rightarrow^* w \beta,\ |w| \leqslant k \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \} </tex> }}
=== Примеры ===
Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.
<tex> \Rightarrow </tex>
Предположим, что есть два различных правила <tex> A \to \alpha </tex> и <tex> A \to \beta </tex> таких, что <tex> c \in \mathrm{FIRST}(\alphaA) \cap \mathrm{FIRST}(\beta) </tex>. Тогда:
* <tex> S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma </tex>
* <tex> S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma </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)-грамматикой.
== См. также ==
