编译原理试题库_计算机-linux-Unix相关.pdf

《编译原理试题库_计算机-linux-Unix相关.pdf》由会员分享，可在线阅读，更多相关《编译原理试题库_计算机-linux-Unix相关.pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.-.word.zl-第一章 什么是编译器？编译程序的构造分为几个阶段，各阶段的任务是什么？遍、编译前端及编译后端的含义？编译程序的生成方式有哪些？第二章 1.写一文法，使其语言是偶正整数的集合。要求：1允许 0 打头2 不允许 0 打头 解：1允许 0 开头的偶正整数集合的文法 ENT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8 2不允许 0 开头的偶正整数集合的文法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|0 2.证明下述文法 G 表达式 是二义的。表达式=a|(表达式)|表达式 运算符 表达式 运算符=+|-|*|/解：可为

2、句子 a+a*a 构造两个不同的最右推导:最右推导 1 表达式表达式 运算符 表达式 表达式 运算符a 表达式*a 表达式 运算符 表达式*a 表达式 运算符a *a 表达式+a*a a+a*a 最右推导 2 表达式表达式 运算符 表达式 表达式 运算符 表达式 运算符 表达式 表达式 运算符 表达式 运算符 a 表达式 运算符 表达式*a 表达式 运算符a *a 表达式+a*a a+a*a 3.给出生成下述语言的上下文无关文法：1 anbnambm|n，m=0 2 1n0m1m0n|n，m=0 解：1 anbnambm|n，m=0 SAA AaAb|.-.word.zl-(2)1n0m1m0

3、n|n，m=0 S1S0|A A0A1|第三章 1、构造一个 DFA，它接收=a,b 上所有满足下述条件的字符串：字符串中的每个 a 都有至少一个 b 直接跟在其右边。解：=a,b，根据题意得出相应的的正规式为：(b*abb*)*根据正规式画出相应的 DFA M，如以下图所示 用子集法将其确定化 I Ia Ib X,1,2,3,Y 4 2,3 4 5,6,1,2,3,Y 2,3 4 2,3 5,6,1,2,3,Y 4 6,1,2,3,Y 6,1,2,3,Y 4 6,1,2,3,Y 由 DFA 得状态图 用最小化方法化简得：0，1，2，3,4，按顺序重新命名 DFA M 第四章 练习 1：文法

4、GV：VN|NE EV|V+E Ni 是否为 LL(1)文法，如不是，如何将其改造成 LL(1)文法。解：LL(1)文法的根本条件是不含左递归和回溯公共左因子，而 GV中含有回溯，所以先消除I Ia Ib 0 1 2 1 3 2 1 2 3 1 4 4 1 4 X Y(b*abb*)*X Y b*abb*1 X Y b 1 2 3 4 5 6 b b a 1 0 2 4 3 a a a a b b b b b 0 3 1 2 a a a b b b 式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法

5、表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-回溯得到文法 GV：GV：VNV V|E EVE E|+E Ni 由 LL(1)文法的充要条件可证 GV是 LL(1)

6、文法 练习 2：有文法 Gs:SBA ABS|d BaA|bS|c(1)证明文法 G 是 LL(1)文法。(2)构造 LL(1)分析表。(3)写出句子 adccd的分析过程 解：(1)一个 LL(1)文法的充要条件是：对每一个非终结符 A 的任何两个不同产生式 A|，有下面的条件成立：FIRST()FIRST()=;假设*,那么有 FIRST()FOLLOW(A)=对于文法 Gs:SBA ABS|d BaA|bS|c 其 FIRST 集如下：FIRST(B)=a,b,c;FIRST(A)=a,b,c,d;FIRST(S)=a,b,c。其 FOLLOW 集如下：首先，FOLLOW(S)=#;对

7、SBA 有：FIRST(A)参加 FOLLOW(B),即 FOLLOW(B)=a,b,c,d;对 ABS 有：FIRST(S)参加 FOLLOW(B),即 FOLLOW(B)=a,b,c,d;对 BaA 有：FOLLOW(B)参加 FOLLOW(A),即 FOLLOW(A)=a,b,c,d;对 BbS 有：FOLLOW(B)参加 FOLLOW(S),即 FOLLOW(S)=#,a,b,c,d;由 ABS|d 得：FIRST(BS)FIRST(d)=a,b,c d=;由 BaA|bS|c 得：FIRST(aA)FIRST(bS)FIRST(c)=a b c=。由于文法 Gs不存在形如 的产生式，

