编译原理部分课后答案,仅供参考要点

1、埠程序1.3高级语言解释系统为了实现在一个计算机上运行高级语言的程序，主要有两个途径：第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。第二个途径是编写一 个程序，它解释所遇到的高级语言程序中的语句并且完成这些 语句的动作，这样的程序就叫解释程序。从功能上说，一个解 释程序能让计算机执行高级语言。它与编译程序的主要不同是第一章编译程序概述1.1 什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多 数计算机系统都含有不止一个高级语言的编译程序。对有些高 级语言甚至配置了几个不同性能的编译程序。1.2 编译过程概述和编译程序的结构编译程序完成从源程序到

2、目标程序的翻译工作，是一个复 杂的整体的过程。从概念上来讲，一个编译程序的整个工作过 程是划分成阶段进行的，每个阶段将源程序的一种表示形式转 换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连 接在一起的。一般一个编译过程划分成词法分析、语法分析、 语义分析、中间代码生成，代码优化和目标代码生成六个阶段 ， 这是一种典型的划分方法。事实上，某些阶段可能组合在一起， 这些阶段间的源程序的中间表示形式就没必要构造出来了。我 们将分别介绍各阶段的任务。另外两个重要的工作：表格管理 和出错处理与上述六个阶段都有联系。编译过程中源程序的各 种信息被保留在种种不同的表格里，编译各阶段的工作都涉及 到构

3、造、查找或更新有关的表格，因此需要有表格管理的工作； 如果编译过程中发现源程序有错误，编译程序应报告错误的性 质和错误发生的地点，并且将错误所造成的影响限制在尽可能 小的范围内，使得源程序的其余部分能继续被编译下去，有些 编译程序还能自动校正错误，这些工作称之为出错处理。 图1.3表示了编译的各个阶段。图1.3编译的各个阶段它不生成目标代码，它每遇到一个语句，就要对这个语句进行 分析以决定语句的含义，执行相应的动作。右面的图示意了它 的工作机理第二章：pl/0编译程序问答第1题 pl/0语言允许过程嵌套定义和递归调用，试问 它的编译程序如何解决运行时的存储管理。答：pl/0语言允许过程嵌套定义

4、和递归调用，它的编译程序在运行时采用了栈式动态存储管理。(数组code存放的只读目标程序，它在运行时不改变。)运行时的数据区s是由解释程序 定义的一维整型数组，解释执行时对数据空间s的管理遵循后进先出规则，当每个过程(包括主程序)被调用时，才分配数据 空间，退出过程时，则所分配的数据空间被释放。应用动态链 和静态链的方式分别解决递归调用和非局部变量的引用问题。问答第2题 若pl/0编译程序运行时的存储分配策略采用栈 式动态分配，并用动态链和静态链的方式分别解决递归调用和 非局部变量的引用问题，试写出下列程序执行到赋值语句 b： =10时运行栈的布局示意图。var x,y; procedure

5、p; var a; procedure q; var b; begin (q) b： =10; end (q); procedure s; var c,d; procedure r; var e,f;begin (r)call q; end (r); begin (s) call r; end (s);begin (p)call s; end (p); begin (main)call p; end (main).答：程序执行到赋值语句b： =10时运行栈的布局示意图为：问答第3题写出题2中当程序编译到r的过程体时的名字表 table的 内容。namekindlevel/valadrsize答

6、 题2中当程序编译到r的过程体时的名字表table的内 容为：namekindlevel/valadrsizexvariable0dxyvariable0dx+1pprocedure0过程p的入口（待填）5avariable1dxqprocedure1过程q的入口4sprocedure1过程s的入口（待填）5cvariable2dxdvariable2dx+1procedure2过程r的入口5evariable3dxvariable3dx+1注意：q和s是并列的过程，所以 q定义的变量b被覆盖。 问答第4题指出栈顶指针t,最新活动记录基地址指针 b,动态链指针 dl,静态链指针sl与返回地址r

