E→>E+T|T T→)T*FF F>E)i 消除左递归后,为 E→TE E→+TE'|E T→FT T→*FT'E F→(E)|i 间接左递归的例 S→>Aalb →Ac|Sl|E 16
16 消除左递归后，为 F E i T T F F E E T T ( )| * || F E i T FT T FT E TE E TE( ) | * | ' | | | | A Ac Sd 间接左递归的例 S Aa b
消除间接左递归的算法 (1)将文法G的所有非终结符按一给定的顺序排序; (2)for(i=1;i<=n;i++) for(=1;j=i-1;j++) 把一个4→)4v形如的产生式改写为, A1→>y|2v|…|dv 其中A1→>1|2|…|是的所有产生式; 消除A1产生式的直接左递归; (3)化简。去除从开始符号出发无法到达的非终结符的产生式,即 去除多余产生式 算法不允许文法中有产生式。因此如果文法中有E的产生式,需 将文法改写。 17
17 消除间接左递归的算法 (1) 将文法G的所有非终结符按一给定的顺序排序； (2) for(i＝1；i<=n；i++) for(j＝1；j<=i-1；j++) { 把一个 形如的产生式改写为， 其中 是的所有产生式； 消除A1产生式的直接左递归； } (3) 化简。去除从开始符号出发无法到达的非终结符的产生式，即 去除多余产生式。 算法不允许文法中有产生式。因此如果文法中有的产生式，需 将文法改写。 A Av i j A v v v i k | | | 1 2 Aj k | | | 1 2
四、预测分析器 消除了左递归、提取了公共左因子之后,就可以 构造一个不带回溯的递归下降分析器了。即为每 个非终结符写一个递归过程,以实现关于这个非 终结符的分析。 「例46(4.5)为消除左递归后的无公共左因子的表 达式文法,它的预测分析器: void match(token t) if(lookahead==t)t lookahead=nexttoken; f elsei error; 18
18 四、预测分析器 消除了左递归、提取了公共左因子之后，就可以 构造一个不带回溯的递归下降分析器了。即为每 个非终结符写一个递归过程，以实现关于这个非 终结符的分析。 [例4.6] (4.5)为消除左递归后的无公共左因子的表 达式文法，它的预测分析器: void match(token t) {if(lookahead==t){ lookahead=nexttoken;} else{ error();} }
void EO {T0;E0} void TO fFO; TO void To i if(lookahead==>*>i match(*); F0; T0; 19
19 void E() { T(); E’();} void T() { F(); T’();} void T’() { if(lookahead==’*’ ){ match(‘*’);F();T’();} }
void E0 if(lookahead==+imatch ( +);TO; E0:5 void FO if(lookahead==i)match(D);) else if(lookahead==0 Match(O;EO; if(lookahead==o)) imatch());9 eise error 0;} elselerror(; 用分析器作语法分析有个前提条件,即描述 语法分析器的语言必须允许递归调用。 20
20 void E’() {if(lookahead==’+’){match(‘+’);T();E’();}} void F() {if(lookahead==’i’){match(‘i’);} else if(lookahead==’(‘) {match(‘(‘);E();if(lookahead== ‘)’) {match(‘ )’);} else {error();}} else{error();} } 用分析器作语法分析有个前提条件，即描述 语法分析器的语言必须允许递归调用