编译原理习题(精品).ppt

《编译原理习题(精品).ppt》由会员分享，可在线阅读，更多相关《编译原理习题(精品).ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.1.四元式之间的联系是通过四元式之间的联系是通过四元式之间的联系是通过四元式之间的联系是通过_实现的实现的实现的实现的A A、临时变量临时变量临时变量临时变量 B B、序列行号序列行号序列行号序列行号 C C、程序变量程序变量程序变量程序变量 D D、符号表符号表符号表符号表2.2.中间代码生成时所依据的是中间代码生成时所依据的是中间代码生成时所依据的是中间代码生成时所依据的是_A A、词法规则词法规则词法规则词法规则 B B、语法规则语法规则语法规则语法规则 C C、语义规则语义规则语义规则语义规则 D D、等价变换等价变换等价变换等价变换3.3.在编译程序中与生成中间代码的目的在编译程

2、序中与生成中间代码的目的在编译程序中与生成中间代码的目的在编译程序中与生成中间代码的目的无关无关无关无关的是的是的是的是_A A、便于目标代码的优化便于目标代码的优化便于目标代码的优化便于目标代码的优化 B B、便于存储空间的组织便于存储空间的组织便于存储空间的组织便于存储空间的组织C C、便于目标代码的移植便于目标代码的移植便于目标代码的移植便于目标代码的移植 D D、便于编译程序的移植便于编译程序的移植便于编译程序的移植便于编译程序的移植14 4、在语法制导翻译中，不采用拉链、在语法制导翻译中，不采用拉链、在语法制导翻译中，不采用拉链、在语法制导翻译中，不采用拉链-回填技术的语句是回填技术

3、的语句是回填技术的语句是回填技术的语句是_A.A.转向语句转向语句转向语句转向语句B B、赋值语句赋值语句赋值语句赋值语句 C C、条件语句条件语句条件语句条件语句 D D、循环语句循环语句循环语句循环语句5 5、能正确表示算术表达式、能正确表示算术表达式、能正确表示算术表达式、能正确表示算术表达式a+b*c+da+b*c+d的后缀式是的后缀式是的后缀式是的后缀式是_A A、abcabc*+d+B.*+d+B.abcabc*d+C.*d+C.abab+cdcd*+D.*+D.bcbc*a+d+*a+d+6 6、对对对对_表进行变动较为困难表进行变动较为困难表进行变动较为困难表进行变动较为困难A

4、 A、三元式三元式三元式三元式B B、间接三元式间接三元式间接三元式间接三元式C C、四元式四元式四元式四元式 D D、三地址码三地址码三地址码三地址码27 7、P202P202练习练习练习练习5.2.3.5.2.3.有产生有产生有产生有产生式式式式ABCDABCDABCDABCD，其中四个文法符号均其中四个文法符号均其中四个文法符号均其中四个文法符号均有两个属性，有两个属性，有两个属性，有两个属性，s s为综合属性，为综合属性，为综合属性，为综合属性，i i为继承属性。为继承属性。为继承属性。为继承属性。判断是否符合判断是否符合判断是否符合判断是否符合S S属性定义；是否符合属性定义；是否符

5、合属性定义；是否符合属性定义；是否符合L L属性定义；是否存属性定义；是否存属性定义；是否存属性定义；是否存在和这些规则一致的求值过程在和这些规则一致的求值过程在和这些规则一致的求值过程在和这些规则一致的求值过程1)A.s=B.i+C.s2)A.s=B.i+C.s 和和D.i=A.i+B.s 3)A.s=B.s+D.s4)A.s=D.i,B.i=A.s+C.s,C.i=B.s和和D.i=B.i+C.i385.3.1E85.3.1EE+T|TTE+T|TTnum.num|numnum.num|num1)1)给出一个给出一个给出一个给出一个SDDSDD来确定每个项来确定每个项来确定每个项来确定每个

