计算机编译原理课后习题及答案详细解析.pdf

《计算机编译原理课后习题及答案详细解析.pdf》由会员分享，可在线阅读，更多相关《计算机编译原理课后习题及答案详细解析.pdf（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机编译原理课后习题及答案详细解析在此深情而热烈的感谢沈仲秋同学的大力支持和帮助，同时希望本文档对各位有些帮助。1、画出编译程序的总体结构图，简述其部分的主要功能。答案编译程序的总框图见下图。图 编译程序的总体结构图其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果上单词符号。语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间优化器对中间代码进行优化处理。

2、一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能表格管理模块保持系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程2、计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么？答案计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。像 B a s i c

3、之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读总而言之，是边翻译边执行。像 C,P a s c a l 之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻译，招其全部变为机器代码，再统1 .文法法S 为:S-A c|a BA-a bB-b c写 出 L(G S )的全部元素。答案S=A c=ab c或 S=aB=ab c所以 L(G S )=ab c 2 .文法G N 为：N-D|N DD-0|l|2|3 4|5|6 7|8|9G N 的语言是什么？答案G N 的语言是 V+o V=0,1,2,3,4,5

4、,6,7,8,9N=N D=N D D.=N D D D D.D=D.D3 .已知文法G S ：S-*d A B A-aA|a B-e b B问：相应的正规式是什么？G S 能否改写成为等价的正规文法？答案正规式是d aa*b*；相应的正规文法为(由自动机化简来)：G S :S-d A A-a|aB B-aB a|b|b C C-b C b也可为(观察得来)：G S :S f d A A-*a|aA|aB B-*b B e4 .已知文法 G Z ：Z-aZ b|ab写出L(G Z )的全部元素。答案Z=aZ b=aaZ b b=aaa.Z.b b b=aaa.ab.b b bL (G Z )=

5、ab|n=l n n5 .给出语言 ab c|n=l,m=0 的上下文无关文法。n n m 分析本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是:A-P,A 6Vn,P G (Vn UVt)*,注意关键问题 答案构造上下文无关文法如下：S-A B|A A-aA b|ab B-B c|c 扩展凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路是这样的:n n m m 要求符合ab c,因为a 与 b 要求个数相等，所以把它们应看作一个整体单元进行,而 c做为另一个单位，初步产生式就应写为S-A B,6.写一文法，使其语言是偶正整数集合。要求：(1)允许0

6、开头；(2)不允许0开头。答案(1)允许0开头的偶正整数集合的文法，注意：0E-N T|G|S F MT-N T|GN-0|l|2|3 4|5|6 7|8|9D-0|2|4|6 8G-2|4|6|8S-N S|eF-1|2|3 4|5|6|7|8 9M-M O|0(2)不允许0开头的偶正整数集合的文法 不是正数。E-N T|DT-F T|GN-D|1|3|5 7|9D-2|4|6|8F-N|0 G-D|07.已知文法G：E-E+T|E-T TT-T*F|T/F FF-X E)|i试给出下述表达式的推导及语法树(l)i;(2)i*i+i (3)i+i*i (4)i+(i+i)答案(1)(2)E=

7、E+T=T+T=T*F+T=F*F+T=i*F+T=i *i +T=i *i+F=i*i+i(3)E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i(4)E=E+T=T+T=F+T=i +T=i +F=i +(E)=i +(E+T)=i+(T+T)=i+(F+T)=i+(i+T)=i+(i+F)=i+(i+i)8.为句子i+i*i构造两棵语法树，从而证明下述文法G 表达式 是二义的。表达式-表达式 运算符 表达式|（表达式）|i 运算符-+|-|*|/答案可为句子i+i*i构造两个不同的最右推导：最右推导1 表 达 式=表达式 运 算 符 表达式=表 达 式 运