7、a的用途。答：栈顶指针t,最新活动记录基地址指针 b,动态链指针dl,静态链指针sl与返回地址ra的用途说明如下：t:栈顶寄存器t指出了当前栈中最新分配的单元 （t也是 数组s的下标）。b:基址寄存器，指向每个过程被调用时，在数据区 s中给 它分配的数据段起 始 地址，也称基地址。sl:静态链，指向定义该过程的直接外过程（或主程序） 运行时最新数据段的基地址，用以引用非局部（包围它的过程） 变量时，寻找该变量的地址。dl:动态链，指向调用该过程前正在运行过程的数据段基 地址，用以过程执行结束释放数据空间时，恢复调用该过程前 运行栈的状态。ra 返回地址，记录调用该过程时目标程序的断点，即调 用

8、过程指令的下一条指令的地址，用以过程执行结束后返回调 用过程时的下一条指令继续执行。在每个过程被调用时在栈顶分配3个联系单元，用以存放sl, dl, rao问答第5题pl/0编译程序所产生的目标代码是一种假想栈式计算机的 汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。 int 0 a opr 0 0 calla答： pl/0编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条指令在code中的位置和功能以及所完成的操 作说明如下：int 0 a在过程目标程序的入口处， 开辟a个单元的数据段。a为局 部变量的个数+3。opr 0 0在过程目标程序的出口处，释放数据段（退栈）

9、，恢复调用该过程前正在运行的过程的数据段基址寄存器b和栈顶寄存器t的值，并将返回地址送到指令地址寄存器p中，以使调用前的程序从断点开始继续执行。cal l a调用过程，完成填写静态链、动态链、返回地址，给出被 调用过程的基地址值，送入基址寄存器b中，目标程序的入口地址a的值送指令地址寄存器 p中，使指令从a开始执行。 问答第6题给出对pl/0语言作如下功能扩充时的语法图和ebnf的语法描述。（1）扩充条件语句的功能使其为：if 条件then语句else 语句（2）扩充repeat语句为：repeat 语句；语句until 条件答： 对pl/0语言作如下功能扩充时的语法图和ebnf的语法描述如下

10、：（1）扩充条件语句的语法图为：ebnf的语法描述为：条件语句:=if条件then语句else 语句（2）扩充repeat语句的语法图为：ebnf勺语法描述为：重复语句二=repeat语句;语句until条件第三章：词法分析程序问答第1题构造正规式切”相应的dfa.答：先构造nfa用子集法将nfa确定化01xaaaababacabacpaabyabyacab除x, a外，重新命名其他状态，令 ab为b ac为c aby为d, 因为d含有y （nfa勺终态），所以d为终态。quvquzvzzzvz.quzvzquzzzz重新命名状态子集，令 vq为a qu为b、vz为c、v为d quz 为e、z

11、为f。.01sabacbbdecffdf.ecefffdfa的状态图:16dfa的状态图:问答第3题0j将下图确定化:将下图的（a）和（b）分别确定化和最小化:01svqquvqvzqu解：用子集法将nfa确定化:解:(b)初始分划得3444n0:终态组0,非终态组1,2,3,4,5对非终态组进行审查：1,2,3,4,5a ，二0,1,3,5而0,1,3,5 既不属于0,也不属于1,2,3,4,5 4 a 仁0,所以得到新分划ni: 0 , 4 , 1,2,3,5x1,2,3,5进行审查：1,5 b .二42,3 b 仁1,2,3,5,故得到新分划n2: 0 , 4 , 1,5 , 2,31,

12、5 a，二1,52,3 a 匚1,3,故状态2和状态3不等价，得到新分划n3: 0 , 2 , 3 , 4 , 1,5这是最后分划了最小dfadfa的状态图:可将该dfag小化：终态组为1,2,4,非终态组为3 , 1,2,40 1,2,41,2,41 3,所以1,2,4为等价状态，可合并。问答第4题构造一个dfa它接收2 =0,1上所有满足如下条件的字 符串：每个1都有0直接跟在右边。并给出该语言的正规式。 解：按题意相应的正规表达式是 (0*10)*0* ，或0*(0 | 10)*0*构 造相应的dfa首先构造nfa为用子集法确定化:i0i1x,0,1,3,y0,1,3,y20,1,3,y

