第一章1. 编译程序绝大多数时间花在( B )上。A 出错处理 B 词法分析C 目标代码生成 D 表格管理2编译方式与解释方式的根本区别在于一是否有目标代码生成.3. 编译程序是对_A_A 汇编语言的翻译B 高级语言程序的解释执行C 机器语言的执行D 高级语言的翻译第二章1. 令2=住，b， E上的正规式和相应的正规集的例子有:正规式正规集aaa I ba,babab(aI b)(aIb)aa,ab,ba,bba *e ,a,a,任意个a的串(a I b)*e ,a,b,aa,ab所有由a和b组成的串(a I b)*(aa I bb)(a I b)*上所有含有两个相继的a或两个相继的b组成的串2.E=a,b,c，则aa*bb*cc*是上的, 正规式，它所表示的正规集为 L= ambncl | m,n,l=11.DFA M接受的字集为。A 以 0 开头的二进制数组成的集合 B 以 0 结尾的二进制数组成的集合 C 含奇数个 0 的二进制数组成的集合D含偶数个0的二进制数组成的集合构造下列正规式相应的 NFA(1) (a|b)*abb(2) (a|b)*a(a|b)(3) (a|b)*(aa|bb)(a|b)*随堂练习已知一状态转换图如图所示，且假定l=j0=0,试求从状态0出发经过一条有向边b而能 到达的状态集J和JCLOSURE(J)。例28正规表达式(a | b) *(aa I bb)(a I b)*的NFA M如图2-14所示，试将其确定化 为 DFA M。图 2-14 例 28的 NFA M表 24 例 28的转换表IIa% 丄 21,2,31241231,235,6,Y1241241,2,31,2,4,5.6.Y1,2,3,5,6,Y1,235,6,Y1,2,46Y1,2,4,56Y1236Y1,2,4,5.6.Y1,2,4,6, Y 表2.5例2.8的状态转1,2,3- &YF换矩阵1,2,4,5.6.Y1,26Y1,2,3,5,6,Y1,2,46Y图2 15例28未化简的DFA M第三章随堂练习(一)设字母表=a, b，试设计一个文法，描述语言L=a2n,b2n|n三 1 分析： n=1 L=aa,bbn=2 L=aaaa,bbbbn=3 L=aaaaaa,bbbbbbL=,aa,bb,aaaa,bbbb,aaaaaa,bbbbbb, - 文法 G=(Vt,VnS E) VT=a,b VN=S,A,B 方法一：E： STaa|aaA|bb|bbBAaa|aaABTbb|bbB方法二：E： STA|BAaa|aAaBTbb|bBb注意： E： STaa|bb|Saa|Sbb 是否 可行？ 随堂练习(二)给出下面语言相应的文法(1) L=ambn | m,n 三 1G(S): STABAa|AaBTb|bB(2) L2=anbnci | n 三 1,i 三0G(S): STAB Aab|aAb BElcB(3) L3=anbncmdm | n 三 1,m 三 1G(S): STABATab|aAbBTcd|cBd(4) L4=a2n+1 | n 20STa|aAATaS或者 STa|aSa随堂练习1. 文法G:STxSx|y所识别的语言是.A xyx B (xyx)* C xnyxn(n20) D x*yx*2. 文法GN= (b, N, B, N, N-b | bB, B-bN),该文法所描述的语言是A. L(GN)=bi | i20B. L(GN)=b2i | i三0C. L(GN)=b2i+1| i20D. L(GN)=b2i+1| i21随堂练习1. 设有文法GT: TTT*F|FFTF f P|PPT(T)|i直接短语：PJ*F短语： T*Pf (T*F), Pf (T*F), P, (T*F), T*F句柄： P求T*P (T*F)句型中的所有短语、直接短语、句柄。2. 设有文法 GS: ST(AS)|(b)AT(SaA)|(a)求出符号串(A(SaA)(b)的短语、直接短语、句柄。1设有文法GA: ATAc | Aad | bd | e,消除直接左递归后文法GA改写为？2. 下述文法GS是否含有左递归？GS: STQc | cQTRb | bRT Sa | a例 3.71. 设有文法GE: ETTEET+TE | TTFTTT*FT | FT(E)| iFIRST(T)=,FOLLOW(F)=.A,(,i- B ,*, - C ,*,+,),#- D ,+,),#-2. 对下面文法GS计算每个非终结符的FIRST集和FOLLOW集。STa | ! | (T)TSTTT,ST | 文法 GSSTuBDzBTBv|wDTEFETy |FTx |计算文法的FIRST集合和FOLLOW集合 构造这个文法的LL(1)分析表。例 1 将文法 GS: STaAbATde |d改写为LL(1)文法。该文法没有左递归，利用提取公共左因子的方法对其进行改写：GS: STaAbATdAATe | 判断下面文法是否为LL(1)文法，不是的话请将其改写为LL(1)文法：STad | AeATaS | bAFIRST(ATaS)=FIRST(aS)=a, FIRST(ATbA)=FIRST(bA)=bFIRST(STad)=FIRST(ad)=a, FIRST(STAe)=FIRST(A)=a,b 所以FIRST(STad) flFIRST(STAe)工该文法不是LL(1)文法。提取公共左因子,改写为： GS: STaS | bAeSTd | SeATaS | bA随堂练习设有文法 GS:STAATB | AiBBTC | B+CCT )A* | (1) 将文法GS改写为LL(1)文法(2) 求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。(3) 构造相应的预测分析表1. 设有文法 GS: STa | ! | (T)TTT,S | S 计算文法G的FIRSTVT和LASTVT集。1. 设有文法GS: STAAB | AiB BTC | B+CCT)A* | ( 试给出句型C+Ci(的短语、句柄和素短语，指出最左素短语。2. 设有文法 GS: ETE+T | E-T | TTTT*F | T/F | F FTFP | PPT(E) | a试给出句型T-T/F+a的短语、直接短语、句柄和最左素短语。随堂检测设文法G为STSSTASTBATaAbAT cBTaBbBTd 令 l=ST SCLOSURE(I)=S今 S , ST A, ST B, A aAb, A c, B aBb, B d1. 设有文法 GS： STaAAAbAb求识别该文法所有活前缀的 DFA。2. 设有文法 GS： SrDDD,i | i 求识别该文法所有活前缀的 DFA。 例320判断下述文法GS是哪类LR文法。GS: (1) STL=R(2) STR(3) LTR(4) LTi(5) RTL解答首先将文法GS拓广为GS：GS+: (0) STS(1) STL=R(2) STR(3) LTR(4) LTi(5) RTL构造文法GS的LR(O)项目集规范族如下：I0： STSI2: STL=RI5： STRSTL=RRTLI:6STL=RSTRl3： LT*RRTLLT*RRTLLT*RLTiLT*RLTiRTLLTiI:7STL=RSTSJ LTiI8: LT*RI:1例322已知算术表达式文法GE如下，试构造该文法的LR分析表:G*E: ETEE I E*EI (E) I i将文法G拓广为文法GS:(O)STE(1) ETEE(2) ETE*E(3) ET(E)(4) E9列出LR(O)的所有项目:1. STE5. ETEE 9. ETE*E 13. ET(E)2. STE 6. ETEE 10. ETE*E 14. ET(E)3. EEE7. ETE*E11.E9(E)15.Ei4. ETEE8. ETE*E12.ET(E)16.ETi用CLOSURE方法构造出文法GS的LR(O)项目集规范族，并根据状态转换E算术表达式文法GS的DFAE E+EE iE+B、EE E+吐E f E*E E+EE+HI1： MEE E+王E E*E:(E)E E+耳EE E函数GO画出文法GS的DFA，如图3-25所示。已知 FOLLOW(S)=#由 STS 得 FOLLOW(S)FOLLOW(S),即 FOLLOW(S) =#由 ST.Se.得 FIRST(e)FOLLOW(S), 由 STS; .得 FIRST(;)FOLLOW(S), 即 FOLLOW(S)=#,e,;I5： STiS要求归约，而STiSeS和STS;S却要求移进，即有：FIRST(e)flFOLLOW(S)=eHeFIRST(;) HFOLLOW (S)=;却也即冲突字符为“ e”和“;”。15：由于是活前缀“S达到I5的，因此遇到后面的“e,则应与前面的活前缀“S结合(就近 原则)以便形成iSeS句型，故应移进；而遇到后面的“;”时，活前缀“S即为一个语句，故 应归约。I6和I8引起冲突的字符是“；”。16:由于是由活前缀“S;S到达16的，因此遇到后面的则应将活前缀“S;S归纳为S,故66应归约。18：由于是由活前缀“iSeS到达18的，因此遇到后面的则应将活前缀“iSeS归纳为S，88故应归约。表*21无冲突的SLR(l)分析表1表达式E的值描述如下:产生式(0) STE(1) ETE(D+E(2)(2) ETE(D*E(2)(3) ET(E(D)ETn语义动作print E.val