编译原理作业

1、习题1 1.1解释名词：源语言、目标语言、翻译器、编译器和解释器。答：源语言是指待翻译的语言，和目标语言相对。目标语言是指被翻译的语言，与源语言相对。能够完成从一种语言到另一种语言的变换的软件称为翻译器，这两种语言分别叫做该翻译器的源语言和目标语言。编译器是一种特殊的翻译器，它进行语言变换的特点是目标语言比源语言低级。解释器是不同于编译器的另一类语言处理器。它不像编译器那样通过翻译来生成目标程序，而是直接执行源程序所指定的运算。它的执行方式是一边翻译一边执行，因此其执行效率一般偏低。1.2典型的编译器可以划分成几个主要的逻辑阶段？各阶段的主要功能是什么？答：典型的编译器可以划分成七个主要的逻辑

2、阶段，分别是词法分析器、语法分析器、语义分析器、中间代码生成器、独立于机器的代码优化器、代码生成器、依赖于机器的代码优化器。各阶段的主要功能：（1）词法分析器：词法分析阅读构成源程序的字符流，按编程语言的词法规则把它们组成词法记号流。（2）语法分析器：按编程语言的语法规则检查词法分析输出的记号流是否符合这些规则，并依据这些规则所体现出的该语言的各种语言构造的层次性，用各记号的第一元建成一种树形的中间表示，这个中间表示用抽象语法的方式描绘了该记号流的语法情况。（3）语义分析器：使用语法树和符号表中的信息，依据语言定义来检查源程序的语义一致性，以保证程序各部分能有意义地结合在一起。它还收集类型信息

3、，把它们保存在符号表或语法树中。（4）中间代码生成器:为源程序产生更低级的显示中间表示，可以认为这种中间表示是一种抽象机的程序。（5）独立于机器的代码优化器：试图改进中间代码，以便产生较好的目标代码。通常，较好是指执行较快，但也可能是其他目标，如目标代码较短或目标代码执行时能耗较低。（6）代码生成器：取源程序的一种中间表示作为输入并把它映射到一种目标语言。如果目标语言是机器代码，则需要为源程序所用的变量选择寄存器或内存单元，然后把中间指令序列翻译为完成同样任务的机器指令序列。（7）依赖于机器的代码优化器：试图改进目标机器代码，以便产生较好的目标机器代码。第二章2.解：由题目分析可知，一个符号串

4、由0和1组成，则0和1的个数只能有四种情况： 偶数个0和偶数个1（用状态0表示）；偶数个0和奇数个1（用状态1表示）；奇数个0和偶数个1（用状态2表示）；奇数个0和奇数个1（用状态3表示）。所以，状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0 和奇数个1（状态1）； 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0 和偶数个1（状态2）； 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0 和偶数个1（状态0）； 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0 和奇数个1（状态3）； 状态

5、2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0 和奇数个1（状态3）；  状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0）； 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0 和偶数个1（状态2）； 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0 和奇数个1（状态1）。因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态，又为终结状态，其状态转换图如下面的图1所示：200011111300start图11.解：由状态转换图可以写出其正规文法为： S0

6、  1S1|0S2|S1  1S0|0S3|1S2  1S3|0S0|0S3  1S2|0S1在不考虑S0产生式的情况下，可以将文法变形为：S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1所以S0 =&#

