3622
правки
Изменения
добавлены два следствия
* <tex> S \Rightarrow^* p A \beta \Rightarrow p \alpha \beta \Rightarrow^* p y \eta </tex>
* <tex> S \Rightarrow^* p A \beta \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi </tex>
где <tex> p </tex> и <tex> y </tex> {{---}} цепочки из терминалов, уже разобранная часть слова <tex> w </tex>, <tex> A </tex> {{---}} нетерминал грамматики, в которой есть правила <tex> A \rightarrow to \alpha </tex> и <tex> A \rightarrow to \alpha' </tex>, причём <tex> \alpha, \alpha', \beta, \eta, \xi </tex> {{---}} последовательности из терминалов и нетерминалов.<br>
Тогда если при выполнении условий, что <tex> |y| = k </tex> или <tex> |y| < k, \eta = \xi = \varepsilon </tex>, верно, что <tex> \alpha = \alpha' </tex>, то <tex> \Gamma </tex> называется '''LL(k)-грамматикой'''.
}}
Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.
* <tex> A \rightarrow to (A)A \mid \varepsilon </tex>* <tex> B \rightarrow to BB \mid (B) \mid \varepsilon </tex>
{| style="background-color:#CCC;margin:0.5px"
|id=thLL1
|statement= <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} LL(1)-грамматика <tex> \Leftrightarrow </tex>
# <tex> A \rightarrow to \alpha,\ A \rightarrow to \beta, A \in N \ \Rightarrow \ \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing</tex># <tex> A \rightarrow to \alpha,\ A \rightarrow to \beta, A \in N,\ \varepsilon \in \mathrm{FIRST}(\alpha) \ \Rightarrow \ \mathrm{FOLLOW}(A) \cap \mathrm{FIRST}(\beta) = \varnothing</tex>
|proof=
* <tex> \Leftarrow </tex>
}}
=== Следствия ===
Сформулируем несколько важных cледствий из теоремы.
==== Левая рекурсия ====
{{Утверждение
|author=1
|statement=Грамматика <tex> \Gamma </tex> cодержит левую рекурсию <tex> \Rightarrow \ \Gamma </tex> не является LL(1)-грамматикой.
|proof=
Если грамматика содержит левую рекурсию, значит, в ней существует какой-то нетерминал <tex> A </tex> с правилами <tex> A \to A \alpha \mid \beta </tex>, где <tex> \beta </tex> {{---}} строка из терминалов и нетерминалов, не начинающаяся с <tex> A </tex>.
Тогда понятно, что <tex> \mathrm{FIRST}(A\alpha) \cap \mathrm{FIRST}(\beta) \ne \varnothing </tex>, и это противоречит первому условию [[#thLL1 | теоремы]].
}}
Чтобы избавиться от левой рекурсии, можно воспользоваться [[Устранение левой рекурсии | алгоритмом устранения левой рекурсии]].
==== Левая факторизация ====
{{Утверждение
|author=2
|statement=Грамматика <tex> \Gamma </tex> cодержит правое ветвление <tex> \Rightarrow \ \Gamma </tex> не является LL(1)-грамматикой.
|proof=
Наличие в грамматике правого ветвления означает, что существует правило <tex> A \to \alpha \beta \mid \alpha \gamma </tex>.
Очевидно, что <tex> \mathrm{FIRST}(\alpha \beta) \cap \mathrm{FIRST}(\alpha \gamma) \ne \varnothing </tex>. Поэтому грамматика не будет LL(1)-грамматикой по первому условию [[#thLL1 | теоремы]].
}}
===== Алгоритм устранения правого ветвленения =====
<tex> A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m </tex>
Однако отсутствие левой рекурсии и правого ветвления в грамматике не является необходимым условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.
== См. также ==
== Источники информации ==
