3622
правки
Изменения
→Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW: добавлено доказательство
# <tex> A \to \alpha,\ A \to \beta, A \in N,\ \varepsilon \in \mathrm{FIRST}(\alpha) \ \Rightarrow \ \mathrm{FOLLOW}(A) \cap \mathrm{FIRST}(\beta) = \varnothing</tex>
|proof=
<tex> \Leftarrow </tex> Предположим, что данная грамматика не будет LL(1)-грамматикой. Значит, у какого-то слова <tex> w </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> \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing </tex>. Аналогично проверятся второе условие. Если, например, <tex> \alpha \Rightarrow^* \varepsilon </tex>, то <tex> \varepsilon \in \mathrm{FIRST}(\alpha) </tex>, и <tex> \mathrm{FOLLOW}(A) \cap \mathrm{FIRST}(\beta) \ne \varnothing </tex> <tex> \Rightarrow </tex> Предположим, что есть два различных правила <tex> A \to \alpha </tex> и <tex> A \to \beta </tex> таких, что <tex> c \in \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\Leftarrow 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> c </tex> лежит в пересечении множеств <tex> \mathrm{FIRST} </tex> двух правил вывода. Так как грамматика <tex> \Gamma </tex>является LL(1)-грамматикой, то из [[#defLLK | определения]] следует, что <tex> \alpha = \beta </tex>. Это противоречит предположению, что <tex> \alpha </tex> и <tex> \beta </tex> {{---}} различные правила. почти очевидноВторое условие проверяется аналогичным образом.
}}
=== Следствия ===
