3622
правки
Изменения
→Алгоритм устранения правого ветвленения
<tex> A' \to \beta_1 \mid \ldots \mid \beta_n </tex>
Алгоритм завершится, когда в грамматике не будет правого ветвления. Он завершится за отработает конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным.
'''Замечание:''' отсутствие левой рекурсии и правого ветвления в грамматике не является необходимым условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.
