编译原理习题汇总

1、第1、2章一填空1 .假设源程序是用高级语言编写的，目标程序是 语言的程序，那么相应的翻译程序称为编译程序。2 .(华中科大)翻译程序是如此一种程序，它能够将 转换成与其等价的3 .对编译程序而言，输入数据是 ,输出结果是 。4 .(华东计算所)汇编程序是将 翻译成;编译程序是将 翻译成a 汇编语言程序b机械语言程序c 高级语言程序d a或be a或cf b 或c5 .(国防科大)编译进程中，语法分析器的任务是 (1)分析单词是如何组成的(2)分析单词串是如何组成语句和说明的的(3)分析语句和说明是如何组成程序的(4)分析程序的结构A (2)(3)B(2)(3) (4) C (1)(2)(3)

2、 D(1)(2)(3)(4)6 .(国防科大)文法 G产生的 的全部是该文法描述的语言。7 .(中国科大)乔姆斯基概念的4种形式语言文法别离为 文法(又称文法)、文法(又称 文法)、文法(又称 文法)、文法(又称 文法)。8 .上下文无关文法比正规文法具有更强的描述能力。判定正误？9 .程序语言 由和概念。10 .文法G所产生的句子的全部是()，记为()。11 . 一个上下文无关文法包括的4个组成部份是0第4章1. 大体思想：从识别符号动身，不断成立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树的角度讲，自上而下分析进程是以开始符号为根节点，试图向下构造一颗语

3、法树，使其结尾节点符号串正好与输入符号串相同。2. LL (1)文法 P73(1)文法不含左递归；(2)文法中每一个非终结符A的各个产生式的候选首符集两两不相交即：假设 A a 1| a 2| , | an则 first( a i) A first( a j)=(i w j )(3)对文法中每一个非终结符A,假设它存在某个候选首符集包括？，那么first(A) nfollow(A)= 重点：左递归的排除计算FIRST和FOLLOW1合3. LL (1)预测分析表的构造1 .自上而下分析会碰到的要紧问题有一一左递归一一和一一回溯一一。2 .语法分析经常使用的方式是自上而下_和_自下而上_第5章自

4、下而上分析1 .大体思想：从待输入的符号串开始，利用文法的规那么步步向上规约，试图规约到文法的开始符号。从语法树的角度看，自下而上分析的进程是以输入符号串作为结尾节点符号串，向着根节点的方向往上构造语法树，使识别符号正好是该语法树的根节点。若是最终根节点是识别符号，那么输入符号串被识别出是相应语言的一个句子；不然不是。2 .自下而上分析进程：边输入单词符号，边归约。核心问题：识别可归约串 “算符优先分析”中：“最左素短语”一一“可归约串”“标准归约分析”中：“句柄”一一“可归约串”3。算符优先分析不是一种标准归约法，是一种自下而上的语法分析法，关键在于规定算符(即终结符)之间的优先顺序和结合性

5、质，借助这种优先关系寻觅“可归约串”进行归约。特点：有利于表达式分析，宜于手工实现。4 .算符优先文法：若是一个算符文法 G中的任何终结符对(a,b)最多只知足下述三关系之一：a ? b , a? b , a? b那么称G是一个算符优先文法。5 . FIRSTVT 和 LASTVW合构造集合FIRSTVT(P):按概念，咱们用以下两条规那么构造集合FIRSTVT(P):(1)假设有产生式 P a或P Qa, 则aC FIRSTVT(P);(2)若 a C FIRSTVT(Q),且有产生式 P Q ，则 a C FIRSTVT(P)。构造集合LASTVT(P):按概念，咱们用以下两条规那么构造集

6、合LASTVT(P):(1)假设有产生式 P a或P aQ,则a C LASTVT(P);(2)若 aC LASTVT(Q),且有产生式 P -9,贝U aC LASTVT(P)。算符优先分析举例：i+i*i T i P90算符优先分析法每次都是对一一最左素短语一一进行规约LR ( K文法A都是无二义性的B都是二义性的 C 一部份是二义性的第5章附加1. 文法:E+T|TT- T*F|FF- (E)|i证明E+T*F是它的一个句型，并指出该句型所有短语、直接短语和句柄。解：E+T*F是它的一个句型，因为存在下面语法树:短语：T*F, E+T*F直接短语：T*F句柄：T*F2. 文法：S 一 a

7、 | 八 | (T)T一 T,S | S(1)给出(a,(a,a) 和(a,a)F,(a),a)的最左和最右推导;(2)指出(a,a)F,(a),a)的标准归约和每一步的句柄，依照那个标准归约，给出“移进-归约”进程，并给出它的语法树自下而上构造进程。解：(1)略(2)下1 ) ( a，a),A,(a),a)2 ) ( S,a),A,(a),a)3 ) (T , a ),A,(a),a)4 ) ( T,S ),A,(a),a)5 ) ( (T) /(a),a)6 ) ( S J,(a),a)7 ) ( T ,a ,(a),a)8 ) ( T ,S ,(a),a)9 ) (T,( a ),a)1