8、 算 符 i=表 达 式*i=表 达 式 运 算 符 表达式*i 表 达 式 运 算 符 i *i=表达式+i *i=i +i *i最 右 推 导2 表 达 式=表 达 式 运 算 符 表 达 式=表 达 式 运 算 符）表 达 式 运 算 符 表达式=表达 式 运 算 符 表 达 式 运 算 符 i=表 达 式 运 算 符 表 达 式*i二 表 达 式（运 算 符 i *i=表 达 式+i *i=i +i *i所 以，该文法 是 二 义 的。9.文 法G S 为:S-A c|aBA-abB-b c该 文 法 是 否为二义的？为 什 么？答 案 对 于 串ab c(l)S=A c=ab c(2

9、)S=aB=ab c即存在两不同的最右推导所以，该文法是二义的。1 0.考虑下面上下文无关文法：S-S S*|S S+：a(1)表明通过此文法如何生成串aa+a*,并为该串构造语法树。(2)G S 的语言是什么？答案(1)此文法生成串aa+a*的最右推导如下：S=S S*=S S*=S a*=S S+a*=S a+a*=aa+a*(2)该文法生成的语言是即加法和乘法的逆波兰式，1 1.令文法G E 为:E-E+T|E-TT-T*F|T/F FF-(E)|I证 明 E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导

10、序列：E=E+T=E+T*F,所 以 E+T*F 句型。此句型相对于E的短语有:E+T*F；相对于T的短语有T*F,直接短语为：T*F。句柄为：T*F。1 2 .已知文法 G E:E-E T+|T T T F*|F F-F-a试证：F F“*是文法的句型，指出该句型的短语、简单短语和句柄。答案该句型对应的语法树如下：该句型相对于E的短语有F F *；相对于T的短语有F F *,F;相对于F的短语有FF;简单短语有F;厂；句柄为F.1 3 .一个上下文无关文法生成句子ab b aa的推导树如下：(1)给出串ab b aa最左推导、最右推导。(2)该文法的产生式集合P可能有哪些元素？(3)找出该句

11、子的所有短语、直接短语、句柄。答案(1)串ab b aa最左推导：S=A B S=aB S=aS B B S=a e B B S=a e b B S=a b b S=a e b b A a=a e b b aa最右推导：S=A B S=A B A a:=A B aa=A S B B aa=A S B b aa=A S b b aa=A e b b aa=a e b b aa产生式有：Sf A B S|A a|e A-a B-S B B b(3)该句子的短语有 al b l b 2 a2 a3、al、b l、b 2、b l b 2、a2 a3、a2；直接短语有al、b l、b 2、a2；句柄是a

12、l o1 4 .给出生成下列语言的上下文无关文法。n n m m(l)ab ab|n,m=0 n m m n(2)(1 0 1 0|n,m=0 r r(3)W a W W属于 0 1 a)*,W表示W的逆 答案(1)a b a b n,m =0 S-A A A-a A b|en m m n(2)1 0 1 0|n,m =0 S-1 S O|A A-O A 1|er(3)W a W W 属于 0|a *,W r 表示 W 的逆S-O S O|1 S 1 e1 5 .给出生成下列语言的三型文法。n(1)a|n =0 n m(2)a b n,m =l n m k (3)a b c|n,m,k =0

13、答案(1)a n =0 的三型文法为：S-a S|en m(2)a b n,m =l 的三型文法为：S-a A A-a A|b B B-b B|en m k n|n n m m (3)a b c|n,m,k =0 的三型文法为:A-a A|b B|c C|e B-b B|c C|e C-c C|e1 6 .构造一文法产生任意长的a,b串，使得|a|=|b|b b|b第 1 个产生式为递归定义，由于在第2 个产生式中B被定义为1 或 2 个 b,所以第1 个产生式可以保证b的个数在|a|与 21 a l 之间，而1 7.下面的文法产生a的个数和b的个数相等的非空a,b串S-a B|b AB-b