13、0,1,3,y221,3,y1,3,y j1,3,y2 1重新命名状态集:s01123223第四章文法和语言问答第1题写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头；(2)不允许0打头。答：(1)允许0开头的偶正整数集合的文法nt|d nt|dn d|1|3|5|7|9d 0|2|4|6|8(2)不允许0开头的偶正整数集合的文法nt|dtf ft|gn d|1|3|5|7|9d 2|4|6|8ff n|0g d|0问答第2题证明下述文法g表达式是二义的。表达式二=a|(表达式)| 表达式运算符表达式运算符二=+| -|*|/答：可为句子a+a*a构造两个不同的最右推导：最右推导1

14、表达式表达式运算符表达式表达式运算符a(2)aa|b表达式* a屋 bb|c表达式运算符表达式* accc| e=表达式运算符a * a问答第6题表达式+ a * a给出下述文法所对应的正规式：=a + a * a腔 0a|1b最右推导2 表达式表达式运算符表达式21s|1表达式运算符表达式运算- 0s|0符表达式答： r = (01 | 10) ( 01 | 10 )*表达式运算符表达式运算第五章 自顶向下语法分析方法符a问答第1题表达式运算符表达式* a对文法gs=表达式运算符a * aa| a |(t)表达式+ a * atf t,s|s=a + a * a(1)给出(a,(a,a) 和

15、(a,a), a ,(a),a)的最左推导。问答第3题(2)对文法g进行改写，然后对每个非终结符写出不带回令文法ge为:溯的递归子程序。t|e+t|e -t(3)经改写后的文法是否是ll(1)的？给出它的预测分析t- f |t*f|t/f表。f- (e)|i(4)给出输入串(a,a)#的分析过程，并说明该串是否为证明e+t*f是它的一个句型，指出这个句型的所有短语、的句子。直接短语和句柄。答：文法-e+t _ e + _ * fg答：因为存在推导序列：ee+t*f是文法ge的一个句型句型e+t*f的短语有：e+t*f,t*f直接短语有：t*f句柄为：t*f问答第4题给出生成下述语言的上下文无关

16、文法:(1) a nbnambml n , m=0(2) 1 n0m 1m0n| n , m=0答：(1)sh aaaab| (2)sh 1s0|aat 0a1| 问答第5题给出生成下述语言的三型文法：(1) a nbm|n,m=1 (2)a nbmck|n,m,k=0 答：(1)s aaaa|bbk bb|b所以腔a| a |(t)tf t,s|s(1) x(a,(a,a)的最左推导为：s ： (t)- (t,s)- (s,s)一(a,s)(a,(t)一 (a,(t,s)-(a,(s,s)-(a,(a,s)-(a,(a,a)x(a,a),a ,(a),a) 的最左推导为s ： (t)一 (t

17、,s)一 (s,s)一 (t),s)- (t,s),s)(t,s,s),s)一(s,s,s),s)一 (t),s,s),s)-(t,s),s,s),s)=-(s,s),s,s),s) 一(a,s),s,s),s) _ (a,a),s,s),s) =(a,a),a,s),s)=o(a,a),a,(t),s)=o(a,a),a,(s),s)二(a,a),a,(a),s)二(a,a),a,(a),a)(2)改写文法为：0) sfa1) sfa2) sf t )3) t fs n4) nf, s n5) n f e非终结 符fst 集followsa, a,(#,)ta, a,().n, e .).对

18、左部为n的产生式可知：first (f, s n ) = , first (f ) = follow/ (n) =)由于 select(nf, s n)hselect(n - ) = , n )= 0也可由预测分析表中无多重入口判定文法是ll(1)的(3)对输入串(a,a) #的分析过程为：栈(stack当前输入符(cur_char剩余输入符(inout_string所用产生式(operation#sia,a)#.#)t(a,a)#腔(t)#)ta,a)#.#)nsa,a)#tf sn#)na#)na,a)#.a)#.sra .#)ns,a)#.n ,sn#)nsa)#.1 .#)naa)#.

