Определение
<aside> 📌 $G = (\Sigma, Г, P, S) -$ контекстносвободная грамматика $A \to A\alpha \in P$, в грамматике $G$ есть непосредственная левая рекурсия
</aside>
Пример такой граммтки:
$S \to S + A|A$ $A \to A * B|B$ $B \to x|(S)$
<aside> 📌 Пусть $A \to A \alpha_1|…|A\alpha_n$ и $A \to \beta_1|…|\beta_k$ - набор правил грамматики $[$обозначим как: $()]$ Тогда $A \to \beta_1A'|...|\beta_kA'$ и $A' \to \alpha_1A'|...|\alpha_nA'|\varepsilon$ $[$обозначим как: $(**)$$]$ эквивалентна $()$.
</aside>
Доказательство:
$()$ $A \rArr A\alpha_{i_1} \rArr A\alpha_{i_2}\alpha_{i_1} \rArr^ A\alpha_{i_m} ... \alpha_{i_2}\alpha_{i_1}$ $\rArr \beta_j\alpha_{i_m}...\alpha_{i_2}\alpha_{i_1}$
$(**)$ $A \rArr \beta_jA' \rArr^* \beta_j\alpha_{i_m} ... \alpha_{i_2}\alpha_{i_1}A'$ $\rArr \beta_j\alpha_{i_m}...\alpha_{i_2}\alpha_{i_1}$
$S \to S + A|A$ $A \to A * B|B$ $B \to x|(S)$
$S \to S + A| A$
$S \rArr S + A \rArr S + A + A \rArr S + A + A + A \rArr A + A + A + A$
$S \to AS'$ $S' \to \varepsilon|+AS'$
$A \to A * B|B$ $A \rArr^* B * B * B$ $A \to BA'$ $A' \to \varepsilon|*BA'$
$B \to x|(S)$ - это правило остаётся без изменений
Строим множнство $First$ и $Follow$
| $First$ | $Follow$ | |
|---|---|---|
| $S$ | $x, ($ | $\dashv, )$ |
| $S'$ | $\varepsilon,+$ | $\dashv, )$ |
| $A$ | $x, ($ | $+, \dashv, )$ |
| $A'$ | $\varepsilon, *$ | $+, \dashv, )$ |
| $B$ | $x, ($ | $*,+,\dashv, )$ |
Строим множество $Select$
| $Select$ | |
|---|---|
| $S \to AS'$ | $x, ($ |
| $S' \to \varepsilon$ | $\dashv, )$ |
| $S' \to +AS'$ | $+$ |
| $A \to BA'$ | $x, ($ |
| $A' \to \varepsilon$ | $+, \dashv, )$ |
| $A' \to*BA'$ | $*$ |
| $B \to x$ | $+$ |
| $B \to(S)$ | $($ |