语法分析-消除左递归

⼀：什么是左递归?

在⼆型⽂法（上下⽂⽆关⽂法中），若⼀个⾮终极符A有任何直接⽂法规则或者通过多个⽂法规则，推导出的句型最左边符号⼜会出现A，我们说这个⾮终极符A是左递归的。

⼆：左递归的类型

• 直接左递归：经过⼀次推导就能看出⽂法存在左递归例如：A->Aa|b ,A∈VN ，a,b∈（VN∪VT）*

• 间接左递归：经过多次推导才能看出⽂法存在左递归例如：A->Ba|β，B->Ar|β，A,B∈VN，a,β,r∈（VN∪VT）*

三：左递归的消除⽅法

• 直接左递归的消除：步骤：

1) 把所有产⽣式写成下列形式：

A→Aa1｜Aa2……｜Aan｜b1｜b2……｜bm，其中每个a都不等于ε，每个b都不以A开头。2）变换候选式成如下形式：A→b1A’｜b2A’……｜bmA’A’ →a1A’｜a2A’……｜anA’｜ε例如：

s->sb,|a可以替换为 s->as' ，s'->b,s'|ε• 间接左递归的消除：步骤：

1）把间接左递归化成直接左递归

2）按照直接左递归的消除⽅法进⾏消除例如：A->Bc∣dB->aA∣Ab

1）转换成直接左递归A->aAc∣Abc∣d

2）消除直接左递归A->aAcA′∣dA′A′->bcA′∣ε