19、sra#)n)#.#)#.n #可见输入串(a,a) #是文法的句子问答第2题已知文法gs:腔 mh|also| eqdml| lfehfmr k|blm判断g是否是ll(1)文法，如果是，构造 ll(1)分析表 答：文法：腔 mh|also| eqdml| lfehfmr k|blm展开为：0)腔 m h1) sra2) h l s o3) h e4) q d m l5) k e6) lfe h f7) mr k8) mr b l m非 终 结 符first 用follow!sa,d,b, ,e#,o.md, &且e,#,oh ,e#,f,olea,d,b,e,o,#kd, e e,#,o对

20、相同左部的产生式可知:select(sm h)n select(sa) = d,b ,e , #,o n a =0select(hl s o) n select什 ) = e n #,f,o =0select(kd m l) n select(伶 ) = d n e,#,o =0aodefb#s-afmhmhfmhfmhfmhm-k-k-kfblm-khf &flsof &lfehfkfdmlselect(mk) n select(mb l m) = d , e,#,o n b = 所以文法是ll(1)的。预测分析表(predicting analysis table )由预测分析表中无多重人

21、口也可判定文法是ll(1)的。问答第3题对于一个文法若消除了左递归，提取了左公共因子后是否 一定为ll(1)文法？试对下面文法进行改写，并对改写后的文法 进行判断。(1) a -aabe|abk bb|d(3) s -aa|b2sb屋ab答：(1)文法：2 aabe|a屋 bb|d提取左公共因子和消除左递归后文法变为：0) a-a n1) nfa b e2) n f e3) bfd n14) n1 -b n15) n1 - e非终结符firstfollowaa.#,dbde.n ja, e #,dn1b, & e.对相同左部的产生式可知：select(na b e) n select时 ) =

22、 a n #,d =0select(n1b n1) n select(n1 ) = b n e =0所以文法是ll(1)的。预测分析表(predicting analysis table )aebd#afa nb-d也可由预测分析表中无多重入口判定文法是ll(1)的(2)文法：腔 aa|b2sb屋ab第1种改写：用a的产生式右部代替 s的产生式右部的 a得：般 sba|b屋ab消除左递归后文法变为：0) s fb n1) nfb a n2) n - 3) b -a b非终 结符first集follow集sb#ba.an e ,a#对相同左部的产生式可知：select(nb a n) n sel

23、ect时 ) = a n # = 0所以文法是ll(1)的。预测分析表(predicting analysis table )ab#s-bnb7abn-ba n也可由预测分析表中无多重入口判定文法是ll(1)的第2种改写：用s的产生式右部代替 a的产生式右部的s得：腔 aa|baab|bb屋ab消除左递归后文法变为：0) s f a a1) sfb非终碧符frstfollow集sb#ababa.a匚a, e a(2) 算符优先关系表(operater priority relation table2) afb b n3) n fa b n4) n f e5) b -a b对相同左部的产生式可知

24、：select(sa a) n select(sb) = b n b = b 丰0select(na b n) nselect时 ) = a n a = a 丰必所以文法不是ll(1)的。预测分析表(predicting analysis table )也可由预测分析表中含有多重入口判定文法不是ll(1)的。第六章算符优先分析法问答第1题已知文法g网为:a| a|(t)tf t,s|s 计算 gs的 firstvt和 lastvt(2)构造gs的算符优先关系表并说明gs是否为算符优先文法。(3)给出输入串(a,a)#和(a,(a,a)# 的算符优先分析过 程。答：文法：腔a| a |(t)tf

