编译原理语法分析 (2).ppt

例：表达式文法直接左递归的消除 E → E + T｜T T → T * F｜F F → ( E )｜id E→ T E’ E’→ + T E’|ε T→ F T’ T’→* F T’｜ε F→ ( E )｜id 例： 间接左递归的消除 S→Ac|c A→Bb|b B→Sa|a 将B的定义代入A产生式得：A→Sab|ab|b 将A的定义代入S产生式得: S→Sabc|abc|bc|c 消除直接左递归： S→abcS’|bcS’|cS’ 　 S’→abcS’|ε 删除“多余的”产生式：A→Sab|ab|b和B→Sa|a 结果： S→abcS’|bcS’|cS’ 　 S’→abcS’|ε 消除左递归的一般方法 用产生式组 A?β1 B|β2 B |…|βm B B?α1 B|α2 B |…|αn B|ε 替换产生式组 A→Aα1|Aα2|…|Aαn|β1|β2|…|βm 其中：B为新变量，相当于A’ 提取左因子 例：if语句的原始文法 S→ if E then S |if E then S else S |other 存在左因子 if E then S 影响分析:遇到 if 时难以判断用哪一个产生式进行匹配（推导） 左因子提取方法 将形如 A→αβ1|αβ2|…|αβn |γ1|γ2|… | γm 的规则改写为 A→αA’|γ1|γ2|… | γm和 A→β1|β2|…|βn 结果： S→ if E then SS’|other S→ε|else S 例 简单算术表达式的分析器 Ｅ的子程序(E→T|E+T) procedure E; begin T; Ｔ的过程调用 while lookhead=+ do begin 当前符号等于＋时 match(‘+’); 处理终结符＋ T Ｔ的过程调用 end end; lookhead：当前符号 E→ T E’ E’→ + T E’|ε Ｔ的子程序(T→F|T*F) procedure T; begin F; Ｆ的过程调用 while lookhead=* then begin 当前符号等于＊时 match(*); 处理终结符＊ F Ｆ的递归调用 end end; T→ F T’ T’→* F T’｜ε Ｆ的子程序(F→(E)|id) procedure F; begin if lookhead=( then begin 当前符号等于（ match((); 处理终结符（ E; Ｅ的递归调用 match()); 处理终结符） end else if lookhead=id then match(id) 处理终结符id else error 出错处理 end 主程序 begin lookhead:=nexttoken; 调词法分析程序 E Ｅ的过程调用 end procedure match(t:token); begin if lookhead=t then lookhead:=nexttoken else error 出错处理程序 end; 递归下降子程序 program – function_list function_list – function function_list | ? function – FUNC identifier ( parameter_list ) statement void ParseFunction() { MatchToken(T_FUNC); ParseIdentifier(); MatchToken(T_LPAREN); ParseParameterList(); MatchToken(T_RPAREN); ParseStatement(); } 优缺点分析 优点：