6、项T T和表达式和表达式和表达式和表达式E E的类型的类型的类型的类型解：重写文法为：解：重写文法为：解：重写文法为：解：重写文法为：E EE E1 1+T|TT+T|TTnumnum1 1.num.num2 2|num|num引入属性引入属性引入属性引入属性typetype,typetype为为为为intint表示整型，为表示整型，为表示整型，为表示整型，为floatfloat表示实型，给出表示实型，给出表示实型，给出表示实型，给出SDDSDD：产生式产生式产生式产生式语义规则语义规则语义规则语义规则E EE E1 1+T+Tif(Eif(E1 1.typetype=intint)&(T.)

7、&(T.typetype=intint)E.E.typetype=intint;elseE.elseE.typetype=float;=float;EETTE.E.typetype=T.=T.typetypeT Tnumnum1 1.num.num2 2T.T.typetype=float=floatT TnumnumT.T.typetype=intint495.4.495.4.4为下面的产生式写出与例为下面的产生式写出与例为下面的产生式写出与例为下面的产生式写出与例5.105.10类似的一个类似的一个类似的一个类似的一个L L属性属性属性属性SDDSDD。S Sif(C)Sif(C)S1 1

8、elseSelseS2 2解：语义规则为：解：语义规则为：解：语义规则为：解：语义规则为：L L1 1=new();=new();L L2 2=new();=new();C.true=LC.true=L1 1;C.falseC.false=L=L2 2;S S1 1.next=S.next=S2 2.next=S.next;.next=S.next;S.codeS.code=C.code|label|L=C.code|label|L1 1|S|S1 1.code|.code|gotogoto|S.next|label|L|S.next|label|L2 2|S S2 2.code.code51

9、05.5.5105.5.5按照按照按照按照5.5.45.5.4节的风格，将节的风格，将节的风格，将节的风格，将5.4.45.4.4中得到的每个中得到的每个中得到的每个中得到的每个SDDSDD和一个和一个和一个和一个LRLR语语语语法分析器一起实现。法分析器一起实现。法分析器一起实现。法分析器一起实现。解：加入必要的占位符，重写文法为：解：加入必要的占位符，重写文法为：解：加入必要的占位符，重写文法为：解：加入必要的占位符，重写文法为：S Sif(Mif(M1 1C)MC)M2 2SS1 1elseMelseM3 3SS2 2MM 假设假设假设假设S.nextS.next位于归约之后的栈顶第二条

10、记录：可以给出位于归约之后的栈顶第二条记录：可以给出位于归约之后的栈顶第二条记录：可以给出位于归约之后的栈顶第二条记录：可以给出S S识别过程的识别过程的识别过程的识别过程的LRLR语法分析栈变化及相关代码如下：语法分析栈变化及相关代码如下：语法分析栈变化及相关代码如下：语法分析栈变化及相关代码如下：?S.nexS.next tif if(MM1 1C.trueC.trueC.falseC.falseL L1 1L L2 2将将将将 归约到归约到归约到归约到MM1 1时执行的代码：时执行的代码：时执行的代码：时执行的代码：C.true=LC.true=L1 1=new();=new();C.f

11、alse=LC.false=L2 2=new();=new();6?S.nexS.next tif if(MM1 1C.trueC.trueC.falseC.falseL L1 1L L2 2将将将将 归约到归约到归约到归约到MM2 2时执行的代码：时执行的代码：时执行的代码：时执行的代码：S S1 1.next=stacktop-6.next;.next=stacktop-6.next;C CC.codeC.code)MM2 2S S1 1.next.next7?S.nexS.next tif if(MM1 1C.trueC.trueC.falseC.falseL L1 1L L2 2将将将

12、将 归约到归约到归约到归约到MM3 3时执行的代码：时执行的代码：时执行的代码：时执行的代码：S S2 2.next=stacktop-9.next;.next=stacktop-9.next;C CC.codeC.code)MM2 2S S1 1.next.nextS S1 1S S1 1.code.codeelselse eMM3 3S S2 2.next.next8?S.nexS.next tif if(MM1 1C.trueC.trueC.falseC.falseL L1 1L L2 2将将将将if(Mif(M1 1C)MC)M2 2SS1 1elseMelseM3 3SS2 2 归约

13、到归约到归约到归约到S S时的代码：时的代码：时的代码：时的代码：tempcodetempcode=stacktop-6.code|label|stacktop-7.L=stacktop-6.code|label|stacktop-7.L1 1|stacktop-3.code|stacktop-3.code|gotogoto|stacktop-10.next|label|stacktop-10.next|label|stacktop-7.Lstacktop-7.L2 2|stacktop.code|stacktop.codetop=top9;top=top9;stacktop.code=sta

14、cktop.code=tempcodetempcode;C CC.codeC.code)MM2 2S S1 1.next.nextS S1 1S S1 1.code.codeelselse eMM3 3S S2 2.next.nextS S2 2S S2 2.code.code91111、为下面的表达式构造、为下面的表达式构造、为下面的表达式构造、为下面的表达式构造DAGDAG(x+y)-(x+y)*(x-y)+(x+y)*(x-y)(x+y)-(x+y)*(x-y)+(x+y)*(x-y)+x xy y*+101212、P237P237练习练习练习练习6.2.16.2.1将算术表达式将算术表

15、达式将算术表达式将算术表达式a+-(b+c)a+-(b+c)翻译成抽象语翻译成抽象语翻译成抽象语翻译成抽象语法树、四元式序列、三元式序列、间接三元式序列。法树、四元式序列、三元式序列、间接三元式序列。法树、四元式序列、三元式序列、间接三元式序列。法树、四元式序列、三元式序列、间接三元式序列。抽象语法树抽象语法树抽象语法树抽象语法树+a auminusuminus+b bc c四元式序列四元式序列四元式序列四元式序列三元式序列三元式序列三元式序列三元式序列0 01 12 2+b bc cuminusuminus(0)(0)+a a(1)(1)+b bc ct t1 1uminusuminust

16、t1 1t t2 2+a at t2 2t t3 3111212、P237P237练习练习练习练习6.2.16.2.1将算术表达式将算术表达式将算术表达式将算术表达式a+-(b+c)a+-(b+c)翻译成抽象语翻译成抽象语翻译成抽象语翻译成抽象语法树、四元式序列、三元式序列、间接三元式序列。法树、四元式序列、三元式序列、间接三元式序列。法树、四元式序列、三元式序列、间接三元式序列。法树、四元式序列、三元式序列、间接三元式序列。+b bc cuminusuminus(0)(0)+a a(1)(1)0 01 12 2(0)(0)(1)(1)(2)(2)指令指令指令指令303031313232间接三

17、元式间接三元式121313、P237P237练习练习练习练习6.2.26.2.2a=bi+cja=bi+cj抽象语法树抽象语法树抽象语法树抽象语法树=a a+b bi i四元式序列四元式序列四元式序列四元式序列*i i8 8t t1 1=b bt t1 1t t2 2*j j8 8t t3 3=c ct t3 3t t4 4+t t2 2t t4 4t t5 5=t t5 5a a=c cj j131313、P237P237练习练习练习练习6.2.26.2.2ai=b*cb*dai=b*cb*d抽象语法树抽象语法树抽象语法树抽象语法树=a a b bc c四元式序列四元式序列四元式序列四元式序

18、列*i i8 8t t1 1=a at t1 1t t2 2*b bc ct t3 3*b bd dt t4 4 t t3 3t t4 4t t5 5=t t5 5t t2 2=*b bd di i*141414、6.5.1(1)6.5.1(1)假定图假定图假定图假定图6-266-26中的函数中的函数中的函数中的函数widenwiden可以处理图可以处理图可以处理图可以处理图6-256-25a a的的的的层次结构中的所有类型，翻译下列表达式。假设层次结构中的所有类型，翻译下列表达式。假设层次结构中的所有类型，翻译下列表达式。假设层次结构中的所有类型，翻译下列表达式。假设x x是浮点是浮点是浮点

19、是浮点型，型，型，型，s s是短整型是短整型是短整型是短整型,c c是字符型。是字符型。是字符型。是字符型。x=s+cx=s+ctt1 1=(short)c=(short)ctt2 2=s+t=s+t1 1tt3 3=(float)t=(float)t2 2x=tx=t3 3151515、6.4.6(1)6.4.6(1)一个按行存放的整数数组一个按行存放的整数数组一个按行存放的整数数组一个按行存放的整数数组Ai,jAi,j的的的的i i的范围为的范围为的范围为的范围为1-1-1010，下标，下标，下标，下标j j的范围为的范围为的范围为的范围为1-201-20。每个整数占。每个整数占。每个整数

20、占。每个整数占4 4个字节。假设数组个字节。假设数组个字节。假设数组个字节。假设数组A A从从从从0 0字节开始存放，请给出下列元素的位置：字节开始存放，请给出下列元素的位置：字节开始存放，请给出下列元素的位置：字节开始存放，请给出下列元素的位置：A4,5A4,5(4-1)*20+(5-1)*4=256(4-1)*20+(5-1)*4=2566.4.7(1)6.4.7(1)按列存放方式按列存放方式按列存放方式按列存放方式(5-1)*10+(4-1)*4=172(5-1)*10+(4-1)*4=172161616、2.3.12.3.1构建一个语法制导翻译构建一个语法制导翻译构建一个语法制导翻译构

21、建一个语法制导翻译方案，该方案将算术表达式从中方案，该方案将算术表达式从中方案，该方案将算术表达式从中方案，该方案将算术表达式从中缀表示方式翻译成前缀表示方式。缀表示方式翻译成前缀表示方式。缀表示方式翻译成前缀表示方式。缀表示方式翻译成前缀表示方式。给出输入给出输入给出输入给出输入9-5+29-5+2的注释分析树。的注释分析树。的注释分析树。的注释分析树。解：解：解：解：EEprint(+)Eprint(+)E1 1+T+TEprint(-)EEprint(-)E1 1TT 以下规则类似图以下规则类似图以下规则类似图以下规则类似图2-152-152-152-15E EE E+T Tprint(

22、+)print(+)print(-)print(-)E E-T T2 2print(2)print(2)print(5)print(5)5 5T T9 9print(9)print(9)171717、3.8.1(1)3.8.1(1)假设我们有两个词法单元：关键字假设我们有两个词法单元：关键字假设我们有两个词法单元：关键字假设我们有两个词法单元：关键字ifif和标识和标识和标识和标识符（除符（除符（除符（除if if外的所有由字母组成的串），请给出识别这些词外的所有由字母组成的串），请给出识别这些词外的所有由字母组成的串），请给出识别这些词外的所有由字母组成的串），请给出识别这些词法单元的法单元

23、的法单元的法单元的NFANFA，请给出识别这些词法单元的请给出识别这些词法单元的请给出识别这些词法单元的请给出识别这些词法单元的DFADFA。解：以下用解：以下用解：以下用解：以下用 表示除表示除表示除表示除i,fi,f外的任意字母外的任意字母外的任意字母外的任意字母a,b,z,A,B,Za,b,z,A,B,Z。识别识别识别识别if if的的的的NFANFA为：为：为：为：1 12 23 3i if f识别标识符的识别标识符的识别标识符的识别标识符的NFANFA为：为：为：为：4 45 5i,f,i,f,i,f,i,f,181717、集成、集成、集成、集成NFANFA为：为：为：为：1 12

24、23 3i if f4 45 50 0 i,f,i,f,i,f,i,f,191717、对应的、对应的、对应的、对应的DFADFA状态状态状态状态输入符号输入符号输入符号输入符号模式模式模式模式i if f 0,1,40,1,42,52,555552,52,5553,53,555idid55555555idid3,53,5555555if ifA AB BC CD DA AB Bi iC CD Df,f,i,i,f fi,f,i,f,i,f,i,f,201818、4.4.44.4.4计算下列文法计算下列文法计算下列文法计算下列文法的的的的FIRSTFIRST集和集和集和集和FOLLOWFOLLO

25、W集集集集（3 3）SSSS（S S）S|S|FIRST(S)=(,FIRST(S)=(,FOLLOW(S)=(,),$FOLLOW(S)=(,),$（5 5）SS(L L)|a aLLLL,S|SS|SFIRST(S)=(,aFIRST(S)=(,aFIRST(L)=(,aFIRST(L)=(,aFOLLOW(S)=FOLLOW(S)=$,)FOLLOW(L)=FOLLOW(L)=,)211919、4.6.14.6.1（1 1）描述下列文法的所有可行前缀）描述下列文法的所有可行前缀）描述下列文法的所有可行前缀）描述下列文法的所有可行前缀SS0S1|0S1|0101解：本文法可推出的右句型可表

26、示为解：本文法可推出的右句型可表示为解：本文法可推出的右句型可表示为解：本文法可推出的右句型可表示为0 0n nS1S1n n或或或或0 0n n1 1n n，其中其中其中其中n=1.n=1.句型句型句型句型0 0n nS1S1n n的句柄为的句柄为的句柄为的句柄为0 0S1S1，此时可行前缀为此时可行前缀为此时可行前缀为此时可行前缀为0 0n nS1S1的前缀。的前缀。的前缀。的前缀。句型句型句型句型0 0n n1 1n n的句柄为的句柄为的句柄为的句柄为0 01 1，此时可行前缀为此时可行前缀为此时可行前缀为此时可行前缀为0 0n n1 1的前缀。的前缀。的前缀。的前缀。本文法的可行前缀集

27、合为以上两可行前缀集合的并集。本文法的可行前缀集合为以上两可行前缀集合的并集。本文法的可行前缀集合为以上两可行前缀集合的并集。本文法的可行前缀集合为以上两可行前缀集合的并集。2220、3.3.4:用一个正规式描述用一个正规式描述select，注意：不关心大小写，注意：不关心大小写，如如SeleCt也可为本正规式匹配。也可为本正规式匹配。(s|S)(e|E)(l|L)(e|E)(c|C)(t|T)232121、练习、练习、练习、练习4.5.24.5.2文法文法文法文法S SSS+|SS*|a,SS+|SS*|a,指出下面最右句型的句柄指出下面最右句型的句柄指出下面最右句型的句柄指出下面最右句型的

28、句柄2)2)SS+a*a+SS+a*a+S SS SS S+a a可画出可画出可画出可画出分析树如上，句柄为分析树如上，句柄为分析树如上，句柄为分析树如上，句柄为SS+SS+S SS S*a aS SS S+242222、练习、练习、练习、练习4.6.5:4.6.5:说明下面的文法：说明下面的文法：说明下面的文法：说明下面的文法：SS AaAbAaAb|BbBaBbBaA AB B 不是不是不是不是SLR(1)SLR(1)的。的。的。的。解：引入识别符解：引入识别符解：引入识别符解：引入识别符SS，SSS S，得拓广文法得拓广文法得拓广文法得拓广文法：(0)(0)SSS(1)S(1)S SAa

29、AbAaAb(2)(2)S SBbBaBbBa(3)A(3)A(4)B(4)B 开始构建项目集规范族：开始构建项目集规范族：开始构建项目集规范族：开始构建项目集规范族：状态状态状态状态项目集项目集项目集项目集后继符号后继符号后继符号后继符号后继状态后继状态后继状态后继状态S S0 0 S S SSS S AaAbAaAbS S BbBaBbBaA A B B S SA AB B#A#A#B#B S S1 1S S2 2S S3 3由于由于由于由于Follow(A)=Follow(B)=a,b,Follow(A)=Follow(B)=a,b,在状态在状态在状态在状态0 0时，如果输入时，如果输入

30、时，如果输入时，如果输入a a或或或或b b时，时，时，时，无法确定归约方式，本文法非无法确定归约方式，本文法非无法确定归约方式，本文法非无法确定归约方式，本文法非SLR(1)SLR(1)。252323、练习、练习、练习、练习4.7.14.7.1为文法为文法为文法为文法S SSS+|SS*|aSS+|SS*|a构造构造构造构造1 1）规范）规范）规范）规范LRLR项集族项集族项集族项集族引入识别符引入识别符引入识别符引入识别符SS，SSS S，得拓广文法得拓广文法得拓广文法得拓广文法(0)(0)SSS(1)S(1)S SSS+(2)SS+(2)S SSS*(3)SSS*(3)Sa a状态状态状

31、态状态项目集项目集项目集项目集后继符号后继符号后继符号后继符号后继状态后继状态后继状态后继状态S S0 0 S S S,$S,$S S SS+,$|aSS+,$|aS S SS*,$|aSS*,$|aS S a,$|a a,$|aS SS SS Sa aS S1 1S S1 1S S1 1S S2 2S S1 1 S S S,$S,$S S SS+,$|aSS+,$|aS S SS*,$|aSS*,$|aS S SS+,SS+,+|*|a+|*|aS S SS*,SS*,+|*|a+|*|aS S a,+|*|a a,+|*|a#S S S S S SS SS SS Sa aS S1010S

32、S3 3S S3 3S S3 3S S3 3S S4 4S S2 2S S a,$|a a,$|a#S S a aS S101026状态状态状态状态项目集项目集项目集项目集后继符号后继符号后继符号后继符号后继状态后继状态后继状态后继状态S S3 3 S S SS+,$|aSS+,$|aS S SS*,$|aSS*,$|aS S SS+,+|*|aSS+,+|*|aS S SS*,+|*|aSS*,+|*|aS S SS+,+|*|aSS+,+|*|aS S SS*,+|*|aSS*,+|*|aS S a,+|*|a a,+|*|a+*S SS SS SS Sa aS S5 5S S6 6S S

33、7 7S S7 7S S7 7S S7 7S S4 4S S4 4 S S a,+|*|a a,+|*|a#S S a aS S1010S S5 5 S S SS+,$|aSS+,$|a#S SSS+SS+S S1010S S6 6 S S SS*,$|aSS*,$|a#S SSS*SS*S S1010S S7 7 S S SS+,+|*|aSS+,+|*|aS S SS*,+|*|aSS*,+|*|aS S SS+,+|*|aSS+,+|*|aS S SS*,+|*|aSS*,+|*|aS S SS+,+|*|aSS+,+|*|aS S SS*,+|*|aSS*,+|*|aS S a,+|*

34、|a a,+|*|a+*S SS SS SS Sa aS S8 8S S9 9S S7 7S S7 7S S7 7S S7 7S S4 4S S8 8 S S SS+,+|*|aSS+,+|*|a#S SSS+SS+S S1010S S9 9 S S SS*,+|*|aSS*,+|*|a#S SSS*SS*S S101027实验三：语义分析实验实验三：语义分析实验实验三：语义分析实验实验三：语义分析实验一、实验目的一、实验目的一、实验目的一、实验目的 根据给出的文法编制语义分析程序。加深对自底向上根据给出的文法编制语义分析程序。加深对自底向上根据给出的文法编制语义分析程序。加深对自底向上根据给

35、出的文法编制语义分析程序。加深对自底向上语义分析的理解。语义分析的理解。语义分析的理解。语义分析的理解。二、实验时间二、实验时间二、实验时间二、实验时间 21 21 21 21学时学时学时学时三、实验内容三、实验内容三、实验内容三、实验内容 对所给语言文法，增加相应的语义代码，并输出所得对所给语言文法，增加相应的语义代码，并输出所得对所给语言文法，增加相应的语义代码，并输出所得对所给语言文法，增加相应的语义代码，并输出所得三地址码；三地址码；三地址码；三地址码；实验报告必须包括采用的语法制导定义或翻译模式，实验报告必须包括采用的语法制导定义或翻译模式，实验报告必须包括采用的语法制导定义或翻译模

36、式，实验报告必须包括采用的语法制导定义或翻译模式，设计的思路，测试报告（输入测试例子，输出结果），设设计的思路，测试报告（输入测试例子，输出结果），设设计的思路，测试报告（输入测试例子，输出结果），设设计的思路，测试报告（输入测试例子，输出结果），设计的体会。计的体会。计的体会。计的体会。28实验三：语义分析实验实验三：语义分析实验实验三：语义分析实验实验三：语义分析实验四、文法四、文法四、文法四、文法 program program program:=:=:=:=.:=:=:=:=-list-list-list -list-list-list:=:=:=:=|-list-list-list

37、:=:=:=:=-list-list-list;:=:=:=:=floatfloatfloatfloat|intintintint -list-list-list:=:=:=:=idididid|-list-list-list,idididid :=:=:=:=id=id=id=id=|beginbeginbeginbegin endendendend|ifififif thenthenthenthen|dodododo whilewhilewhilewhile 29实验三：语义分析实验实验三：语义分析实验实验三：语义分析实验实验三：语义分析实验四、文法（续）四、文法（续）四、文法（续）四、文

38、法（续）:=:=:=:=|;:=:=:=:=:=:=:=:=|=:=:=:=:=|:=:=:=:=+|-:=:=:=:=|:=:=:=:=*|/:=:=:=:=id id id id|num num num num|()30实验三：语义分析实验实验三：语义分析实验实验三：语义分析实验实验三：语义分析实验五、说明五、说明五、说明五、说明（1 1 1 1）如如如如果果果果不不不不能能能能采采采采用用用用自自自自底底底底向向向向上上上上实实实实现现现现，可可可可以以以以选选选选择择择择采采采采用用用用其其其其它它它它方方方方法，如法，如法，如法，如:可以自顶向下实现，此时满分为可以自顶向下实现，此时

39、满分为可以自顶向下实现，此时满分为可以自顶向下实现，此时满分为B+B+B+B+。（2 2 2 2）可可可可以以以以对对对对所所所所给给给给文文文文法法法法的的的的子子子子集集集集进进进进行行行行分分分分析析析析，此此此此时时时时根根根根据据据据实实实实际际际际情情情情况况况况适适适适当当当当扣扣扣扣分分分分。最最最最少少少少需需需需完完完完成成成成 expressionexpressionexpression的的的的分分分分析析析析，此此此此时时时时如如如如为为为为自自自自底底底底向向向向上上上上分分分分析析析析，满满满满分分分分为为为为B B B B，如如如如果果果果基基基基于于于于其其其其

40、它它它它分分分分析析析析方方方方法法法法，满满满满分分分分为为为为C+C+C+C+。（3 3 3 3）加加加加分分分分因因因因素素素素：界界界界面面面面、错错错错误误误误处处处处理理理理、类类类类型型型型处处处处理理理理、采采采采用用用用拉拉拉拉链链链链回填技术等回填技术等回填技术等回填技术等31两种自底向上分析方法：两种自底向上分析方法：两种自底向上分析方法：两种自底向上分析方法：（1 1 1 1）基于）基于）基于）基于L L L L属性定义，特别考虑属性定义，特别考虑属性定义，特别考虑属性定义，特别考虑 嵌入语义动作的处理嵌入语义动作的处理嵌入语义动作的处理嵌入语义动作的处理l l引入标记

41、非终结符号引入标记非终结符号引入标记非终结符号引入标记非终结符号MM和规则和规则和规则和规则MM，将原语义动作与规将原语义动作与规将原语义动作与规将原语义动作与规则则则则MM结合结合结合结合l l去掉原来的嵌入语义动作去掉原来的嵌入语义动作去掉原来的嵌入语义动作去掉原来的嵌入语义动作 继承属性的处理继承属性的处理继承属性的处理继承属性的处理l l用综合属性代替继承属性用综合属性代替继承属性用综合属性代替继承属性用综合属性代替继承属性32 :=:=:=:=dodododo whilewhilewhilewhile S SdodoSS1 1 whilewhileCCS S1 1C CL L1 1L

42、 L2 2Y YN NS.S.nextnextS SdodoMM1 1SS1 1 whilewhileMM2 2CC?S.nextS.nextdodoMM1 1C.trueC.trueC.true=C.true=newLabelnewLabel();();emit(labelC.true);emit(labelC.true);S S1 1.nextnext=newlabelnewlabel()();S S1 1.next.nextMM1 1-33S S1 1C CL L1 1L L2 2Y YN NS.S.nextnextS SdodoMM1 1SS1 1 whilewhileMM2 2CC?

43、S.nextS.nextdodoMM1 1C.trueC.trueS S1 1.next.nextS S1 1whilewhileMM2 2MM2 2-C.trueC.trueC.falseC.falseC.true=stacktop-3.true;C.true=stacktop-3.true;emit(labelstacktop-3.next);emit(labelstacktop-3.next);C.false=stacktop-5.nextC.false=stacktop-5.next;34两种自底向上分析方法：两种自底向上分析方法：两种自底向上分析方法：两种自底向上分析方法：（2 2

44、2 2）拉链回填）拉链回填）拉链回填）拉链回填S S1 1C CL L1 1L L2 2Y YN NS.S.nextlistnextlistS SdodoMM1 1SS1 1 whilewhileMM2 2CC backpatchbackpatch(S(S1 1.nextlistnextlist,M,M2 2.instrinstr););backpatchbackpatch(C.(C.truelisttruelist,M,M1 1.instrinstr);S S.nextlist nextlist=C.=C.falselist falselist MMM.M.instrinstr=nextinstrnextinstr;35