25、 t,s|s展开为：s asha腔(t)tf t,stf s(1) firstvt - lastvt 表非终 结符firstvt集lastvt集s a a (. aa ) .t a a(, aa ) , a1(),#a.,a.(),.#_6表中无多重人口所以是算符优先(opg文法。(3)对输入串(a,a) #的算符优先分析过程为栈当前输剩余输入串动 作(s入字符(input s(actiontac(charring)k)#a,a)#move in#(,a)#move in#(aaa)#.reduce:#(na)#.sra#(n,)#.move in,#.move ina#(n)#.reduce

26、:,a)#.sra#(n)reduce:,n#tf t,s#(nmove in#(nreduce:)腔(t)#nsuccess!对输入串(a,(a,a) ) #的算符优先分析过程为:栈(stac)当前字符 k(chr)剩余输入串(input string动作.(action#(#(a#(n #(n, #(n,( #(n,(a #(n,(n #(n,(n #(n,(n, a#(n,(n, n#(n,(n #(n,(n) #(n,n #(n #(n)#na, aa#a,(a,a) #.,(a,a)#.(a,a)#.(a,a)#.a,a)#.,a)# a)#. a)#.)#.)#.)#.)#.#.#

27、.#.move in move inreduce:sramove inmove in move inreduce:sramove inmove inreduce:srareduce:tf t,s move inreduce: 腔(t)reduce: tf t,smove inreduce: 腔(t)success!问答第2题对题1的gs(1)给出(a,(a,a)和(a,a)的最右推导，和规范归约过程。(2)将(1)和题1中的(3)进行比较给出算符优先归约和规 范归约的区别。答：文法：腔a| a |(t)tf t,s|sx(a,a )和(a,(a,a)的最右推导:(a,a )的最右推导过程为：s

