又到了我们喜闻乐见的消除左递归环节。每次我都会忘记怎么操作,因为每次我图省事都死记那个公式,考完就忘。

按理来说文法的运算就那么几种,那能不能直接算出来呢?试了一下果然可以!(可能不太严谨,但对于帮助熟练此算法是好的)

解释

首先,我们有一个代表性的左递归语法:

$$ \begin{align} A \to Aa_1 \mid Aa_2 \mid b_1\mid b_2 \end{align} $$

第一步,我们这样分成两堆:

$$ A \to A(a_1\mid a_2) \quad A \to (b_1\mid b_2) $$

两式右边连接临时非终结符 $T$ (它可置空,否则会改变语法)

$$ AT \to A(a_1\mid a_2)T \quad AT \to (b_1\mid b_2)T $$

左式的 $A$ 可以消除。

$$ T \to (a_1\mid a_2)T \quad AT \to (b_1\mid b_2)T $$

注意 $T$ 是可空的,因此:

$$ T \to (a_1\mid a_2)T \mid \varepsilon \quad A \to (b_1\mid b_2)T $$

简而言之,只要分成两堆,右边加上 $T$ ,然后代入可空情况,即可消除左递归。熟练之后可以直接写出来,并且有十足信心是正确答案。

例子

(1)$E \to E + T \mid T$

右连临时变符 $E'$ ,得到 $E E' = E + T E' \quad EE' \to TE'$

左删变符 $E$,并考虑致空 ,得到 $E' = + TE' \mid \varepsilon $

以及 $E \to TE'$

(2)$S \to Sabc\mid abc\mid bc\mid c$

$$ \begin{align} & SS' \to SabcS' \quad & SS'\to& (abc|bc|c)S'\\ \Rightarrow& S' \to SabcS' \mid \varepsilon \quad & S \to& (abc|bc|c)S' \end{align} $$

因此答案为:

$$ \begin{align} S &\to abcS' \mid bcS' \mid cS' \\ S' &\to SabcS\ \mid \varepsilon \\ \end{align} $$

(3)

$$ \begin{align}S &\to baA\mid \varepsilon \\A &\to Sbb\mid a\end{align} $$

疑问

消除左递归和尾递归优化是否存在某种关系呢?