8、0 ) (T,( S ),a)11 ) (T, (T) ),a)12 ) ( T,S ),a)13 ) ( (T) ,a)14 ) ( S ,a)15 ) ( T ,a)_16 ) ( T ,S )17 ) (T)18 ) S标准句型及每一步的句柄(用划线标示)：“移进-规约”进程:步骤分析栈输入串动作(1)#(a,a)F,(a),a)#预备(2 )#(a,a),A,(a),a)#移进(3 )#(a,a),A,(a),a)#移进(4 )#(a,a),A,(a),a)#移进(5 )#(a,a),A,(a),a)#移进(6 )#(S,a),A,(a),a)#归约(7 )#(T,a),A,(a),a

9、)#归约(8 )#(T,a)F,(a),a)#移进(9 )#(T,a)F,(a),a)#移进(10)#(T,S)F,(a),a)#归约(11)#(T),A,(a),a)#归约(12)#(T),A,(a),a)#移进(13)#(S,A,(a),a)#归约(14)#(T,A,(a),a)#归约(15)#(T,A,(a),a)#移进(16)#(TF,(a),a)#移进(17)#(T)S,(a),a)#归约(18)#(T,(a),a)#归约(19)#(T,(a),a)#移进(20)#(T,(a),a)#移进(21)#(T,(a),a)#移进(22)#(T,(S),a)#归约(23)#(T,(T),a)

10、#归约(24)#(T,(T),a)#移进(25)#(T)S),a)#归约(26)#(T),a)#归约(27)#(T),a)#移进(28)#(S,a)#归约(29)#(T,a)#归约(30)#(T,a)#移进(31)#(T,a)#移进(32)#(T,S)#归约(33)#(T)#归约(34)#(T)#移进(35)#S#归约(36)#S#同意语法树的自下而上的构造进程:3. (1)计算练习2文法G2的FIRSTVT和LASTVT(2)计算G2的优先关系，G2是一个算符优先文法吗?(3)给出输入串(a,(a,a)的算符优先分析进程。解：(1)FIRSTVTLASTVTa,人,()a,人,)ST ,a,

11、人，,a,()人,)(2)优先关系表如下:aA(),#a>>>人>>>(<<<=<)>>>,<<<>>#<<<=因为：1)该文法不含 £产生式；2 )该文法是算符文法；3 )由优先关系表能够看出，任何终结符之间的优先关系最多知足一种优先关系;因此该文法是算符优先文法。(3)步骤分析栈输入串动作 缘故0#(a,(a,a)#预备1#(a,(a,a)#移进#<(2#(a,(a,a)#移进(<a3#(S,(a,a)#归约a>,4#(S,(a,a)#移

12、进(>,5#(S,(a,a)#移进,<(6#(S,(a,a)#移进(<a7#(S,(S,a)#归约a>,8#(S,(S,a)#移进(<,9#(S,(S,a)#移进,<a10#(S,(S,S)#归约,>)11#(S,(T)#归约,>)12#(S,(T)#移进(=)13#(S,S)#归约)>)14#(T)#归约，>)15#(T)#移进(=)16#S#归约)>#17#S#分析成功5.考虑文法：SfAS|bA一 SA|a(1)列出那个文法所有的LR(0)项目；(2)构造那个文法的 LR(0)项目集标准族和识别活前缀的DFA(3)那个文法

13、是SLR的吗？假设是，构造分析表；(4)那个文法是 LALR或LR(1)的吗？解：拓广文法如下：S' -SS-AS|bAfSA|a(1)所有LR(0)项目如下：1) S' -.S 2 ) S' 一 S. 3) S一.AS 4 ) S-A.S 5 ) S- AS. 6) Sf .b7 ) S-b. 8 ) A- .SA 9 ) A - S.A 10 ) A- SA. 11 ) A- .a 12 ) Z a.(2)该文法的LR(0)项目集标准族如下：I0: S '一- SI2=Go(I0,A):I5=Go(I1,A):I7=Go(I2,S):S 一 ASSf A ,

14、 SAf SA-S-AS-S 一 bSf - ASS A , SA-S AA一 SASf bSf ASA> S ' AA一 aAf SAS 一 - bA一 aI1=Go(I0,S):Z aI6=GoA1,S):SASf - ASS' 一S ,I3=Go(I0,b):A-AS>-AaS 一 - bAf S- AAf SAA一 SAA一 aA一 aSf - ASS 一 ASS 一 - bS 一 - bDFA 略。(3) FIRST (S) =b, a FIRST (A) =a, bFOLLOW(S) =#, a, b FOLLOW(A) =a, b在LR(0)项目集标准