28、 ： (t)-(t,s)-(t,a)一 (s,a)一(a,a)(a,(a,a)的最右推导过程为：s ： (t)_ (t,s)_ (t,(t)-(t,(t,s)-(t,(t,a)一(t,(s,a)-(t,(a,a)-(s,(a,a)一(a,(a,a)success!(4)对输入串(a,(a,a) ) #的规范归约过程为:对输入串(a,a ) #的规范归约过程为:栈(stack )剩余输入 串(inputleft )动作(action )#(#( a#( s#( t#( t,#( t,a#( t,s#( t#(t)#s(a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.)#.)#.)#

29、.#.#.shiftshiftreduceby :s fareduce by :t fsshiftshiftreduce by :s fareduce by :t ft,sshiftreduce by :s - (t)栈(stack )剩余输入串(input left )动(action作)#(a,(a,a)#.shift#(a,(a,a)#.shift#( a,(a,a)#.reduce#( s,(a,a)#.by :s #( t,(a,a)#.reduce#( t,(a,a)#.by :t fs#( t,( ja,a)#.shift#( t,(a,a)#shift#( t,(s,a)#sh

30、ift#( t,(t,a)#reduce#( t,(t,a)#.by :s fa#( t,(t,a)#.reduce#( t,(t,s)#.by :t fs#( t,(t)#.shift#( t,(t)#.shift#( t,(s)#.reduce#( t)#.by :s fa#( t)#.reduce#s#.by :t ftsshiftreduce by :s - (t)reduce by :t ft, sshiftreduce by :s - (t)success!第七章lr分析法问答第1题已知文法2 aad|aab| e判断该文法是否是 slr(1)文法，若是构造相应分析表，并 对输入串

31、ab#给出分析过程。答：文法：2 aad|aab| e拓广文法为g ,增加产生式s f若产生式排序为：0s fa1 a faad2 a faab3 a 6由产生式知：first (s ) = ,afirst (a ) = e ,afollow(s ) = #follow(a ) = d,b,#g的lr(0)项目集族及识别活前缀的dfa如下图所示：在i 中:a faad和a f.aab为移进项目，a f 为归约项目，存在移进-归约冲突，因此所给文法不是lr(0)文法。在i。、12中：follow(a) na= d , b, # na=。所以在i。、12中的移进-归约冲突可以由follow集解决，

32、所以g是slr(1)文法。构造的slr(1)分析表如下：题目1的slr(1)分析表状态(state )actiongotoadab#s2r31r3r3.30acc1s2r32r3r33s4s54r15r1r1r2r2r2题目1对输入串ab#的分析过程状态栈(state stack )文法 符号栈剩余输 入串(inputleft )动作(action )00 20 2 30 2 30 1#a#aa#aab#aab#.b#.b#.#.#.shiftreduce by :a - shiftreduce by :a faab分析成功，说明输入串ab是题目1文法的句子问答第2题若有定义二进制数的文法如下

33、：sh l.l|llf lb|bbk 0|1(1)试为该文法构造lr分析表，并说明属哪类lr分析表(2)给出输入串101.110的分析过程。答：文法：sh l.l|llf lb|b-0|1拓广文法为g ,增加产生式s - s若产生式排序为：0 s fs1 s fl.l2 s fl3 l flb4 l fb5 b f06 b f1由产生式知：first (s ) = 0,1first (s ) = 0,1first (l ) = 0,1first (b ) = 0,1follow(s ) = #follow(s ) = #follow(l ) = .,0,1,#follow(b ) = .,0,

34、1,#g的lr(0)项目集族及识别活前缀的dfa如下图所示：在i 2中:b f.0和b f.1为移进项目，s fl.为归约项目，存在移进 - 归约冲突，因此所给文法不是lr(0)文法。在i 2、i 8中:follow(s) n0, 1= # n0,1=。所以在i2、i 8中的移进-归约冲突可以由follow集解决，所以g是slr(1)文法。构造的slr(1)分析表如下：题目2的slr(1)分析表状态(state )actiongoto0sl1#bs4s5123acc.s6s40s5r271r4r4.2r4r4.3r5r5.4r5r585r6r636r6r6.7s4s58r3r37r3r3s4s

35、5r1题目2对输入串101.110#的分析过程状态栈文法符号剩余输入串动作(state(input(action )栈stack )left )0#101.110#.shift0 5#101.110#.reduce0 3#b01.110#.by :b -10 2#l01.110#.reduce0 2 4#l01.110#.by :s flb0 2 7#lb1.110#.shift0 2#l1.110#.reduce0 2 5#l1.110#.by :b f00 2 7#lb.110#.reduce0 2#l.110#.by :s flb0 2 6#l.110#.shift0 2 6 5#l.1

36、10#.reduce0 2 6 30 2 6 8#l.b#l.l10#.10#.by :b -1reduce0 2 6 8 5#l.l10#.by :s flb0 2 6 8 7#l.lb0#.shift0 2 6 8#l.l0#.shift0 2 6 8 4#l.l0#.reduce0 2 6 8 7#l.lb#.by :b -10 1#s#.reduce by :s fb shift reduce by :b -1 reduce by :s flb shift reduce by :b f0 reduce by :s fl.l分析成功，说明输入串101.110是题目2文法的句子。问答第3题

37、文法 g=(u,t,s,a,b,c,d,e,p,s)其中p为：般 uta|tbtf s|sc|du us|e(1)判断 g 是 lr(0) , slr(1) , lalr(1)还是 lr(1),说明 理由。(2)构造相应的分析表。答：文法：般 uta|tbtf s|sc|du us|e拓广文法为g,增加产生式s-s若产生式排序为：0s-s1s-uta2s-tb3t fs4t fsc5t fd6u fus7u二e由产生式知:first (s ) = d,efirst (s ) = d,efirst (u ) = efirst (t ) = d,efollow(s ) = #follow(s )

38、= a,b,c,d,e,#follow(u ) = d,efollow(t) = a,bg的lr(0)项目集族及识另1j活前缀的dfa如下图所示:在11中：s -s.为接受项目，t -s.为归约项目，t -s.c为移进项目， 存在接受-归约和移进-归约冲突，因此所给文法不是lr(0)文法。在i1中：follow(s) n follow(t)= # na ,b=0follow(t) n c= a , b nc= 0在i 8中:follow(u) n follow(t)n c=d,en a , b nc=0所以在i 1中的接受-归约和移进-归约冲突与i 8中的移进-归约和 归约-归约冲突可以由fo

39、llow集解决，所以g是slr(1)文法。 构造的slr(1)分析表如下：题目3的slr(1)分析表状态actiongoto(state )abcdes u#t0s5 s41 21r3r3s6)32acc.3s5 s48 2s9r7 r7r5r5r49 r410 s10s9r3 r3. s6r6r2r2.r2r2r2rir1.riririr6r2ri在i 中:问答第4题证明文法:腔a$babb|dbdab- d 是lr(i)但不是slr(i)。(其中$相当于#)b -.,a和t -. , b为归约项目，但它们的搜索符不同，若当 前输入符为a时用产生式b - 归约，为b时用产生式d - 归约，所

40、以该文法是 lr(i)文法。若不看搜索符，在i。中项目b -.和t -.为归约-归约冲突， 而follow(b ) n follow(d ) = a,b na,b丰 0,冲突不能用 follow集解决，所以该文法不是slr(i)文法。构造的lr(i)分析表如下：答：文法:babb|dbdab d 拓广文法为g ,增加产生式s f若产生式排序为：0s faiafbabb2 afdbda3 bf 64 d &由产生式知：first (s ) = a,bfirst (a ) = a,bfirst (b ) = first (d ) = follow(s ) = #follow(a ) = #foll

41、ow(b) = a,bfollow(d) = a,bg的lr(i)项目集族及识别活前缀的dfa如下图所示:题目4的lr(i)分析表stateactiongotoa .b .#abdr3r4.i20acc3is4.2s5.3r3.4r4.65s86s9.778ri9r2问答第5题给定文法：腔do s or s|do s|s;s|act(i)构造识别该文法活前缀的dfa(2)该文法是lr(0)吗？是slr(1)吗？说明理由。(3)若对一些终结符的优先级以及算符的结合规则规定如下：a) or 优先性大于do;b);服从左结合；c);优先性大于do ;d);优先性大于or ;请构造该文法的lr分析表，

42、并说明lr(0)项目集中是否存在 冲突和冲突如何解决的。答：首先化简文法，用d代替do;用o代替or;用a代替act; 文法可写成：般 dsos|ds|s;s|a拓广文法为g,增加产生式s - s若产生式排序为：0 s fs1 s fdsos2 s fds3 s fs;s4 s fa由产生式知：first (s ) = d,afirst (s ) = d,afollow(s ) = #follow(s ) = o,;,#(1)识别该文法活前缀的 dfa如下图。(2)该文法不是lr(0)也不是slr(1)因为：在i 5、i6、和i 8中存在移进-归约冲突，因此所给文法不是lr(0)文法。又由于

43、follow(s ) = o, ;,#在i 6、和i 8中:follow(s ) n ; =o, ; ,# n ; =; 丰 0在i 5中：follow(s ) n ; , o =o , ; ,#n ; , o =; , o 0所以该文法也不是slr(1)文法。此外很容易证明所给文法是二义性的，因此该文法不可能满足lr文法，(3)若对一些终结符的优先级以及算符的结合规则规定如下：a) or 优先性大于do;b);服从左结合；c);优先性大于do ；d);优先性大于or ；则在i 5中：or和；优先性都大于do,所以遇输入符。和；移 进；遇#号归约。在i 6中：；号服从左结合所以遇输入符属于 follow(s )的都 应归约。在18中：；号优先性大于or 所以遇输入符为；号 移进；遇 o和#号归约。此外，在i1中：接受和移进可以不看成冲突，因为接受只有遇#号。由以上分析，所有存在的移进-归约冲突可用规定的终