《哈工大编译原理4-5》由会员分享，可在线阅读，更多相关《哈工大编译原理4-5（19页珍藏版）》请在金锄头文库上搜索。
1、第四章 语法分析14.5 LR分析方法对二义文法的应用 任何二义文法都不是LR文法 某些二义文法对语言的说明和实现非常 有用，如描述表达式的文法：EEE|E*E|(E)|id 规定优先级 和结合率无二义文法： EE+T|TTT*F|FF(E)|id2辛明影例：描述if语句的文法：stmtif expr then stmt|if expr then stmt else stmt|other规定匹配原则无二义文法 stmt matched_stmt |unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt |
2、other unmatched_stmt if expr then matched_stmt else unmatched_stmt | if expr then _stmt 3辛明影EE I0 E E+E E E*E E (E) E idEE I1 E E +E E E *EEE ( E) E E+E E E*E E (E) E id I2(E id I3idid(+E E+ E E E+E E E*E E (E) E id I4EE E* E E E +E E E *E例：EEE|E*E|(E)|idE (E.) I6 E E +E E E *EE E+ E E E +E E E *EE
3、(E). I9E E* E E E+E E E*E E (E) E id I5I7I8(idI3*E(id*)+4辛明影FOLLOW(E)=$FOLLOW(E)=$,+,*,)E E+ E I7 E E +E E E *E在I7状态，遇+，根据左结 合率，应对栈内+归约规定*优先级高于+*、+为左结合率在I7状态，遇*，根据优先 级，应将*移入栈内E E*E I8 E E +E E E *E在I8状态，遇*，根据左结 合率，应对栈内*归约在I8状态，遇+，根据优先 级，应对栈内*归约5辛明影表4.11 文法G4.4的SLR分析表6辛明影描述if语句的文法：stmtif expr then st
4、mt|if expr then stmt else stmt|other悬空else的二义性用I表示if expr then， e 表示else ,a表示 other,文法可改为：S SSiSeS|iS|a7辛明影S S I0 S iSeS S iS S aS S I1S i SeS I2 S i S S iSeS S iS S aS a I3S i S eS I4 S i S S i Se S I5 S iSeS S iS S aS i S eS I6SiaSiaeSia在I4状态遇e，栈内符号为iS，根据最近匹配 原则应移入eFollow(S)=$,e 8辛明影9辛明影LR(k)和LL(k
5、)的比较1. A1 2LL(k)根据FIRST(i)确定使用哪条 产生式；而LR(k)是在识别出整个后,再 往后看k个符号,然后确定使用哪条产生 式。wAwA10辛明影LL(k)文法都是LR(k)文法。 2. 都能用形式化方法实现； 3. 非LR结构例：L=wwR wa,b*GS: SaSa bSb 4. LR(k)分析用手工构造是不可能的。类Pascal语言的LR(1)分析表，估计要数 千 个状态；由于有软件工具， LR分析 受到广泛重视。 11辛明影4.5 分析器的生成器Yacc 一 . 用生成器Yacc构造翻译器的过程 Yacc 编译器yacc源程序 translate.yy.tab.c
6、C 编译器y.tab.ca.outa.out源程序输出12辛明影二. Yacc源程序有三部分组成 声明 翻译规则 C写的支持例程 三. 例4.21 台式计算器GE: EE+T TT T*F FF (E) digit读入一个表达式，计算它的值并输出。13辛明影% # include % % token digit% line : exprn printf(“%dn”,$1); expr : expr +term $=$1+$3;: term;14辛明影term : term *facter $=$1*$3;: facter; facter : (expr ) $=$2;: digit; % yy
7、lex() int c;c=getchar();if (isdigit( c ) yylval=c- 0;return digit ; return c ; 15辛明影声明部分 有任选的两节。第一节处于分界符%和%之间，它是一 些普通的C的声明； 第二节是文法记号的声明。翻译规则部分 每条翻译规则由一个文法产生式和有关的语义动作组成。 支持例程部分 一些C写的支持例程。例：词法分析器，错误恢复例程等。16辛明影总结：自顶向下分析递归预测分析（递归子程序法）非递归预测分析LL(1)注意：首先消除左递归和提取左公因子。自底向上分析算符优先分析LR分析:LR(0), SLR(1), LR(1), LALR(1)17辛明影LL(0)LR(0)SLRLALRLR(1)LR(k)LL(1)LL(k)Unambiguous GrammarsAmbiguousGrammars文法类的谱系18辛明影作业：4-40 第 一问3-37 第 一问19辛明影