15、族中，同时存在“移进 -归约”和“归约-归约”项目的项目集有I1 , I5和I7 ;其中I1中“归约”项目是“同意”项目，面临#时同意，移进项目要求面临a和b时移进，不存在冲突；I5中归约项目面临 FOLLOW(A2元素a,b时归约，“移进”项目面临a,b时移进，存在冲突；同理，I7也存在冲突。因此该文法不是SLR的。(或：构造出SLR分析表，指出存在多重入口)(4)构造LR(1)项目集标准族:I0:S' 一 S , #S一 AS, #/a/bS一 - b, #/a/bA一 SA, a/bA一 a, a/bI1=Go(I0,S):S' 一 S ,#A-S- A, a/bA=Go

16、(32Sa/bA- ASa, a#/a/bA- SAS, a/bS一 SAa/b/bA一 a, a/b阚 AS, a/bI2=Go(I0,A):S- A, S, #/a/bSf AS, #/a/bSf b, #/a/b Af SA, a/b Z - a, a/b I3=Go(I0,b):S - b , #/a/bI4=G(I0,a):A9=G o(J蝌：S- AS- , a/bZ S A, a/b2 - SA, a/bZ - a, a/b Sf AS, a/bI5=Go(I1,A):2 SA -，a/bSf A - S, a/bSf AS, a/bSf b, a/b2 - SA, a/b2 -

17、 a, a/bI10=Go(I5,A):Sf A- S, a/bSf - AS, a/bSf b, a/b2 - SA, a/b2 - a, a/bI6=Go(I1,S):Z S A , a/b2 - SA, a/bZ - a, a/bSf - AS, a/bSf b, a/bI7=Go(I1,b):S- b , , a/bI5S8,I9 b,附在“移进-j!药” b,姓因此该文法不是LR(1)的，更不是LALR的。:该文法是二义文法，故不是任何LR文法。)本章补充作业:1 .文法GS,构造LR(1)分析表:Sf aAd | bAc | aec | bedA-e解：(1)拓广文法如下：0) S

18、' 一 S1) S-aAd2) S-bAc3) S-aec4) S-bed5) ) A一 e(2) LR(1)项目集标准族构造如下:10: S ' 一 .S, #S 一 .aAd, #S 一 .bAc, #S 一 .aec, #S 一 .bed,#11: S '一 S., #12: S 一a.Ad, #S 一 a.ec, #A一 .e, d13: S fb.Ac, #S-b.ed, #A一 .e, c S 一 ae.c, #Z e., d16: S 一 bA.c, #17: S 一 be.d, #Z e., c18: S 一aAd., #ACTIONU0-S-f bAc

19、., #GOTOabcdI11: STbed,#且052S311Aft3SB43ST64强5相t5gS107r5Silailgi3LOLI工4(3) LR(1)分析表如下:I4: S 一aA.d, #I9: S 一aec., #2.文法 GS : S-ABA- aBa| eBfbAb| £(1)该文法是SLR的吗？(2)假设是，请构造它的分析表；(3)给出输入串baab#的分析进程。解：对文法拓广：(0)S ' 一 S(1)S 一 AB(2)A 一 aBa(3)A 一 £(4)B 一 bAb(5)B 一 £(1)构造LR(0)项目集标准族如下：10: S

20、' 一.SI3: A 一a.BaS 一 .ABAf .aBa A-.11: S '一 S.Bf .bAbBf.I4: S 一AB. B 一 b.Ab16: A faB.a17: B 一 bA.b18: A 一 aBa.19: B fbAb.I2: S 一A.B因为：FOLLOW(S)=# FOLLOW(A尸b,# Bf.bAbI0面临FOLLOW(A2元素时归约，面临B 一.冲突也能够用SLR方式解决，因此该文法是FOLLOW(B)=a,#a时移进，不存在冲突；同理，I2,I3,I5SLR 的。中的(2) SLR分析表如下:JicnonGOTOa.baSAB033工3121acc255r54 13r*.S5t5s4t1EKi3137Sss-7598t2,r2gr4(3)步骤 状态栈符号栈输入串00# baab#1 02 #A baab#2025#Abaab#30253#Abaab#402536#AbaBab#5025368#AbaBab#60257#AbAb#702579#AbAb#8024#AB#901#S#3 .假设有文法GS:Sf S;M|MMH MbD|DA D(S)| s(1)证明GS是SLR文法，并构造它的分析表;(2)给出GS的LR(1)项目