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(\alphaA) = \{w \mid \alpha A \Rightarrow^* w \beta,\ |w| \leqslant k \} \cup \{ \varepsilon\ \mathrm{if}\ \alpha A \Rightarrow^* \varepsilon \} </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>