7、160;(00|11)S0 + (01|10)S3 + 11 + 00        (1)     S3 = (00|11)S3 + (01|10)S0 + 01 + 10         (2)解(2)式得：S3 = (00|11)*(01|10

8、)S0+(01|10)代入(1)式得：     S0=(00|11)S0+(01|10)(00|11)*(01|10)S0 +(01|10)+(00|11)=>S0=(00|11)S0+(01|10)(00|11)*(01|10)S0+(01|10)(00|11)*(01|10)+(00|11)=>S0=(00|11)+(01|10)(00|11)*(01|10)S0+(01|10)(00|11)*(01|10)+(00|11)=>S0=(00|11)|(01|10)(00|11)*(01|10)*(01|10)(0

9、0|11)*(01|10)+(00|11)=>S0=(00|11)|(01|10)(00|11)*(01|10)*(00|11)+(01|10)(00|11)*(01|10)=>S0=(00|11)|(01|10)(00|11)*(01|10)*(00|11)|(01|10)(00|11)*(01|10)=>S0=(00|11)|(01|10)(00|11)*(01|10)+=>S0=(00|11|(01|10)(00|11)*(01|10)+因为S0所以由偶数个0和偶数个1构成的01串的正规式为：S0(00|11|(01|10)(00|11)*(01|10)*

10、0;由正规式(00|11|(01|10)(00|11)*(01|10)*画其NFA答：先画正规式分析树如图 1所示。图 1NFA如图 2所示。图 2由上面的NFA转换图得：-closure(1)=1,2,36,3,27,4,7,28,31=A-closure(move(A,1)= -closure(8,32)=8,32=B-closure(move(A,0)= -closure(5,29)=5,29=C-closure(move(B,1)= -closure(33)=33,34,35,36,2,3,27,4,7,28,31=D-closure(move(B,0)= -closure(9)=9,

11、10,11,19,12,15,20,23=E-closure(move(C,1)= -closure(6)=6,10,11,19,12,15,20,23=F-closure(move(C,0)= -closure(30)=30,34,35,36,2,3,27,4,7,28,31=G-closure(move(D,1)= -closure(8,32)=B-closure(move(D,0)= -closure(5,29)=C-closure(move(E,1)= -closure(16,24)=16,24=H-closure(move(E,0)= -closure(13,21)=13,21=I-

12、closure(move(F,1)= -closure(16,24)=16,24=H-closure(move(F,0)= -closure(13,21)=13,21=I-closure(move(G,1)= -closure(8,32)=8,32=B-closure(move(G,0)= -closure(5,29)=5,29=C-closure(move(H,1)= -closure(17)=17,18,11,19,12,15,20,23=J-closure(move(H,0)= -closure(25)=25,26,35,36,2,3,27,4,7,28,31=k-closure(mov

13、e(I,1)= -closure(22)=22,26,35,36,2,3,27,4,7,28,31=L-closure(move(I,0)= -closure(14)=14,18,11,19,12,15,20,23=M-closure(move(J,1)= -closure(16,24)=16,24=H-closure(move(J,0)= -closure(13,21)=13,21=I-closure(move(K,1)= -closure(8,32)=8,32=B-closure(move(K,0)= -closure(5,29)=5,29=C-closure(move(L,1)= -cl

14、osure(8,32)=8,32=B-closure(move(L,0)= -closure(5,29)=5,29=C-closure(move(M,1)= -closure(16,24)=16,24=H-closure(move(M,0)= -closure(13,21)=13,21=IDFA的转换表如下。状态输入符号10ABCBDECFGDBCEHIFHIGBCHJKILMJHIKBCLBCMHI这个DFA的转换图如下。0=B,C,E,F,H,I,J,M,A,D,G,K,L1= E,F,J,M,A,D,G,K,L,B,C,H,I2= E,F,J,M,A,D,G,K,L,B,I,C,H最简D

15、FA的转换表如下。状态输入符号10ABCBAECEAECB极小化DFA的转换图如下。matched_stmt->if expr then matched_stmt else matched_stmt | other unmatched_stmt->if expr then matched_stmt | if expr then matched_stmt else unmatched_stmt if expr then matched_stmt else matched_stmt  if expr the

16、n matched_stmt else unmatched_stmt  if expr then unmatched_stmt else matched_stmt  if expr then unmatched_stmt else unmatched_stmt  （3） 漏掉了还是包含在里面？（4） 能否由推出？若不能推出，会不会造成结构性缺失？解：(1) 漏掉了。(2) 不能由推出，并且不会造成结构性缺失。会使文法具有二义性。3.10

17、构造下面文法的LL（1）分析表。D>TLT>int | realL>id RR>,id R |解：D>TL FIRST(D)=FIRST(TL)=FIRST(T)= int, real T>int FIRST (int)= int T> real FIRST (real)= real FIRST(T)= int，realL>id R FIRST (L)=FIRST (id R)= id R>，id R FIRST (，id R)= ，R> FIRST ()= FIRST (R)=，, FOLLOW(R)= FOLLOW(L)=FOLL

18、OW(D)=$由此得出上述文法的LL（1）分析表如下表所示。文法的LL（1）分析表intrealid,$DD>TLD>TLTT>intT> realLL>id R RR>,id RR>非递归的预测分析对题3.10的预测分析器接受输入分别为int id，id id，id:real时的动作根据上题中得出的分析表（表格 1）可得三列表分别为表格 2、表格 3。表格 1intrealid,$DD>TLD>TLTT>intT> realLL>id R RR>，id RR>表格 2栈输入输出$Dint id，id$LTin

19、t id，id$D>TL$L intint id，id$T>int$L id，id$Rid id，id$L>id R $R，id$ Rid， ，id$R>，id R$ Ridid$ R$R>表格 3栈输入输出$Did，id:real$因为MD,id没有产生式，出错，所以直接退出。3.18 求下面文法中非终结符的FIRST、FOLLOW集。【注：文法分析中不能判断闭包、加号、乘号等符号，均视为终结符】E>E+T|TT>TF|FF>F*|a|b解：F> a FIRST(a)=a F> b FIRST(b)=bFIRST(F)= FIRST

20、(F*)FIRST(a)FIRST(b)=a,bFIRST(T)= FIRST(TF)FIRST(F) = FIRST(T)FIRST(F)= FIRST(F) =a,bFIRST(E)= FIRST(E+T)FIRST(T)= FIRST(E)FIRST(T) = FIRST(T)= a,b即FIRST(E)= FIRST(T)= FIRST(F)= a,bE为开始符号，FOLLOW(E)=+,$FOLLOW(T)=FIRST(F)FOLLOW(E)=a,b+,$=a,b,+,$FOLLOW(F)=*,$FOLLOW(T)=*,$a,b,+,$=*,a,b,+,$即FOLLOW(E)=+,$

21、FOLLOW(T) =a,b,+, $FOLLOW(F)=*,a,b,+, $一、解：LR分析器对于输入id +id *id的格局变化和相应动作栈输入动作0id +id *id$移进0 id 5+id *id$按F>id归约0 F 3+id *id$按T>F归约0 T 2+id *id$按E>T归约0 E 1+id *id$移进0 E 1 + 6id *id$移进0 E 1 + 6 id 5*id$按F>id归约0 E 1 + 6 F 3*id$按T>F归约0 E 1 + 6 T 9*id$移进0 E 1 + 6 T 9 * 7id$移进0 E 1 + 6 T 9

22、 * 7 id 5$按F>id归约0 E 1 + 6 T 9 * 7 F 10$按T>T*F归约0 E 1 + 6 T 9 $按E>E+T归约0 E 1 $接受二、3.18 求下面文法E>E+T|TT>TF|FF>F*|a|b解：拓广文法：E>EE>E+T|TT>TF|FF>F*|a|bLR(0)项目集规范族(DFA构造过程)：I0：E>·EE>·E+TE>·TT>·TFT>·FF>·F*F>·aF>·bI1

23、：E>E·E>E·+T I2：E>T·T>T·FF>·F*F>·aF>·bI3：T>F·F>F·* I4：F>a·I5：F>b·I6：E>E+·T T>·TFT>·FF>·F*F>·aF>·bI7：T>TF·F>F·*I8 ：F>F*·I9：E>E+T ·T>

24、;T·F F>·F*F>·aF>·bE>EE>E+T E>TT>TFT>FF>F*F>aF>bFIRST(E)=FIRST(T)=FIRST(F)=a,bFOLLOW(E)=+,$FOLLOW(T)=a,b,+, $FOLLOW(F)=*,a,b,+, $表达式文法的分析表状态动作转移+*ab$ETF0s4s51231s6acc2r2s4s5r273r4s8r4r4r44r6r6r6r6r65r7r7r7r7r76s4s5937r3s8r3r3r38r5r5r5r5r59r1s4s5r17

25、3.18 为下面文法构造LR(1)分析表和LALR分析表E>E+T|TT>TF|FF>F*|a|b解：拓广文法：E>EE>E+T|TT>TF|FF>F*|a|bFIRST(E)=FIRST(T)=FIRST(F)=a,bLR(1)项目集族(DFA构造过程)： I0：E>·E，$E>·E+T，$/+E>·T，$/+T>·TF，$/+/a/bT>·F，$/+/a/bF>·F*，$/+/a/b/*F>·a，$/+/a/b/*F>·b

26、，$/+/a/b/*I1：E>E·，$E>E·+T，$/+I2：E>T·，$/+T>T·F，$/+/a/bF>·F*，$/+/a/b/*F>·a，$/+/a/b/*F>·b，$/+/a/b/*I3：T>F·，$/+/a/bF>F·*，$/+/a/b/* I4：F>a·，$/+/a/b/*I5：F>b·，$/+/a/b/*I6：E>E+·T，$/+T>·TF，$/+/a/bT>

27、3;F，$/+/a/bF>·F*，$/+/a/b/*F>·a，$/+/a/b/*F>·b，$/+/a/b/*I7：T>TF·，$/+/a/bF>F·*，$/+/a/b/*I8 ：F>F*·，$/+/a/b/*I9：E>E+T·，$/+T>T·F，$/+/a/b F>·F*，$/+/a/b/*F>·a，$/+/a/b/*F>·b，$/+/a/b/*E>EE>E+T E>TT>TFT>FF>

28、;F*F>aF>b表达式文法的LR(1)分析表状态动作转移+*ab$ETF0s4s51231s6acc2r2s4s5r273r4s8r4r4r44r6r6r6r6r65r7r7r7r7r76s4s5937r3s8r3r3r38r5r5r5r5r59r1s4s5r17考虑LR(1)项目集族没有同心的项目集。所以LALR分析表同LR(1)分析表。表达式文法的LALR分析表 状态动作转移+*ab$ETF0s4s51231s6acc2r2s4s5r273r4s8r4r4r44r6r6r6r6r65r7r7r7r7r76s4s5937r3s8r3r3r38r5r5r5r5r59r1s4s5r

29、173.23 证明下面的文法S>Aa|bAc|Bc|bBaA>dB>d是LR(1)文法，但不是LALR(1)文法。解：拓广文法：S>SS>AaS>bAcS>BcS>bBaA>dB>dLR(1)项目集族(DFA构造过程)： I0：S>·S，$S>·Aa，$S>·bAc，$S>·Bc，$S>·bBa，$A>·d，aB>·d，cI1：S>S·，$I2：S>A·a，$I3：S>b·Ac

30、，$S>b·Ba，$A>·d，cB>·d，aI4：S>B·c，$I5：A>d·，aB>d·，cI6：S>Aa·，$I7：S>bA·c，$I8 ：S>bB·a，$I9：A>d·，cB>d·，aI10：S>Bc·，$I11：S>bAc·，$I12：S>bBa·，$接受活前缀的DFA转换图： S>SS>AaS>bAcS>BcS>bBaA>dB&

31、gt;d表达式文法的LR(1)分析表状态动作转移abcd$SAB0s3s51241acc2s63s9784s105r5r66r17s118s129r6r510r311r212r4考虑LR(1)项目集族有1对同心的项目集。I5和I9合并成：I59：A>d·，a/cB>d·，c/a所以LALR(1)分析表如下所示。表达式文法的LALR(1)分析表 状态动作转移abcd$SAB0s3s591241acc2s63s59784s1059r5 r6r6 r56r17s118s1210r311r212r4因为LR(1)分析表中无分析冲突，而LALR(1)分析表中存在2处归约-

32、归约冲突，故所给文法是LR(1)文法，但不是LALR(1)文法。3.29 下面两个文法中哪一个不是LR(1)文法?对非LR(1)的那个文法，给出那个有移进-归约冲突的规范的LR(1)项目集。S>aAcA>Abb|bS>aAcA>bAb|b解：文法S>aAcA>bAb|b不是LR(1)文法。拓广文法：S>SS>aAcA>bAbA>bLR(1)项目集规范族：I0：S>·S，$ S>·aAc，$I1：S>S·，$I2：S>a·Ac，$A>·bAb，cA>&

33、#183;b，cI3：S>aA·c，$I4：A>b·Ab，cA>b·，cA>·bAb，bA>·b，bI5：S>aAc·，$I6：A>bA·b，cI7：A>b·Ab，bA>b·，bA>·bAb，bA>·b，bI8：A>bAb·，cI9：A>bA·b，bI10：A>bAb·，bS>SS>aAcA>bAbA>b 状态动作转移abc$SA0s211acc2s

34、433s54s7r365r16s87s7 r398s29s1010r2有移进-归约冲突的规范的LR(1)项目集是I7：A>b·Ab，bA>b·，bA>·bAb，bA>·b，b3.29 对是LR(1)的那个文法S>aAcA>Abb|b解：拓广文法：S>SS>aAcA>AbbA>bS>SS>aAcA>AbbA>b状态动作转移abc$SA0s211acc2s433s6s54r3r35r16s77r2r24.7 用S的综合属性val给出下面文法中s产生的二进制数的值。例如：输入1

35、01.101时，S.val=5.625。SL.L|LLLB|BB0|1(a)仅用综合属性决定S.val。(b)用L属性定义决定S.val。在该定义中，B的唯一综合属性是c（还需要继承属性），它给出由B产生的位对最终值的贡献。例如，101.101的最前一位和最后一位对值5.625的贡献分别是4和0.125。解：(a):产生式语义规则SL1.L2 S.val=L1.val+L2.val/pow(2,L2.length)SLS.val=L.valLL1 B L.val=L1.val*2+B.valL.length=L1.length+1 LBL.val=B.val

36、60;LS  L.val=S.val L.length=1 B0  B.val=0   B1 B.val=1/pow(a,b)为a的b次方。(b):先将文法改写为：  SL.R|LLBL|B RRB|B   B0|1 然后有：/其中i是B的继承属性，val和c是综合属性 产生式语义规则SL.R   S.val=L.val+R.valSLS.val=L.val LBL1 B.i=

37、L1.c*2L.c=L1.c*2 L.val=L1.val+B.c LB B.i=1L.c=1L.val=B.c RR1 B  B.i=R1.c/2R.c=R1.c/2 R.val=R1.val+B.c RB B.i=0.5R.c=0.5 R.val=B.c B0B.c=0B1 B.c=14.10 文法如下：S(L)|aLL,S|S (a)写一个翻译方案，它输出每个a的嵌套深度。例如，对于句子(a,(a,a)，输出的结果是1 2 2。 (b)写一

38、个翻译方案，它打印出每个a在句子中是第几个字符。例如，当句子是(a,(a,(a,a),(a)时，打印的结果是2 5 8 10 14。解：(a):SS.depth=0SSL.depth=S.depth+1 (L) Saprint(S.depth)   LL1.depth=L.depthL1,S.depth=L.depthS   LS.depth=L.depthS (b):   SS.in=0S SL.in=S.in+1(L)S.out=L

39、.out+1   Sa S.out=S.in+1；print(S.out)   LL1.in=L.inL1，S.in=L1.out+1SL.out=S.out LS.in=L.inSL.out=S.out4.3 为文法 S(L)|a LL,S|S(a)写一个语法制导定义，它输出括号的对数。并画出(a),(a)的注释分析树。(b)写一个语法制导定义，它输出括号嵌套的最大深度。并画出(a),(a)的注释分析树。解：(a): 注意：用下标加以区分。构造表达式语法树的语法制导定义产生式语义规则

40、SSn print(S.val)S(L)S.val = L.val + 1 Sa  S.val = 0 L  L1 , SL.val = L1.val + S.valL  S  L.val = S.valSnS.val=4()L.val=3L.val=2，S.val=1()L.val=0S.val=2()L.val=1S.val=1()L.val=0S.val=0aS.val=0a(b): 注意：用下标加以区分。构造表达式语法树的语法制导定义产生式语义规则SSn&#

41、160;print(S.val)S(L)S.val = L.val + 1 Sa  S.val = 0 LL1,SL.val = max(L1.val,S.val)LS  L.val = S.valSnS.val=3()L.val=2L.val=2，S.val=1()L.val=0S.val=2()L.val=1S.val=1()L.val=0S.val=0aS.val=0a4.7 用S的综合属性val给出下面文法中s产生的二进制数的值。例如：输入101.101时，S.val=5.625。SL.L|LLLB|BB0

42、|1(a)仅用综合属性决定S.val。(b)用L属性定义决定S.val。在该定义中，B的唯一综合属性是c（还需要继承属性），它给出由B产生的位对最终值的贡献。例如，101.101的最前一位和最后一位对值5.625的贡献分别是4和0.125。解：(a):产生式语义规则SL1.L2 S.val=L1.val+L2.val/pow(2,L2.length)SLS.val=L.valLL1 B L.val=L1.val*2+B.valL.length=L1.length+1 LBL.val=B.val LS  L.val=S.val L.length=1 B0  B.val=0   B1 B.val=1/pow(a,b)为a的b次方。(b):先将文法改写为：  SL.R|LLBL|B RRB|B B0|1 然后有：/其中i是B的继承属性，val和c是综合属性