编译原理-消除左递归

前言

在进行语法分析的时候，如果采用自上而下的分析方法（从开始符开始，推句子），那么要求文法不是左递归的，进而如果是左递归的，则要求消除左递归 左递归的定义：文法经过一次或多次推导之后，出现如下形式 左递归的分类 直接左递归：P → Pa 简介左递归：P → Aa， A → …… → Pb

直接左递归的消除

对于 P → Pa | b 形式(b可为空)，可以知道，推导结束的时候一定有一个b在最开始位置（如ba），后面是无数多个a，所以可以归纳得出如下的消除方法

P  →  bP;
P  →  aP | ε;

更一般化的形如P → PX|Y（其中X和Y看作一个整体，比如：P → Pabc|ab|b，X就是abc，Y就是ab|b），可以归纳成如下形式：

P  →  YP;        比如：P  →  abP | b P
P  →  XP | ε;   比如： P  →  abcP | ε

间接左递归的消除

对于P → Aa | x1， A → …… → Pb | x2的形式 消除规则 1） 若消除过程中出现了直接左递归，就按照直接左递归的方法，来消除 2） 若产生式右部最左的符号是非终结符，且这个非终结符序号大于等于左部非终结符，则暂不处理（后面会处理到） 3） 若序号小于左部的非终结符，则用之前求到的式子的右部来替换 步骤伪代码

// 1.把文法G的所有非终结符按任意顺序排列，并编号
[P1,P2,……,Pn]

// 2.按上面的排列顺序，对这些非终结符进行遍历
for(int i = 1; i <= n; ++i) {

  for(int j = 1; i <= i - 1; ++j) {
    // 3.将当前处理的非终结符中的序号小于等于它的非终结符按规则3）进行替换（序号大于的按规则2）处理）
    2）、3）
  }
  // 4.消除i序号的非终结符的直接左递归（如果存在的话）
  1）
}

// 5.删除其中不可达的非终结符（从开始符开始，无法再推出的非终结符）

注意 第一步对非终结符进行排序的序列不同，最后结果的产生式有可能不同，但它们是等价的 开始符号不能改变 该算法，能同时消除直接、间接左递归

例题

存在如下文法，消除左递归 1）S → Qc | c 2）Q → Rb | b 3）R → Sa | a

1）把文法G的所有非终结符按任意顺序排列，并编号

R、Q、S

2）按上面的排列顺序，对这些非终结符进行遍历 3）将当前处理的非终结符中的序号小于等于它的非终结符按规则3）进行替换（序号大于的按规则2）处理）

R:
R的右部中的非终结符有S;
S的下标大于R，可以暂时不处理;
所以此时R改写为：R  →  Sa | a

----------------------------------------------
Q:
Q的右部中的非终结符有R;
R的下标小于Q，将R的右部替换进来;
所以此时Q改写为：Q  →  Sab | ab | b;
S的下标大于Q，可以暂时不处理;
所以此时Q改写为：Q  →  Sab | ab | b;

-----------------------------------------
S:
S的右部中的非终结符有Q;
Q的下标小于S，将Q的右部替换进来;
所以此时S改写为：S  →  Sabc |abc | bc | c
S的下标等于S，可以暂时不处理;
所以此时S改写为：S  →  Sabc |abc | bc | c

4）消除i序号的非终结符的直接左递归（如果存在的话）

S  →  Sabc |abc | bc | c
∴  X = abc，Y = abc | bc | c
∴ 直接消除左递归的结果是：
S  →  abcS | bcS | cS
S  → abcS | ε

5）删除其中不可达的非终结符，这里就是Q、R了

∴ 最终消除左递归的结果是

S  →  abcS | bcS | cS
S  → abcS | ε

其它

课件下载：

更多信息：