8、故无需求解形如FIRST()FOLLOW(A)的值。也即，文法 GS是一个 LL(1)文法。(2)由 Gs:SBA ABS|d BaA|bS|c 的 FIRST(B)=a,b,c;FOLLOW(B)=a,b,c,d;FIRST(A)=a,b,c,d;FOLLOW(A)=a,b,c,d;FIRST(S)=a,b,c。FOLLOW(S)=#,a,b,c,d 可构造 LL(1)预测分析表如下：a b c d#S SBA SBA SBA A ABS ABS ABS Ad B BaA BbS Bc S SBA SBA SBA A ABS ABS ABS Ad B BaA BbS Bc 式有哪些第一章第二

9、章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.wor

10、d.zl-(3)在分析表的控制下，句子 adccd的分析过程如下：第五章 1 文法 GS为：Sa|(T)TT,S|S (1)计算 GS的 FIRSTVT 和 LASTVT。(2)构造 GS的算符优先关系表并说明 GS是否为算符优先文法。(3)给出输入串(a,(a,a)#的算符优先分析过程。解：文法：Sa|(T)TT,S|S 展开为：Sa S S(T)TT,S TS(1)FIRSTVT-LASTVT表 非终结符 FIRSTVT 集 LASTVT 集 S a (a )T a (,a ),(2)算符优先关系表如下:表中无多重入口所以是算符优先OPG 文法。a (),#a(),#栈当前输入符号输入串说

11、明#Sadccd#SBA#ABadccd#BaA#AAaadccd#AAdccd#Ad#Addccd#Accd#ABS#SBccd#Bc#Scccd#Scd#SBA#ABcd#Bc#Accd#Ad#Ad#dd#分析成功式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造

12、一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-(3)输入串a,(a,a)#的算符优先分析过程为：栈 当 前 字符 剩余输入串 动作#(#(a#(N#(N,#(N,(#(N,(a#(N,(N#(N,(N,#(N,(N,a#(N,(N,N#(N,(N#(N,(N)#(N,N#(N#(N)#N(a,(a,a)#a,(a,a)#,(a,a)#(a,a)#(a,a)#a,a)#,a)#a)#a)#)#)#)

13、#)#Move in Move in Reduce:SaMove in Move in Move in Reduce:Sa Move in Move in Reduce:Sa Reduce:TT,S Move in Reduce:S(T)Reduce:TT,S Move in Reduce:S(T)第六章 例 1：有文法：S(L)|a LL,S|S 给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号的个数。如对于句子(a,(a,a)，输出是 2。解：参加新开场符号 S和产生式 SS，设 num 为综合属性，代表值属性，那么语法制导定义如下：产生式 语义规那么 SS

14、print(S.num)S(L)S.num:=L.num+1 Sa S.num:=0 LL1,S L.num:=L1.num+S.num LS L.num:=S.num 例 2：构造属性文法，能对下面的文法，只利用综合属性获得类型信息。D L,id|L L T id T int|real 解：属性文法语法制导定义：产生式 语义规那么 D L,id D.type:=L.type addtype(id.entry,L.type)D L D.type:=L.type L T id L.type:=T.type addtype(id.entry,T.type)T int T.type:=integer

15、 T real T.type:=real 第七章 例 1：给出下面表达式的逆波兰表示(后缀式)：式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文

16、法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-(1)a*(-b+c)(2)if(x+y)*z=0 then s:=(a+b)*c else s:=a*b*c 解：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=￥注：￥表示 if-then-else 运算 例 2：请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列。解：三元式 间接三元式 (1)(+a,b)间接三元式序列 间接码表 (2)(+c,d)(1)(+a,b)(1)(3)(*(1),(2)(2)(+c,

17、d)(2)(4)(-(3),/)(3)(*(1),(2)(3)(5)(+a,b)(4)(-(3),/)(4)(6)(-(4),(5)(5)(-(4),(1)(1)(5)四元式 (1)(+,a,b,t1)(2)(+,c,d,t2)(3)(*,t1,t2,t3)(4)(-,t3,/,t4)(5)(+,a,b,t5)(6)(-,t4,t5,t6)例 3：请将以下语句 while(AD)then X:=Y+Z 翻译成四元式 解：假定翻译的四元式序列从100开场：100 if AD goto 104 103 goto 100 104 T=Y+Z 105 X=T 106 goto 100 107 例 4：

18、写出 for 语句的翻译方案 解：产生式 动作 S for E do S1 S.begin:=newlabel S.first:=newtemp S.last:=newtemp S.curr:=newtemp S.code:=gen(S.first“:=E.init)|gen(S.last“:=E.final)|gen(“if S.first“S.last“goto S.next)|gen(S.curr“:=S.first)式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式

19、表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-|gen(S.begin“:)|gen(“if S.curr“S.Last“goto S.next)|S1.code|gen(S.curr:=s

20、ucc(S.curr)|gen(“goto S.begin)E v:=initial to final E.init:=initial.place E.final:=final.place 第八章 例 1：C 语言中规定变量标识符的定义可分为 extern,extern static,auto,local static和 register五种存储类：(1)对五种存储类所定义的每种变量，分别说明其作用域。(2)试给出适合上述存储类变量的存分配方式。(3)符号表中登记的存储类属性，在编译过程中支持什么样的语义检查。解：(1)extern 定义的变量，其作用域是整个 C 语言程序。extern st

21、atic 定义的变量，其作用域是该定义所在的 C 程序文件。auto 定义的变量，其作用域是该定义所在的例程。local static 定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保存。register 定义的变量，其作用域与 auto 定义的变量一样。这种变量的值，在存放器有条件时，可存放在存放器中，以提高运行效率。(2)对 extern 变量，设置一个全局的静态公共区进展分配。对 extern static 变量，为每个 C 程序文件，分别设置一个局部静态公共区进展分配。对 auto 和 register 变量，设定它们在该例程的动态区中的相对区头的位移量。而例程

22、动态区在运行时再做动态分配。对 local static 变量，为每个具有这类定义的例程，分别设置一个部静态区进展分配。(3)实施标识符变量重复定义合法性检查，及引用变量的作用域围的合法性检查。第九章 例 1：下面的程序执行时，输出的 a 分别是什么？假设参数的传递方法分别为(1)传名；(2)传地址；(3)得结果；4)传值。program main(input,output);procedure p(x,y,z);begin y=y+1;z=z+x;end;begin a=2;b=3;p(a+b,a,a);print a end.解：(1)参数的传递方法为“传名时，a 为 9。式有哪些第一章第

23、二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.wo

24、rd.zl-(2)参数的传递方法为“传地址，a 为 8。(3)参数的传递方法为“得结果，a 为 7。(4)参数的传递方法为“传值，a 为 2。例 2：过程参数的传递方式有几种？简述“传地址和“传值的实现原理。解：参数的传递方式有下述几种：传值，传地址，传名，得结果“传值方式，这是最简单的参数传递方法。即将实参计算出它的值，然后把它传给被调过程。具体来讲是这样的：1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单元。2.调用过程计算实参的值，并将它们的右值r-value 放在为形式单元开辟的空间中。3.被调用过程执行时，就像使

25、用局部变量一样使用这些形式单元。“传地址方式，也称作传地址，或引用调用。调用过程传给被调过程的是指针，指向实参存储位置的指针。1.如实参是一个名字或是具有左值的表达式，那么左值本身传递过去。2.如实参是一个表达式，比方 a+b 或 2，而没有左值，那么表达式先求值，并存入某一位置，然后该位置的地址传递过去。3.被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。例 3：下面是一个 Pascal程序 program PP(input,output)var K:integer;function F(N:integer):integer begin if N=0 then

26、 F:=1 else F:=N*F(N-1);end;begin K:=F(10);.end;当第二次递归地进入 F 后，DISPLAY 的容是什么？当时整个运行栈的容是什么？解：第十章 例 1：何谓代码优化？进展优化所需要的根底是什么？式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文

27、无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-解：对代码进展等价变换，使得变换后的代码运行结果与变换前代码运行结果一样，而运行速度加快或占用存储空间减少，或两者都有。优化所需要的根底是在中间代码生成之后或目标代码生成之后。例 2：编译过程中可进展的优化如何分类？最常用的代码优化技术有哪些？解：依据优化所涉及的程序围，可以分为：局部优化、循环优化和全局优化。最常用的代码优化技术有

28、 1.删除多余运算 2.代码外提 3.强度削弱 4.变换循环控制条件 5.合并量与复写传播 6.删除无用赋值 例 3：试对以下根本块 B2：B：=3 D：=A+C E：=A*C F：=D+E G：=B*F H：=A+C I：=A*C J：=H+I K：=B*5 L：=K+J M：=L 应用 DAG 对它们进展优化，并就以下两种情况分别写出优化后的四元式序列：1假设只有 G、L、M 在根本块后面还要被引用。2假设只有 L 在根本块后面还要被引用。解：根本块对应的 DAG 如下：B：=3 D：=A+C E：=A*C F：=D+E G：=B*F H：=A+C I：=A*C J：=H+I K：=B*5

29、 L：=K+J M：=L 例 1 一个编译程序的代码生成要着重考虑哪些问题?解：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。课后习题答案：P36-6(1)L G()1是 09 组成的数字串(2)最左推导:NNDNDDNDDDDDDDDDDDDDNNDDDDNNDNDDDDDDDD0010120127334556568 最右推导:式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运

30、算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-NNDNNDNNDNDNNDNDNNDNNDND77272712712701274434886868568 P36-8 文法：ET ET ETTF TF TFFE i|*|/()

31、|最左推导:EETTTFTiTiTFiFFiiFii iETTFFFiFiEiETiTTiFTiiTiiFiii *()*()*()*()*()*()*()最右推导:EETETFET iEFiEi iTi iFi iii iETFTFFFEFETFEFFEiFTiFFiFiiiii *()*()*()*()*()*()*()*()语法树：/*EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*i P36-9 句子 iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiiei P647(1)1 01

32、101(|)*0 1 1 0 1 X 1 2 3 4 Y 5 X Y 式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法

33、解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-1 确定化：0 1 X 1,2,3 1,2,3 2,3 2,3,4 2,3 2,3 2,3,4 2,3,4 2,3,5 2,3,4 2,3,5 2,3 2,3,4,Y 2,3,4,Y 2,3,5 2,3,4 0 1 0 0 0 1 1 0 0 1 0 1 1 1 最小化：,012 34 56012 34 5135012 34 512 4 6012 3456012 34135012 3456012 310100 3012 312 4012 3 45601101122 332 34012 345610

34、101,0 1 0 0 1 0 0 1 0 1 1 1 P6412(a)a 6 0 1 2 3 5 4 5 0 1 2 4 3 式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺

35、序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-a,b a 确定化：a b 0 0,1 1 0,1 0,1 1 1 0 给状态编号：a b 0 1 2 1 1 2 2 0 3 3 3 3 a a a b b b b a 最小化：,012 30110122 30 32 330123abab a a b b a b(b)b b a a b 0 1 2 3 0 1 2 0 1 0 2 3 式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不

36、允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-a a b b a a a 已经确定化了,进展最小化 最小化：,0 12 3

37、4 50 110 12 42 3 4 51 3 0 52 3 4 52 3 4 52 41 02 43 53 53 53 52 40 12 43 50 110 12 42 4,abababababa,1 02 43 53 53 53 52 4 bab b b a a b a P811(1)按照 T,S 的顺序消除左递归|,)(|)(TSTTSTTaSSG 递归子程序：procedure S;begin if sym=a or sym=then abvance else if sym=(then begin advance;T;if sym=)then advance;else error;en

38、d else error end;procedure T;begin 1 4 5 0 1 2 式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法

39、如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-S;T end;procedure T;begin if sym=,then begin advance;S;T end end;其中:sym:是输入串指针 IP 所指的符号 advance:是把 IP 调至下一个输入符号 error:是出错诊察程序(2)FIRST(S)=a,(FIRST(T)=a,(FIRST(T)=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW(T)=)预测分析表 a (),#S Sa S ST()T TST TST TST T T T

40、ST,是 LL(1)文法 P812 文法：|)(|*|baEPFFFPFTTTFTEEETE(1)FIRST(E)=(,a,b,FIRST(E)=+,FIRST(T)=(,a,b,式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所

41、示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-FIRST(T)=(,a,b,FIRST(F)=(,a,b,FIRST(F)=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#(2)考虑以下产生式:EETTFFPE

42、a b|*|()|FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T)=(,a,b,+,),#=FIRST(*F)FIRST()=*=FIRST(*F)FOLLOW(F)=*(,a,b,+,),#=FIRST(E)FIRST(a)FIRST(b)FIRST()=所以,该文法式 LL(1)文法.(3)+*()a b#E ETE ETE ETE ETE E EE E E T TFT TFT TFT TFT T T TT T TT TT TT T F FPF FPF FPF FPF F

43、F FF*F F F F F F P PE()Pa Pb P (4)procedure E;begin if sym=(or sym=a or sym=b or sym=then begin T;E end else error end 式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文

44、无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-procedure E;begin if sym=+then begin advance;E end else if sym)and sym#then error end procedure T;begin if sym=(or sym=a or sym=b or sym=then begin F;T end else error

45、end procedure T;begin if sym=(or sym=a or sym=b or sym=then T else if sym=*then error end procedure F;begin if sym=(or sym=a or sym=b or sym=then begin P;F end else error end procedure F;begin if sym=*then begin advance;F end end procedure P;begin if sym=a or sym=b or sym=then advance else if sym=(t

46、hen begin advance;E;if sym=)then advance else error 式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法

47、是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-end else error end;P1331 EETETF *短语:E+T*F,T*F,直接短语:T*F 句柄:T*F P1332 文法：SaTTT S S|(),|(1)最左推导:STT SS Sa SaTaT SaS Saa Saa aST SS STST SST S SSS S SSTS SST SS SSS SS SSa S()(,)(,)(,)(,()(,(,)(,(,)(,(,)(,(,)(,)(,)(),)(,),)(,),)(,),)(),),

48、)(,),),)(,),),)(,),),)(,),),)(,),),)(,),(),)(,),(),)(,),(),)(,),(),)S SSa aS SSa aSSa aTSa aSSa aaSa aaa 最右推导:STT STTTT STT aTS aTa aSa aaa aST ST aS aTaT SaTTaTSaTaaT SaaTaa()(,)(,()(,(,)(,(,)(,(,)(,(,)(,(,)(,(,)(,)(,)(,)(),)(,),)(,(),)(,(),)(,(),)(,(),)(,(),)(,(),)(),(),)(,),(),)(,),(),)(,),(),)(,

49、),(),)SaaTaaT SaaT aaaS aaaa aaa(2)(a,a),(a),a)(S,a),(a),a)(T,a),(a),a)(T,S),(a),a)(T),(a),a)(S,(a),a)(T,(a),a)(T,S,(a),a)(T,(a),a)(T,(S),a)(T,(T),a)(T,S),a)(T),a)(S,a)(T,S)(T)S 式有哪些第一章第二章写一文法使其语言是偶正整数的集合要求允许打头不允许打头解允许开头的偶正整数集合的文法不允许开头的偶正整数集合的文法证明下述文法表达式是二义的表达式表达式表达式运算符表达式运算符解可为式运算符表达式最右推导表达式表达式运算符表

50、达式表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式运算符表达式表达式运算符表达式给出生成下述语言的上下文无关文法解第三章构造一个它接收上所有满足下相应的如以下图所示用子集法将其确定化由得状态图用最小化方法化简得按顺序重新命名第四章练习文法是否为文法如不是如何将其改造成文法解文法的根本条件是不含左递归和回溯公共左因子而中含有回溯所以先消除回溯得到文.-.word.zl-“移进-归约过程：步骤 栈 输入串 动作 0#(a,a),(a),a)#预备 1#(a,a),(a),a)#进 2#(a,a),(a),a)#进 3#(a,a),(a),a)#进 4#(a ,a),(a),a)#进