Изменения

Для построения <tex> \mathrm{FIRST} </tex> воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть <tex> \alpha, \beta </tex> {{---}} цепочки из терминалов и нетерминалов, <tex> c </tex> {{---}} символ из алфавита.

{{Лемма

|author=1

|statement=<tex> \mathrm{FIRST}(\alpha \beta) = \mathrm{FIRST}(\alpha) \cup (\mathrm{FIRST}(\beta)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha)) </tex>

Данная лемма означает, что в множество <tex> \mathrm{FIRST} </tex> правила <tex> A \to X_1 X_2 \dots X_k </tex>, где <tex> X_i,\ (1 \leqslant i \leqslant k) </tex> {{---}} произвольный терминал или нетерминал, {{---}} нужно добавить <tex> \mathrm{FIRST}(X_i) </tex>, если для всех <tex> 1 \leqslant j < i </tex> верно, что <tex> X_j \Rightarrow^* \varepsilon </tex>.

{{Лемма

|author=2

|statement=

</code>

{{Утверждение

|statement=Приведённый алгоритм правильно строит множество <tex> \mathrm{FIRST} </tex> для данной грамматики.

|proof=

}}

== Построение FOLLOW ==

== См. также ==

== Примечания ==