编译原理答案(主编张晶)

1、标准文档1.1翻译程序:臥某一种程序设计语言所编写的程序作为翻译或力0J的对象， 将它翻译成与之等价的另一种语言的程序0高级语言虽然优越，但计算机硬件却只懂得自己的指令系统，即只能直接 瓠行相应机器语言格式的代码程序而不能直接执行用高级语言或汇编语言 编写的程序*因此高级程瘵设计语言需要翻锋程序将苴翻译成为计算机能 理解与执行的机器语言的程序。1.2编译程序解释程序：从高级语言到机器语言或汇编语言的翻译程序* 编译程序；产生目标程序然后再执行目标程序，可以反复执彳亍。解释程序：不产生目标程序，逐句翻译执行，只能执行一次，若需重新 执行，则必须重新解释程序。1.3实用文案(1) 通常一个编译程序

2、由词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成出错管理和符号表管理八部分组成。(2) 各部分的任务：i司法井析：从左到右逐个字符的读入源程序按照源语言規定的词法规贴对构成源程序的字符流进行扌瑚和分解，从而识别出一个个单词，并把 他们表示成机内单词形式纺语法分析：根採源语言的语法規则扌词序列分解成各类语法单位，并指出其中的语法错吴语义分析：分析各语法成分的含义和力能，即它1门的属性或在执行时应曲亍的运算或操作。中间代码生成：在语法分析和语义分析的基础上，根扌居语法成分的语义对其翻译，翻译成在语义上等怕的中间代码的语言。代码优化：对代码进行改造变换，目的是使生成的目标代码更为

3、高效，目皓时间和省空间。目标代码生成：转换为等价的目标代码。出错管理：员贵发现源程序中可能出现的错误，并把错误报告给用户，指出错误的tJ厮竣生错误能墨符理：记录源程序中使用的标识符和毎个标识符的答种属性，臥便后续的工作中Bffft用。1.4编译程序的组织方式有3种：(1逻辑组织方式，即将编译过程划分为六个阶段，贯穿始终的是符号 表管理和出错管理*(2编译过程分为前端和后端两个部分，前端主要依輟于源语言，它由 几乎独豈于目标机器的阶段或阶段的一部分组成后端是编译器中依赖于目 标机器的部分，它一般独立于源语言而与中间语言有关。(3采用“吩遍”的形式，即编译过程可以由一遍或多遍来完成。(遍： 在编译

4、过程中，对源程序或其等价的内部表示从头到屋扫视，幷进行相应的 加工处理进而完成规定任务的过程称为编译的一遍)2.1标准文档最左推导： E3T=F=i E =T = F =旧=(T) =(F) =(i) E=T z=T*F=F*F= 产F = 产i E =E+T=T+T =F+T =i+T =i+T*F =i+F*F =i+产F ni+产i E =E+T =T+T =F+T =i+T =l+F = k(E) =i+(T) = l+fT*F)=i+(F*F) =i+(F*F) =i+F) =i+(門) E =E+T =T+T =T/F+T =F/F+T =i/F+T =i/i+T =i/i+T*F

5、 =i/i+F*F=i/i+i*F =i/i+i/i最右推导：E=T=F=i E=T=F=(E) =(T) n (F) =(i) E 二E+TdE+I/F =E+T/i 二 E+M =E+i/i =T+i/i F+i/i qi+i/i E =E+T=E+F = E+(E) = E+(E+T) = E+(E+F) =E+|E+i) =E+(T+i)二* E+(F+i) E+(i+i) =T+(i+i) F+i+i)二 i+(i+i) E =E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*l=T/F+l*i=T/i+i/i =F/i+i/i =i/i+i/i实用文案标准文档语法树：

6、AE 4-I /K 【T /实用文案EE/NI +I AF f E I /Ni E2.2标准文档此西答案不唯一，正确即可4 XOS I 1AA-OA | EaS | bA | fA- bA | cC | ECCC I s-a5 | eS-OA | IBADS | 1C |0B-1S | 0C| 1C-OB | 1A2.3实用文案标准文档此题答案不唯一，正确即可。 S-aAbCAaAb | eC-cC | ESISO I 1A0A-OA1 | 01SOIAAlAl | 0SDiAIDjA-D5A|D：D1-1|2|3|4|5|6|7|S|9Dr2|4|6|8D3-0|l|2|3|4|5|6|7|