14、S|a B B bA-a S|b A A a其中非终结符B推 出 b比 a的个数多1 个的串，A则反之。说明该文法是二义的。对上述文法略作修改，使之非二义，并产生同样的语言。(略做修改的含义是：不增加非终结符。)答案句 子 a a b b a b 有两种不同的推导。S=a B=a a B B=a a b B=a a b b S=a a b b a B=a a b b a bS=a B=a a B B=a a b S B=a a b b A B=a a b b a B=a a b b a b即它可以产生两棵不同的语法树，故它是二义的。修改后的无二义文法如下：S-a B S|b A S|a B|b

15、 A B-a B B|b A-b A A|a1 8.给出0,1,2,3 型文法的定义。答案乔姆斯基(c h o m s k y)把文法分成类型，即 0型，1 型，2 型和3 型，0型强于1 型，1 型强于2 型，2 型强于3 型。如果它的每个产生式a -0的结构是a G (V n U V t)*且至少含有一-个非终结符，而P e (V n U V t)*,我们说G=(V t,V n,S,8)是一个0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵(T u n ri n g)机。或者说，任 何 0型语言都是递归可枚举如果把0型文法分别加上以下的第i 条限制，则我们就得i 型

16、文法为：1.G的任何产生式a -B 均满足I a|e 例外,但 S不得出现在任何产生式的右部。2.G 的任何产生式为 A-B ,A e V n,Be(V n U V t)*3.G的任何产生式为A-a B 或 A-a,其中A,B e V n1 型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，一般不允许替换成空串。2 型文法对非终结符进行替换时无须考虑上下文，3 型文法也称线性文法。1.构造正规式1 (0|1)*1 0 1 相应的D FA o先构造N FA01XAAABBCBCADDCBD FA：2.招下图确定化:r-o01sQUVQQUQUQUZVZZVQUZ

17、QUZ11Z重新命名，令V Q为A、Q U为B、V Z为C、V为D、Q U Z为E、Z为F。01SABACBBDEcFFDFECEFFFD FA：01a答案初 女 合 分 龙 U彳等c 0=老 冬 态 组 9J m 3冬 态 组 a.2对 与 归 在 冬 右 阻 进 千 亍 审 至s 1J N 3,5 A u f 1,3,5 TTn Om 1,3 5 不 JW o j 3 1 2,S J 14 m U t o),所 以 不 号 新 分 封 U-x1=3,4 ,d 2n&5】对 d 2,3,5 进 行 市 蛰,.d 5 1 匕 u 4d 3 1 口 =t l,2J 3q 5 1 n古 殳 得 新

18、 分 知2=O,4,1_,5 ,2,3 I 5 7 =u d 5 7 2.3 J Q u 1.3 ,岐 吠 态 之 不 口 供 志 3 不 等 许口3=1。),2,3,41,O A|1 BA-1 S|1B-O S|O 答案解方程组S的解：S=O A|1 BA=1 S|1B=O S|0将 A、B 产生式的右部代入S中S=01 S|01|1 0S|1 0=(01|1 0)S|(01|1 0)所以：S=(01 1 0)*(01 1 1 0)6.为下边所描述的串写正规式，字 母 表 是 a,b.a)以 ab结尾的所有串b)包含偶数个b但不含a的所有串c)包含偶数个b且含任意数目a的所有串d)只包含一个

19、a的所有串e)包含a b 子串的所有串f)不包含a b 子串的所有串 答案注意正规式不唯一a)(a|b)*a bb)(b b)*c)(a*b a*b a*)*d)b*a b*e)(a|b)*a b (a|b)*f)b*a*7.请描述下面正规式定义的串.字母表S=0,1）.a)0*(10+)*0*b)(0|1)*(00|11)(0 1)*c)l(0|1)*0 答案a）每 个 1 至少有一个0 跟在后边的串b）所有含两个相继的0 或两个相继的1 的 串 c）必 须 以 1 开头和。结尾的串8.构造有穷自动机.a）构造一个DFA,接受字母表b）构造一个DFA,接受字母表c）构造一个NFA,接受字母表

