}}
===== Алгоритм устранения правого ветвленения =====
Чтобы избавиться от правого ветвления, нужно воспользоваться алгоритмом левой факторизации. Его суть заключается в следующем: для каждого нетерминала <tex> A </tex> ищем самый длинный префикс, общий для двух или более правил вывода из <tex> A </tex>. Важно, чтобы как можно больше строк имело общий префикс, и можно было вынести части правил после общего префикса в отдельный нетерминал. Более формально, рассмотрим правила
<tex> A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m </tex>
Однако Причём <tex> \alpha \ne \varepsilon </tex>, а наибольший общий префикс <tex> \alpha </tex> и <tex> \gamma_i,\ 1 \leqslant i \leqslant m</tex> равен <tex> \varepsilon </tex>. Тогда изменим грамматику следующим образом, введя новый нетерминал <tex> A' </tex>: <tex> A \to \alpha A' \mid \gamma_1 \mid \ldots \mid \gamma_m </tex> <tex> A' \to \beta_1 \mid \ldots \mid \beta_n </tex> Алгоритм завершится, когда в грамматике не будет правого ветвления. Он завершится за конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным. '''Замечание:''' отсутствие левой рекурсии и правого ветвления в грамматике не является необходимым условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.
== См. также ==