7、8|92.4(1)终结符；0* 、 非终结符：S. L 幵皓符号:S实用文案2.5(3) CD(L)二 (LPS)二 (SfS)二 (aFS)二 (ara)$ = (L) = (LfS) = (S-S) = (L).S = (S)fS) = (a)5)=(aML = (aK(S) = a)4a(4) S= (L) = (LS) = La) = (Sa) = (ara)5= L) = (LS) = L(L = (L(S =仏剛= (SJa)= I(L)4a = (SMa)= (却)(1) S=aSbS =aSb =abSaSb=abSab =abab 5 =a5bS =aSba5bS =a5ba

8、Sb aSbab =abab由于句子abab在两种不同的最右推导，所以该文法为一个二义性文 法(2) SaSbS abSabaSbSababSabab 5 =aSbS =abSaSbS = abaSbS=aba bS =4abab由于句子abab在两种不同的最左推导，所汰该文法为一个二义性文J eZ 1由于句子mbab存在两棵不同的语法树所臥该文法为一个二义性文法。2.6根据1型文法的是义可知该文法为1型文法。2.7(1) Liabtd-1 0=1, j=0(2) L2=baa | i=0)=l2.8(1) P=SABS | Aa | G A-a?B-bAB5 =aBS=aSBBS =aBBS

9、 =abBS =abbS =abbAa =4abbaa最右推导：S =ABS =ABAa = ABaa ASBBaa =ASBbaa = ASbbaaAbba a=abbaa2.9生成该语言的文法为G:S-ABA-aAd | DD-bDc | beB-Be | e2.10例如对于句子abc： 5 =AB =aB =abc 5 =DC abC = a be由于句子日be存在两种不同的最左推导，所I汰该文法为一个二义性文法3.1(1)正规式为:s=o+|onr有穷自动机为:(2)正规式为：S=aa+(bc)+有穷自动机为：3.2（1）状态转换團为:(2)右线性文法为:| 0AARIA | OBBW

10、B | IB(b)SlB | OAA-1A | OCB-HJB | 1C90C | 1C3）同以,1幵头.由g 1组成的数字串,或以D开头，至少包含两个0 的由讥丄组成的数字串*（b）臥o开头，至少含有2个0的由0、1组成繼字串，或以1开头, 至少含有2个1的由0、1组成的数字串。3.3 bmb、bbbv ba bbc（2）以maa* aat aba.占bb结尾的由a% b组咸的符号串;列举四个较短的句子为：aaa aab aba abb（打含有2个。的宙0、1组成的符号串；列举四个较桓的句子为：00、100, 010 001.（4）以0或1结尾的前面由若干个01组成的符号串；列举四个较短的旬

11、子为：o. r 010, 011c3.4使用子集法进行确定化，并对状态重新进行命名（0. 1. 2. 3:01二 *SrArB0AAC1APB2ArBFC1A.BPC1ArBrT3傀B2A,Bfq1AfB23A.BX1APB2确走化的有穷自动机为:3.5使用子集法进行确定化，并对状态重新进行命名（久B、： D、E）:01n *1A2,4B2,4B(5,61D(3)C3 C1A*A6)D6*6E何 E确定化的有穷自动机为:3.634(D*423使用最小化算注后四个状态可以凛少为三个状态：1,4,2,3 画出的最小化的DFA为：3.7与正规式蒔价的有穷自动机为:3.8正规式：1(0|1)*00NF

12、A如下團所示；101n闵 10BX-D 2CrD 2忆 D*E3QD4CAE： 3MEtF 5QD4C-D)4比D同 3IGD4*CrD,E,F5t,D.E,F) 5CD4DFA如下團所示;使用最小化聖去后，5个状态可以凛少为心个状态：也册剧冏，以2 作为状态代表，最小化后的DFA为：3.9文法G对应的自动机为:该自动机是不确定的。使用子集法进行确定化，并对状态重新进行命名（As B、C）:101=RAABABA,S C0*A,S CA,S CA B则DFA如下團所示:标准文档3.10实用文案标准文档使用子集法进行确定化，并对状态重新进行命名（X、3. 4、5.灵7）:101=S1VB2BX3

13、A.B2 JA,BfQD 4B5BfC3AFBfC 6BfD7* 仏 BCD4A.BD 4B.D1B5gB6B5A7BrC 6AzBrQD 4B,D7* D 7A.B.GD 4 1DFA如下團所示;000200030使用最小化算法后7个狀态可決减少为6个状态；2”创5阀他7,以4作为状态代表，最小化后的D啟为：3.11(1) (a | b厂的 NFA为:梗用子集法进行确定化，并对状态重新进行命名（A、B）:1abm2.3 B(2,3 B* (2.3)2.3 B2,3) BDFA如下團所示:使用最小化算法后,2个状态可以减少为1个状态:A（Bb決A作为状态代表，最小化后的DF自为:(2a|bra

14、(a |b)的 nfa为:使用子集法迸行确定化，并对状态重新进行命名（茲氛3. 4, 5）:1ab=1,Z32,3,42.3323323A5 423,55乙3(2342.33*23 A 52,3t4fS 42,3,55*2.3,52,3r42.33DFA如下團所示:使用最小化算法后，5个状态可以减少为幼个状态：lr3J2r4r5J 以.1作为状态代表：最小化后的DFA为：(3H0 I tO I 11W 1 的 NFA为:使用子集法进行确走化，并对状态重新进行命名（K 2.沢4：101nu 132.432闾 241X4 3432*540DFA如下图所示:该團已为最1毗的DFA。（4 （0| 1）

15、 ） 101 可简化为（0 | 1） 101,它的 NFA为:使用子集法进行确定化，并对状态重新进行命名(A, B. C. D. E):101= 1.232,32,3,4 C2J2,3234 C2,3,42,3P5 D23A C23Q2.3B23A623.5 D234 CDFA如TF图所示:使用最小化算法后，5个状态可以;咸少为山个状态： 以A作为状态代表，最小化后的DFA为:3. 12(a | b)a白的NF血为:使用子集法进行确定化并对状态重新进行命名5、驭0 )：1ab=1,23 a(2t3r4Jc2331 B23-4503c2.3 C2341c*2,3AS23 绻 5231cDFA如下

16、图所示:使用最小化M法后，4个状态可咲减少为2个状态：A.Cj/BLfDhA作为状态代表，最小化后的DFA为：实用文案2)(b a | a)NFA为:使用子集法进行确走化，并对状态重新进行命名（A,氛C”1abn *1,2,4233 C*2.43C c2r4DFA如下團所示:态代表，最小化后的DF血为:仪旺u2.寸 一A屈扯 XBVTA丘 gp 尿屁地”点期不八丘辔 pum 屈班芝冠aq个八住理7X4-aspga-v3BTE 个诂5呆55*!*削-旱LdLO个山二LU)个 52qsT8JBW-U5J、5aSTca的T-Tb | b: bbfc根据产生式，可求得该文法中各非终结符的FIRST集和

17、FOLLOW集如下所示:产生式FIRST 集FOLLOW 集SAB(a, Uc#A-aAb | Eab,cBbB | cb(c#根揚产生式，可求得该文；去中各非终结符的FIRST集和FOLLOW集如下所示:产生式FIRST 集FOLLOW 集2 aAbDe | dgd #, af e A- BsD | ea, cfd, e,sbB- Sac | cD | eardtcsD 今 Se | Eard bF e,s4.4根据文法的各个产生式 可求得FIRST ft. FOLLOW集和SELECT集如下所示:产生式FIRST 集FOLLOW 集SELECTS-eTe#eS-RTd, aP bf s如b

18、T-DRWb#afbT-e#RdRddR-Ela.b,#DWaId,#aHbdbb由于每一非终结符的各个候选式的SELECT集互不相交，所以该文法为LL(1)文法.4.5根据文法的各个产生式，可求得FIRST集、FOLLOW集和SELECTajOTS所示：严生式FIRST 集FOLLOW 隼SELECT 集aFbr #他a,bR #a-bca,b,#a,bP #6-a2g#aikSC-bbttbC-#该文法的同一非络结符的各个产生式的可选集的交集如下；SELCnB-a)n5ELECT(B)=SELECT(Cb)nSELECT(C 根擔LL文建的定义可知，该文法杲一个L1文法亠(2)构造的LL分

19、析表対:ab#sS-A#S-A#AA-BCA-BCABCBB-aB-Cc-bSe4.6消除左递归后的文法为：5F | (T)TsrTTsr | 对消去左递归后的文法求FIRST集s FOLLOW集和SELECT集:产应FIRST 集FOLLOW 集SELECT 集S-aa骷)a5)(t-star()1()T%sr-0)TW)根据SELECT可得到消去左递归后文法的L中吩析表知a(rSTT-STFT-STrTTTwTyr由于同一非终结符的各个候选式的可选集互不相交所以该文法为LL文法标准文档4.7由于该文法存在公共左因子，所次该文法不是LL文法改写文法为:S-NSr今 |EE9SEETe I +

20、E改写后文法与原文法等价且是山1文法。(2)由干该文法存在直接左递归，所以该文法不是LL文法。 改写文法为：A今BNaUba, | eBnC0F | E| DD-(A) | i改写后文法与原文法等价且是LL文法。4.8(1)与GA等协的文法甲伪:A-aArATAbe | 0-IBr实用文案:铢昨i鲍阴加(323e,92q岛q启pp用pzp-#M23e,v盯eaflVVe(PJ#)eev13313S蕭 MCmCHiglSHH:土昂丄呼毒丄RUS血零MOllOd赴來巨f竿玉睾心号劭因*BX1W标准文档aedbAA-aAfXA?-ABe心eA%BB1Bf-eBTbB谕入串日3d餅的分析过程为:步骤分

21、析栈余留输入串所用产生式1#AaadettA-aA*2#Araaade#3#Arade#AABe4ffeBAa de#A-aA55tteBAaade#6ffeBAde#Af-7#eBde#8#eBrddetf9#eBr曲B510#e11分析成功4.9各个产生式的Fl RST集、FOLLOW集和SELECT集如下:产生式FIRST 集FOLLOW 集SELECT 集SaBc(a)#aS-bABbbA-aAbaW#aA-bbbBbb訂b)B今EC,#根g SELECT可得到LL分析表为:abc#sS-aBcSABAA-aAbA今bBB-b符号串bab的分析过程为:分析桟余留输入串所用产生式1#Sb

22、abbbttS-bAB2#BAbbabbb#3#BAabbb#A-aAb4#8bAaabbbff5ffBbAbbb#A-b6#Bbbbbb#7帕bbbti8b#B-b9#b10分折成功由上述分析过程可知符号串babbb为该文进的句子,4.10各个产生式的FIRST集、FOLLOW集和SELECT集女吓:产生式FIRST 集FOLLOW 集SELECT 集S-TPa,c a(c P-aSa代bap*优bT-QRa,c(aA#Ja-cR-Taca, b, #(a,cR今E町af bF #QaSbaaQ云cc根据各个产生式及其SELECT集可写出递归下降分析程序如下:实用文案王朗数：scan;cal

23、ls；if tokens then accept; else error;MS:if token in ayc then call T;call P;else error;ffl&T:if token in a.c then call Q;call R;else error;MP：If token = 8then match(a); call S;else if token in b# the n return;标准文档函数Q：if token = 8then match(a); call S; match(b);else if token = V then matchc);else erro

24、r;函數R：if token In afcthen call T;else if token in a,bR# then return;else error;4.11各个产生式的FIRST集、FOLLOW集和SELECT集浚吓:产生式FIRST 集FOLLOW 集select集S-AaB(aftg#a.f,gS-Bb:d,已 bd,eFbA-aDaaaA-Dtgf,gB今dMb,#JdB去eBEE际 JD今fDfafMgg根据各个产生式及其SELECT集可写出递归下降分析程序如下:标准文档王国数：scan：call s;rf token = then acceptelse error;购数S:

25、rf token in a, frgthen call A;matchf a); call B;else rf token fin d,巳 b then call B;match) b);else error;函数A：if token = *afthen match(a);call D;else rf token in fPg then call D;else error;标准文档的数B：if token 二 7Tthen match(d);else rf token 二 JeJthen match(e);else tf token in b,#then return;else error;函

26、数D:if token = Tthen match(f); call D;else if token -创then match(g);else error：4.12S-aAbA-aAb | eS-OA11AOAll | SaAbA-bAb | a实用文案标准文档实用文案5.1句子严i的分析过程为:步骤分析栈内容余留谕入串动作1#-i+i*i#移进2i+i*i#移进3#d+i*i#用Li归约4# F+i*i#用F-F归约5#F+i*i#用Tf F U醪6#T+i*i#用Ef T朋7#E+i*i#移进8#E+产i#移进9#E+I*i#用F-i归约10#E+F用TF归约11#E+T*itt移进12#

27、E+T*i#移进13#E+T*I#用F-i归约14#E+T*F用Tf T芥归约15#E+T用Ef “T归约16#E#接受5.2TFJ5语：F, Ft, FFtS 无 FFt*a* 直接短语：F, Ft , a 句柄：F最左素短语：F t5.3ETF 11TFFPfPpIII(1) 句子 i f (i+i)的短语为：il, D(R)1)R-R;P | Pd i, (i）P-S | 1b G(b )1D今iii（2）该文法的算符优先关系表为:ff()Ji(-5.5根据各个产生式，可以得到FIRSTVT集 LASTVT集如下表所示：电式FIRSTVT 集LASTVT 集s-bAbbbA-B 1 aI

28、 aa, (, 0-Aa)(, a)该文法的算符优先关系表为:b(aIb=(二)#=. SaP 1 P4 b, 5 d4 b, J dP- PbQ | Qb，s dc, d| d仙d d该文法的算符优先关系表为:abcd#abcd步骤符号栈输入串优先关系动作1dacbd#d移进2#tacbdff# a用Q今d归约3ffQacbd#na移进斗#03cbdtta c移进5畀Qacbd#a b用Q讥归约6ffQaQbd#a b移进7#QaQbd#b dP移进8ffQaQbd#bd 9菸119#QaQbQ#a #用PPbQ归约ID用SSaP归约11#5#接受5.7丰艮据旨个产主式,可以得到Fl RST

29、VT集和LAS1VT集如下表所示;产生式Fl RSTVT 集LASTVT 集5 1 (T)4(他）T-SJ | Sa. (=J#由算符优先关系表可见，丈去中f壬诃一对终结符之间至务只满足一种关系, 所以该文法為算符优先文法。(2)句子(仙叭可的算符优先分析过程为:符号栈输入串优先关系动作1(fa； a), a#(移进2(3/ ab a#(移进3a#(a移进4#(a；a), a#(.用5-a朋5(S、a)7日胯c移进5ah atfr8移进7ab郦,)用 Sa Jl3g5砒()用T*T归约3(Tb确(=)移进10#(mj a)#(,用(T)归约11#(S,a)#(，移进12#(S,a#,a移进13

30、#(S, a怜r)用宀I哟14#(S, 5(|用TSJ归约15#(T(=)移进16#(T)#fr用5今归约17ffS接受句子阿亦可的规范归约过程为:步骤分析栈内容余留输入符号串动作1#(a ? 3)，a)#移进2ff(归ah耶移进3#(4 ab a)#移进4、ab用5归约5*l(s7 ab训移进6帕a) a)#移进7#(S, a),a#用宀归约8#(S, sb砂用丁冬归约9帕T),a J#用WT归约10制Th a J#移迸11如用S-T）归约12#(S,at#移进13训移进14#(S aJ#用Sa归约15#( S艸用T*归约16#(S TJ#用T-SJ归约17#(T-移进18fl(T)用“归约

31、19#S接受5.8(1)vi, i： r的规范推导为(为了区分，特将I进行编号为k、h)：S =vl: T =v I: r =vlj b: r =v ii, b: rR)句子vi, i： r的崽语为：h, i八、vi1? i2： r句子vij i： r的句柄为:ii句子vl, I: r的素短语为；k、r(3)根据各个产生式，可以得到FIRSTS集和LASTVT集如下表所示:产生式FIRSTVT 集LASTVT 集VI: Ty：，b Cl-b i | ih iT-r | c. cfrj c该文5去的算符优先关系表为:Vrrc#VA =irc#二(4)句子心的算符优先分析过程为:步骤符号栈输入串优

32、先关系动作1vij 1： r# V移进2#vG i：井v i移进3Wi,i： 甲v f用1今i归约4#vl,1: r#移进5#vbi： r#,=i移进6#vl, i:Zv:用19归约7#vli r#V -:移进3#vl :#:用“ r归约10#vh T用Wvl: T归约11#s接受5.9(1)根据各个产生式,可叹得到FIR5TVT集#口 LA5TVT集如下表所示:产生式FIRSTVT 集LASJVT 集5今CAic仙bA- a Ab | c(flj c4 C(2)该文法的算符优先关系表为:cabcab-(3)由算符优先关系表可见，文法中任何一对终结符之间至多只满定一 种关系，所以该文法为算符优

33、先文法。仪旺u静静UV ttH3VOmVCDVraq A u V mq1003q A q11 ru Veq II p站A o V册4t 霄 o年_g看qq*o|r#U0 um (Do心toit e Q 并nittcA5 A-d6 B-c01 B-d$-.Eb：A今匚上E-.aAA-xAbeMS-*EkAd.lliE-a.AbiE-*bB.A-.CAh：日去EA-.dh：EbJB-.dB今上Bn；B-d.B-.dha：A-cA.h；EaA 0-HBbLR(O!(分析表为:MSATORACTIONGOTO9cE4e0轨寂1Iacc25sSfi43知乌74r2r2r2r2r25$sS106r5r5r5r5r57r3r3r3t3S知务ii9r7r7r7r7r710r4r4r4r4r411r6rfirflf66acccd的井折过程；歩議n編入卑动隹下一吓状态10$12012S53Qa2cSccd#S540b2c55cd#S5$0)c5c5cS撫6(JiZc5c5e5d&*rsGOT0(5,A)=1O7Od2tSt5tSA10#GOT