<aside> 📌 $A \to \alpha\beta_1 | \alpha\beta_2 … | \alpha\beta_n$ Эквивалентна $A \to \alpha Q$ $Q \to \beta_1 | … | \beta_n$
</aside>
#Пример
$A \to BAC|BAd |B$
$A \to BQ$
$Q \to Aa | Ad | \varepsilon$
$A \to BQ$
$Q \to AR|\varepsilon$
$R \to a|d$
Суть алгоритма заключается в следующем: для каждого нетерминала $A$ ищем самый длинный префикс, общий для двух или более правил вывода из $A$. Важно, чтобы как можно больше строк имело общий префикс и можно было вынести части правил после общего префикса в отдельный нетерминал. Более формально:
$A \to \alpha \beta_1| … | \alpha \beta_n | \gamma_1 | … | \gamma_m$
Причем $\alpha \not = \varepsilon$, а наибольший общий префикс $\alpha$ и $\gamma_i$ $(1 ≤ i ≤ m)$ равен $\varepsilon$. Тогда изменим грамматику слудующим образом, введя новый нетерминал $Q$.
$A \to \alpha Q | \gamma_1 | … | \gamma_m$
$Q \to \beta_1| … | \beta_n$
Алгоритм завершится, когда в грамматике не будет правого ветвления. Он работает конечное число шагов, так как каждый раз длина правой части правил уменьшается хотя бы на единицу, а тривиальные префиксы мы не рассматриваем.