20、d）构造一个NFA,接受字母表换为等价的0,1上的以0 1 结尾的所有串0,1上的不包含0 1 子串的所有串.x,y上的正规式x（x|y）*x描述的集合a,b上的正规式（ab|a）*b+描述的集合并将其转DFA.以及最小状态DFA 答案 b）c)NFA：DFAX 答案可通过消结法得出正规式R=(01)*(00|l)(0 1)*|0)也可通过转换为正则文法，解方程得到正规式。1 0.已知正规式：(1)(a|b)*a a)*b；(2)(a|b)*b.试用有限自动机的等价性证明正规式(1)和(2)是等价的，并给出相应的正规文法。分析基本思路是对两个正规式，分别经过确定化、最小化、化简为两个最小D F

21、 A,如这两个最 小 D F A 一样，也就证明了这两个正规式是等价 答案状态转换表1abX1241234124Y12341234124Y124Y1234124Y状态转换表2aB123223323ab123223abX121212Y121212Y12Y1212Yab123_2_23得 D F A 图两图完全一样，故两个自动机完全一样，所以两个正规文法等价。对相应正规文法，令故为：A-a A|b B|bB-a A|b B|b即为S-a S|b$|B,此即为所求正规文法。A对 应 1,B对 应 2四1.文法S-a|*|(T)T-T,S|S(1)对(a,(a,a)和(a,a),(a),a)的最左推导

22、。(2)对文法G改写，然后对每个非终结符写出不带回溯的递归子程序。(3)经改写后的文法是否为L L (1)的？给出它的预测分析表。(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。答案(1)对(a,(a,a)的最左推导为：S=(T)=(T,S)=6,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)对(a,a),(a),a)的 最 左 推 导 为:S=(T)=(T,S)=(S,S)=(C r),s)：(T,s),s)=(T,S,S),S)=(S,S,S),S)=(T),S,S),S)=(T,S),S,S),S)=(S),S,S

23、),S)=(a,S),S,S),S)=(a,a),S,S),S)=(a,a),S),S)=(a,a)/，(T),S)=(a,a)/，(S),S)=(a,a)/，(a),S)=(a,a),(a),a)(3)改写文法为：0)S-a1)S-2)S-(T )3)T-S N 24)N 2-,S N 25)N 2-e对左部为N 2的产生式可知:F IR ST (-,S N 2)=,F IR ST (-)=e F O LLO W N 2)=)(,C )=0所以文法是LL 的。可见输入串(a,a)#是文法的句子。2.已知文法G A 如下，试用类C或类P A SC A L语言写出其递归下降子程序.(主程序不需写

24、)G A :A f B B-X A X-(a|b)a|b 答案不妨约定:在进入一个非终结符号相应的子程序前，已读到一个单词.w o r d：存放当前读到的单词，Ge t s ym O 为一子程序，每调用一次，完成读取一单词的工作。e r r o r。为出错处理程序.F IR ST (A)为终结符A的 F IR ST 集.类 C程序如下:3.文法：S-M H|a H-LSo|E K-dM L L-e H f M-K|bLM 判断 G 是否为 LL(1)文法，如果是,构 造 LL(1)分析表。答案源文法G 展开为：0)S-M H1)S-a2)H-L S o3)H-4)K-d M L5)K-e6)L

25、-e H f7)M-K8)M-b L M；=:：西 芭至三-二 匚 二”三 三 三；=：1.I三三一 一 ：=二匚-工三匚二 匚:一-二 丘 三 二-由预测分析表中无多重入口判定文法是LL(1)的。4.设有文法G A 的产生式集为：A-B aC|C bB B-A c|c C-B b|b试消除G A 的左递归。答案提示：不妨以A、B、C排序.先将A代入B中，然后消除B中左递归；再将A、B代 入 C中。再消除C中左递归。最后结果为:G A :A-*B aC|C bB B-C bB cB cB B -aC cB)|e C-cB bC|bC C -bB cB bC|e 五1、对于文法 S(L)a L

