编译原理作业题.doc

第一章习题一1 解释名词：源语言、目标语言、翻译器、编译器和解释器。答：源语言：被翻译器翻译的语言，用于书写源程序的语言。目标语言：被翻译器翻译之后得到的语言，用于书写目标程序的语言。翻译器：能够完成从一种语言到另一种语言的变换的软件。编译器：一种特殊的翻译器，要求目标语言比源语言低级。解释器：解释器是不同于编译器的另一种语言处理器。解释器不像编译器那样通过翻译来生成目标程序，而是直接执行源程序所指定的运算。第二章 词法分析作业：假设=0,1，求1. 写出包含010的所有串的正规式2. 写出不包含010的所有串的正规式 答： 1. （0|1）*（010）（0|1）* 2.（10*1）*|（11|00）*|0111*0）* .2.（0|1）*010（0|1）*解：（1）RE的分解树如下：r17r16r11*r15r14()|r12r1301r100r9r81r7r60r5*r4r3()|r1r201（2）由分解树及基本的Thompson构造算法逐步构造等价的NFA过程如下：230Startr1：451Startr2：1243501r3、r4:6Start012435016r5:7Start780Startr6：01243501670r7:8Start891Startr8：0124350167801r9:9Start9100Startr10：0124350167801r11:9100Start12130r12：Start14151r13：Start1112141315Start0116r14、r15：10Start1112141315011617r16：Start012435016780911001112141315011617r17:（3）由子集法构造等价的DFA过程如下：01ABCBBDCBCDECEFGFFGGHIHFGIFI其中含有r.初态的是A作为新的DFA的初态，含有原r17终态的是E、F、G和H作为新的DFA的终态。做出对应DFA的状态转换图如下：StartA0HBC101D010E1F0G101011I010（4）直接由分割算法处理该DFA，如得到的DFAmin与原DFA一致说明原DFA本身就是最简的：由于导致A，B，C和D落入的状态集是不等价的，说明A，B，C和D是不等价的，故A，B，C，D应该分裂为A，B，C和D，故：由于落入不同的状态集（相对来说是两个不等价的状态集），说明A，C和B是不等价的，故A，B，C，D应该分裂为A，C和B，故：由于落入同一个状态集，故E，F，G，H，I暂不分裂。由于落入同一个状态集，故E，F，G，H，I暂不分裂。故最终划分为：说明A和C是等价的，E、F、G、H和I是等价的。合并等价状态（A和C中保留A，E、F、G、H和I中保留E）并处理对应弧线得最小化DFA如下：A0B01D10E110001012103110010101022303331.010011232403124340110200403101013.1考虑文法 S ( L ) | a L L , S | S(a)建立句子（a,(a,a)）和(a,(a,a),(a,a)的分析树。(b)为（a）的两个句子构造最左推导。(c)为（a）的两个句子构造最右推导。(d)这个文法产生的语言是什么。（a,(a,a)）的分析树 S（L ）L ， SS （ L ）a L , S S a a(a,(a,a),(a,a)的分析树 S（ L ） L ， S a ( L ) L , S a ( L ) L , S a ( L ) L , S S a a（a,(a,a)）的最左推导Slm (L) lm (L,S) lm (S,S) lm（a,S）lm (a,(L) lm (a,(L,S) lm (a,(S,S) lm (a,(a,S) lm (a,(a,a)(a,(a,a),(a,a)的最左推导Slm （L） lm (L,S) lm (S,S) lm (a,S) lm (a,(L) lm (a,(L,S) lm (a,(S,S) lm (a,(L),S) lm (a,(L,S),S) lm (a,(S,S),S) lm (a,(a,S),S) lm (a,(a,a),S) lm (a,(a,a),(L) lm (a,(a,a),(L) lm (a,(a,a),(L,S)lm (a,(a,a),(S,S) lm (a,(a,a),(a,S) lm (a,(a,a),(a,a)（a,(a,a)）的最右推导Srm (L) rm(L,(L) rm (L,(L,S) rm (L,(L,a) rm (L,(S,a) rm (L,(a,a) rm (S,(a,a) rm (a,(a,a)(a,(a,a),(a,a)的最右推导 Srm (L) rm (L,S) rm (L,(L) rm (L,(L,S) rm (L,(L,(L) rm (L,(L,(L,S) rm (L,(L,(L,a) rm (L,(L,(S,a) rm (L,(L,(a,a) rm (L,(S,(a,a) rm (L,(L),(a,a) rm (L,(L,S),(a,a) rm (L,(L,a),(a,a)rm (L,(S,a),(a,a) rm (L,(a,a),(a,a) rm (S,(a,a),(a,a)rm (a,(a,a),(a,a)（d）该文法产生的语言是括号匹配的串，串中的各项用“，”隔开，项可以是括号匹配的子串或a3.2考虑文法 SaSbS|bSaS|（a） 为句子abab构造两个不同的最左推导，以此说明文法是二义的。（b） 为abab构造对应的最右推导。（c） 为abab构造对应的分析树（a）1.Slm aSbS lm abSaSbS lm abaSbSlm ababSlm abab2.S lm aSbSlm abSlm abaSbSlm ababSlm abab(b)Srm aSbS rm aSbrm abSaSbrm abSabrm abab(C)分析树（1） Sa S b S a S b S 分析树（2） Sa S b Sa S b S (d)该文法产生的语言是a、b个数相等的ab串含空串习题33.3下面的二义文法描述命题演算公式，为它写一个等价的非二义性文法。 SS and S| S or S| not S| true| false|(S)答：E-E or T | TT-T and F | FF-not F | (E) | true | false3.10 构造下面文法的LL(1)分析表D-TL T-int | realL-id RR-,id R|答：First(TL)=int,realFollow(D)=#First(T)=int,real Follow(T)=idFirst(D)=int,realFollow(L)=#First(int)=int Follow(R)=#First(real)=realFirst(id R)=idFirst(L)=idFirst(,id R)=,First()=First(R)= , , IntRealId,#DD-TLD-TLTT-intT-realLL-id RRR-,id RR-3.11 下面的文法是否为LL（1）文法？说明理由。（两种方法）S-A B | P Q x A-x y B-b cP-d P | Q-a Q |答：方法一：First(AB)=x First(PQx)=d,a,x因为：First(AB)First(PQx)=x所以此文法不是LL(1)文法。方法二：First(AB)=x Follow(S)=#First(PQx)=d,a,x Follow(A)=bFirst(x y)=xFollow(B)=#First(b c)=bFollow(P)=a,xFirst(d P)=dFollow(Q)=xFirst()=First(a Q)=aFirst(S)=d,a,xFirst(A)=xFirst(B)=bFirst(P)= d,First(Q)= a,xdab#SS-ABS-PQxS-PQxS-PQxAA-x yBB-b cPP-P-d PP-QQ-Q-a Q该文法有分析表有多个入口，不是LL（1）文法。3.19 证明下面的文法不是LL（1）文法 SS A | AA-a答：该文法存在左递归所以不是LL（1）文法。3.20 证明下面的文法是LL（1）文法 S-AaAb| BbBaA-B-答：First(AaAb)=aFollow(S)=#First(BbBa)=b Follow(A)=a,bFirst(A)=Follow(B)=a,bFirst(B)=First()=First(S)=a,b 1，该文法无二义性，无左递归 2，First(AaAb)First(BbBa)= 3，First(A) First(B) 但是： First(A)Follow(A)=First(B)Follow(B)=所以是一个LL（1）文法。习题33.18考虑下面的文法 EE+T | T TT F | F FF*| a| b(a) 为此文法构造SLR分析表。(b) 构造LALR分析表。答： (a) E E E E + T E T T TF T F F F* F a F bTI9baF+I7I5FTEEE E+TE TT TFT FF F*F aF bI0EEE E+TI1EE TT TFF F*F aF bT FF F*I2I3aF abF bI4E E+TT TFT FF F*F aF bI6FT TFF F*abI4I5F F* I8*E E+TT TFF F*F aF bFaI7I4bI5I3I4I5Follow(E) = #,+Follow(T) = #,+,a,bFollow(F) = #,+,a,b,*习题33.18考虑下面的文法 EE+T | T TT F | F FF*| a| b(c) 构造LR分析表。答： (b) E E E E + T E T T TF T F F F* F a F bI3I4I5I0I4I5I3I9I2baFFabEI1EE ,$EE+T,$/+E T ,$/+T TF,$/+ /a/bT F ,$/+ /a/bF F* ,$/+/a/b/*F a ,$/+ /a/b/*F b ,$/+ /a/b/*E E,$E E+T,$/+I6E E+T,$/+T TF,$/+ /a/bT F,$/+ /a/bF F*,$/+ /a/b/*F a,$/+ /a/b/*F b,$/+ /a/b/*E E+T,$/+T TF,$/+ /a/bF F*,$/+ /a/b/*F a,$/+ /a/b/*F b,$/+ /a/b/*I7I4I5TET,$/+TTF,$/+ /a/bFF*,$/+/a/b/*Fa,$/+/a/b/*Fb,$/+/a/b/*TbaFI4I5I7TTF,$/+ /a/bFF*,$/+ /a/b/*FTF,$/+ /a/bFF* ,$/+ /a/b/*aF a,$/+ /a/b/*bF b,$/+ /a/b/*F F*,$/+ /a/b/*I8*状态Action动作Move+*ab#ETF0S4S51231S6acc2R2S4S5R273R4S8R4R4R44R6R6R6R6R65R7R7R7R7R76S4S5397R3S8R3R3R38R5R5R5R5R59R1S4S5R174.7用S的综合属性val给出下面文法中产生的二进制数的值，例如，输入101.101时，s.val=5.625。SL.L|LLLB|BB0|1(a) 仅用综合属性决定s.val。(b) 用L属性定义决定s.val。在该