26、L,S|S(1)给出句子(a,(a,a),(a,a)的 个最右推导，并指出右句型的句柄;(2)按照(1)的最右推导，说明移进一归约分析器的工作步骤。答案 S=(L)=(L,S)=(L,(L)=(L,(L,S)=(L,(L,(L)=(L,(L,(L,S)=(L,(L,(L,a)=(L,(L,(S,a)二 (L,(L,(a,a)二 (L,(S,(a,a)二)(L,(L),(a,a)=(L,(L,S),(a,a)=(L,(L,a),(a,a)二)(L,(S,a),(a,a)二)(L,(a,a),(a,a)=(S,(a,a),(a,a)=(a,(a,a),(a,a)（注：句柄下面有下划线）（2）步骤栈

27、输 入动作1(a,(a,a),(a,a)#移进24(a,(a,a),(a,a)#移进3#(a,(a.a),(a,a)#归约，S玲a4t(S,(a,a),(a,a)#归约，LS5#(L,(a,a),(a,a)#移进64(L,(a,a),(a,a)I移进r#(L,(a,a),(a,a)#移进8#(L,(a,a),(a,a)#移进9#(L,(a,a),(a,a)#归约，S玲a10#(L,(S,a),(a,a)#归约，L1 S11#(L,(L,a),(a,a)#移进12#(L,(L,a1.Q,a n i#移进13f(L,(L,a),(a,a)#归约，S玲a14#(L,(L,S),(a,a)#归约，L玲

28、L,S15#(L,(L),(a,a)#移进16#(L,(L),(a,a)#归约，S玲(L)17#(L,(S.(a,a)：i#归约，L-S18#(L,(L,(a,a)#移进19#(L,(L,(a,a)f移进20#：L,(L,(a,a)1移进21#(L,(L,(a,a)#归约，S玲a221 一 一 1#(L,(L,(S1 y _ ，一 ，一 1,a)#归约，L9S344(L)归约，S玲(L)35fS*接受2、已知文法 G S 为：S a|(T)T T,S|S(1)计算 G S 的 F 1 R ST V T 和 LA ST V T0(2)构造G S 的算符优先关系表并说明G S 是否未算符优先文法。

29、计 算 G S 的优先函数。(4)给出输入串(a,a)#和(a,(a,a)#的算符优先分析过程。答案(1)F IR ST V T 和 LA ST V T(2)算符优先关系FIRSTVTLASTVTSa、“、(a、)T,、a、(,、a、x )a()Aa(*=)3卡*卡(3)对应的算符优先函数为:a()9.S212221T331131(4)句子(a,a)#分析过程如下:步骤栈优先关系当前符号剩余输入串移进或归长1*#)归约#(F,F,)#归约8#(F(=)#移进9#(F)#归约1 0*F#=#*接受 给 出（a,（a,a）和（a,a）的最右推导和规范归约过程。步骤栈优先关系当-2 一1 1 IJ符

30、号剩余输入申移进或归约1#归约17*F#三#接受（2）将（1）和题2中的进行比较给出算符优先归约和规范归约的区别。答案(1)(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)的最右推导过程：S=(T)=(T,S)=(T,a)=(S,a)=(a,(a,a)(注：句柄下面有下划线)(2)(a,(a,a)的规范归约过程。步骤栈输 入动 作1(a,(a,a)#移进2#(a,(a,a)#移进3#(a,(a,a)#归约，S a4#(S,(a,a)：)#归约，L B

31、S5#(T,(a,a)#移进6#(T,(a,a)#移进f(T,(a,a)#移进8#(T,(a,a)#归约，S S a9t(T,(S,a#归约，T S1 0f(T,(T,a)#移进1 1#(T,(T,a)#移进1 2(T,a)9归约，S-a1 3#(T,(T,S)?归约，TO T,S11#(T,(T)#移进1 54(T,(T)#归约，S-(T)1 6#(T,S)#移进1 7#(T,S)#归约，T-T,S1 8#(T)归约，S(T)1 9#S接受(a,a)的规范归约过程。步骤栈输 入动 作1(a,a)#移进25 (a,a)#移进3#(a.a)#归约，S玉4#(S,a)#归约，T3 s5f(T,a)

32、#移进6#(T,a)#移进f(T,a)#归约，S-a8#(T,S)#归约，T-T,S9#(T)#移进1 0f(T)归约，ST(T)1 1f S#接受FIR STVTLASTVTSi,+,),(i,+,*,(Vi,+,),(T+,),(+.(,*F),(,*,(i+*()IIII 1(2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名字是什么，因此去掉了单非终结符的归约。规范归约的可归约串是句柄，并且必4、有文法 G S：S V V T|Vi T T F T+F F)V*(1)给出(+(i

33、(的规范推导。(2)指出句型F+Fi (的短语，句柄，素短语。(3)G S 是否为O P G?若是，给出(1)中句子的分析过程。答案(1)S=V=Vi T=Vi F=Vi(=T i(=T+F i(=T+(i(=F+(i(=(+(i(2)句型F+Fi (的语法树：短语：F,F+F,(,F+Fi(句柄：F素短语：(3)FIR STVT和 LASTVT(2)算符优先关系因为该文法是O P,同时任意两个终结符的优先关系唯一，所以该文法为O P G。i才丈*才才(才)卡*+(i(#归约3#F#ii(#归约6#F+F+ii(#归约i(#移进8#Fii#归约10#FiF归约11#=#接受5、试为下列各文法建

34、立算符优先关系表。答案算符优先关系表如下:六truefalsenotandor()#true才才falsenot卡and*才*or*(*=)f*1、已 知 文 法：A-a Ad|a Ab|，判断该文法是否SLR (1)文法，若是构造相应分析表，并对输入串a b#给出分析过程。答案(1)拓广文法(0)S-A(1)A-a Ad (2)A-a Ab (3)A-EFO LLO W(A)=d,b,#对于状态 1 0：FO LLO W(A)D a =对于状态 1 1 ：FO LLO W(A)C a =因为，在 DFA中无冲突的现象，所以该文法是SLR(l)文法。(3)SLR 分析表(4)串 a b#的分析

35、过程2、设文法G 为 S A A BA|e步骤状态栈10202302340235501(1)证明它是LR(1)文法;a B|b(2)构造它的LR(1)分析表；(3)给出输入符号串a b a b 的分析过程。答案(1)拓广文法 G:(0)S S(1)S A(2)A BA(3)A e FIR ST(A)=a,b FIR ST(B)=a,b构造的 DFA 如下：(4)B a B(由项目集规范族看出，不存在冲突动作。.该文法是LR(D文法。(3)输入串abab的分析过程为:状态Ac t i o nGo t oaB#SAB0S4S5r 31231a c c2r l3S4S5r 3634S4S55r 5r

36、 5r 56r 2Lr 4r 4r 4步骤状态栈符号栈当前字符剩余字符串动 上(1)0ab a b#移进(2)0 4曲aba b#移进(3)0 4 5#a bab#归 约B-b(4)0 4 7#a Bab#归 约B-a B(5)0 3怔ab#移进(6)0 3 4VBab移进(7)0 3 4 5 Ba b*归 约Bf b(8)0 3 4 7IBa B#归 约B a B0 3 3*归约(1 0)0 3 3 6 BBA*归 约A9 BA(1 1)0 3 6#BA*归 约A9 BA(1 2)0 2 A归 约S-A(1 3)0 1空#a c c3、考虑文法S A S|b A S A|a (1)构造文法的

37、LR(O)项目集规范族及相应的DFA。(2)如果把每一个LR(O)项目看成一个状态，并从每一个形如B a的状态出发画一条标记为X 的箭弧刀状态B a X(3)构造文法的SLR 分析表。(4)对于输入串b a b,给 出 SLR 分析器所作出的动作。(5)构造文法的LR(1)分析表和LALR 分析表。答案(1)令拓广文法G 为(O)S S(1)S A S(2)S b (3)A S A(4)A a其 LR(O)项目集规范族及识别该文法活前缀的DFA如下图所示：FO LLO W(S)=#,a,b FO LLO W(A)=a,b(2)显然，对所得的NFA求 e闭包，即得上面的LR(O)项目集，即 DF

38、A中的状态。故此NFA与(a)中 DFA是等价的。(3)文法的S LR 分析表如下：因为 15 中：FOLLOW (A)n a,b W ，17 中：FOLLOW (B)A a,b W 所以，该文法不是S LR (1)文法。或者：状 态一a c ti o ng o toAbSA0S 4S 3121S IS 3a c c652s;S 3L23r2r2r24r 1r4r 45S 4/r3S 3/r3F*26S IS 365S 4/rlS 3/rlR l65从分析表中可看出存在歧义，所以该文法不是S LR (1)文法。(4)对于输入串b a b,S LR 分析器所作舟的动作如下：步骤状态栈符号栈当前字

39、符剩余字符串动4(1)0ba b#移 立(2)03*bab#归 约s(3)01#Sab#移义(4)014#S ab归 约/(5)015f S Ab归 约A(6)02#Ab移M(7)0A2b 3#AbI归 约t(8)027f AS邛归约S(9)01#S接V(在第5 个动作产生歧义)(b)LR(l)项目集族为：10:S S,#S AS,#a|b S S A,a bIl:S，S A S A,a|bS b,#|a|b A a,a bS AS,a|bA,a,a )b S ,b,a|b12:S A S,#|a|b 13:S b ,#|a|b S b,i t|a b S,AS,i t|a|b 14:A a

40、,a|b A,S A,a|b A,a,a|b15:A S A ,a|b 16 :A S -S A S,a|b A S A,a bS AS,a|b A,a,a|b S ,b,a b S ,AS,a|b A,S A,ab S ,b,a|b A,a,a I b 17:S AS ,a b A S ,A,a I b A S A,a|bA,a,a|bS AS,a|bS ,b,a|b T6状态集中存在“归约一一移进”冲突，故无法构造LR(1)分析表，因而也就无法构造 LALR 分析表。4、对下面的文法:S-U T a|T b T-S S c|d U-U S|e判断是否为LR(O),S LR(1),LALR(

41、1),LR(1),说明理由,并构造相应的分析表。答案(1)拓广文法：(O)S -s(l)S-U T a(2)S-T b(3)T-S(4)T-S c(5)T-d(6)U-U S(7)U-e(2)构造识别LR (0)项目的DFA如下:因 为H、18中存在冲突，所以该文法不是L R(0)文法。因为 FOLLOW (S)=#,c,a,b,d,e,FOLLOW (T)=a,b,FOLLOW (U)=d,e 11 中FOLLOW(T)C c =18 中 FOLLOW(U)A c =，FOLLOW(T)C c =，FOLLOW(T)D FOLLOW(U)=H、18中冲突解决，所以该文法是S LR (1)文法

42、。FIRSTFOLLOWSe,da,b,d,e,#,cTe,da,bUed,e构造识别LR 项目的DFA如下:因为不存在冲突，所以该文法是LR (1)文法。其 中 12、19 可合并，Ill、H 3 可合并,可合并，17、115可合并，合并后无冲突,15、110可合并，16、H 4 可合并,所以112、116ACTIONG O TO状态abCdeSTU0S5S41321r3S6acc2S10S48L93Sil4r75r56r4LS12S138r3r3S14r6r69S10S4815910r5r511r2r2r212rlrlrl13r2r214r4r415S16SI 316rlrlACTIONG

43、OTO状态abcdeST0S5,10S4131r3S6acc2,9S5,10S487,153Sll,134r7r75,10r5r56,14r4r47,15S12,16Sll,138r3r3S6,14r6r611,13r2r2r2r2r212,16rlrlrlrlrl七产生式语义规则L f Epr ini(E,va 1)E -E+TE.val:=E.va 1+T.va 1.一 E.val:=T.va 1T-T*FT.val:=l.va 1 va 1T-FT.va 1:=F.va 1F f(E)F.va I:=E.va 1F f d i g i tF.va 1:=digi l.lexva 11、对

44、于输入的表达式(4*7+1)*2,根据下表的语法制导定义建立一棵带注释的分析树。va l:表示非终结符的整数值，综合属性,le x va l是 单 词 d i g i t的属性语法制导定义 答案2、令 S.va l为下面的文法由S生成的二进制数的值（如，对于输入101.101,S.va l=5.6 25）；S-L.L|LL-LB|BB f 0|1 答案va l为综合属性，代表值属性语法制导定义产生式语义规则S3I7.L2S.val:=L val+L2.val/2u.S9LS.val:=L.val3,结果为整数，否则为E-*E+T|T T-*n u m.n u m|n u m给出语法制导定义确定

45、每个子表达式的类型。Lf I/BL.vol:=L val*2+B.valL.length:=L1.length+1L玲BL.val:=B.valL.length:=1Bf0B.val:=0B 1B.val:=1 答案设 ty p e 是综合属性，代表各非终结符的“类型”属性产生式语义规则E-El+TIF(Ex.type=integer)and(T.type=integer)TEE.type:=integerELSEE.ty p e：=re a lE-TE.type:=T.typeT 玲 num.numT.type:=realT 玲 numT.type:=integer4、利用下列文法 E-*E

46、+T|T T-n u m.n u m n u m把表达式翻译成前缀形式，并且决定类型。试用一元运算符i n tto re a l 答案把整型值转换为相等的实型值，以使得前缀表为综合属性，代表各非终结符的代码属性ty p e 为综合属性，代表各非终结符的类型属性i n tto re a l把整型值转换为相等的实型值vto c h a r将数值转换为字符串产生式语义规则S-Eprint E.codeE-E1+TIF(El.type=integer)and(T.type=intefbeginE.type:=integerE.code=+|Ei.code 11T.code;endELSE begin

47、E.type:=realIF El.type=integer TH ENbegin El.type:=realEl.val:=inttoreal(El.val)语法制导定义设c o d e、请按语法制导的定义，将后缀表达式翻译成中缀表达式。注意，不允许出现冗余括号，后续表达式的文法如下：E-EE+E-EE*E fidE l.c o d e=v t o c h a r (1.v a l)e n dIF T.t yp e:=i n t e g e r THE Nb e g i nT.t yp e:=r e a lT.v a l :=i n t t o r e a l (T.v a l)T.c o

48、d e=v t o c h a r (T.v a l)e n dE.c o d e=，+)|E i.C O加 11T.c o d e;E n dE+TE.t yp e:=T.t yp eE.v a l :=T.v a lE.c o d e=v t o c h a r(E.v a l)TTn u.n u T.t yp e:=r e a lT.v a l :=n u m.n u m.l e x v a lT.c o d e=v t o c h a r(T.v a l)TTn i mT.t yp e:=i n t e g e rT.v a l :=n u m.l e x v aT.c o d e=v

49、 t o c h a r (T.v a l)答案6、有文法：S-(L)|a L-*L,S|S产生式语义规则S-Ep r i n t E.c o d eE-E&+E.c o d e=E*.c o d e|+?|E:.c o d e;E.o p=+ET&*IF E x.o p=+A ND E；.o p=+THE NE.c o d e=*(*|EX.c o d e|1)11 *1 1 (1|E?.C OCE L SE IF E i.o p=+THE NE.c o d e=(|E i.c o d e IT)IT*I|E2.C Oa print(S.f);L-LI.f:=L.f;LI,S.f:=L.fS

50、L-S.f:=L.f;SL一,i LIL.Type:=Ll.Typeaddtype(i.entry,L.type)L-*：TL.type:=T.typeT-*integerT.type:=integerT-*realT.type:=real9、对下面的文法，只利用综合属性获得类型信息。D-L,i d|LLT i dT i n t|r e a l 答案D-L,idD.type:=L.typeaddtype(id.entry,L.type)D-*LD.type:=L.typeL-*T idL.type:=T.typeaddtype(id.entry,T.type)T-*intT.type:=int