编译原理-第1~5章习题课答案.ppt

《编译原理-第1~5章习题课答案.ppt》由会员分享，可在线阅读，更多相关《编译原理-第1~5章习题课答案.ppt（75页珍藏版）》请在三一办公上搜索。

1、chapter1,1、何谓源程序、目标程序、翻译程序、编译程序 和解释程序？它们之间可能有何种关系？,源程序：用源语言编写的程序。,目标程序：源程序经翻译程序过加工处理后生成的程序。,翻译程序：将源程序转换为与其逻辑上等价的目标程序。,编译程序：,源语言为高级语言，目标语言为汇编语言或机器语言的翻译程序。,解释程序：,源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。,先翻译后执行,边解释边执行,执行速度快,有利于程序的调试,多次运算,1次运算,2、一个典型的编译系统通常由有哪些部分组成？各部分的主要功能是什么？,chapter1,编译系统,编译程序,语法分析,语义分析与中间代

2、码生成,优化,目标代码生成,运行系统,词法分析,语法分析(Syntax Analysis)：,在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。,语义分析(Syntactic Analysis)：,语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集类型信息。,chapter1,词法分析(Lexical Analysis)：,从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）。,chapter1,代码优化(Optimization of code)：,为了使生成

3、的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。,代码生成(Generation of code)：,目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。,中间代码生成(Generation of intermediate code)：,完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记号系统。,chapter2,1.写出C语言和Java语言的输入字母表。,C语言：09数字，大小写英文字母，键盘上可

4、见的字符,Java语言：Unicode可以包括的所有字符。,6.文法G6为:N D|ND D 0|1|2|3|4|5|6|7|8|9（1）G6的语言是什么?,G6的语言是：09的数字组成的任意非空串,L(G6)=x|x0,1,2,3,4,5,6,7,8,9+,（2）给出句子0127、34和568的最左和最右推导。,7、写一文法，使其语言是奇数集。要求：不以0打头。,复杂的情况:分三部分,末尾：以1|3|5|7|9结尾,(一位):,D 1|3|5|7|9,开头：除了0的任意数字,中间部分：空或者任意数字串,D1|3|5|7|9,CCA|A0|B,所以题目要求的文法GN可以写成：,B2|4|6|8

5、|D,9、证明文法:S iSeS|iS|i 是二义的。,二义性的含义:,如果文法存在某个句子对应两棵以上不同的语法树，或者两种以上不同的最左/右推导，则称这个文法是二义的。,首先：找到此文法对应的一个句子 iiiei,其次：构造与之对应的两棵语法树,结论：因为该文法存在句子iiiei对应两棵 不同的语法树，因而该文法是二义的。,11、给出下面语言的相应文法,L1=anbnci|n1,i0,G1(S):SAB AaAb|ab BcB|,从n，i的不同取值来把L1分成两部分：,A aAb|ab,前半部分是 an bn：,后半部分是 c i：,B Bc|,所以整个文法G1S可以写为：,L2=aibn

6、cn|n1,i0,G2(S):SAB AaA|BbBc|bc,L3=anbnambm|m,n0,G3(S):SAB AaAb|BaBb|,L4=1n 0m 1m 0n|n,m0,可以看成是两部分：,剩下两边的部分就是：,S 1S0,中间部分是 0m 1m：,A 0A1|,所以G4S可以写为：,S 1S0|A A 0A1|,|A,chapter3,7.构造下列正规式相应的DFA。,步骤:,.根据正规式画出对应的状态转换图;,.根据状态转换图画出对应的状态转换矩阵;,.根据状态转换矩阵得到重命名后的状态转换矩阵;,.根据重命名后的状态转换矩阵得出最后的DFA.,问题：将状态转换图与DFA混淆。,1

7、(0|1)*101,.状态转换图,a,b,a,d,b,1(0|1)*101,a,1,(0|1)*,101,d,c,e,f,1,0,1,1,0,1,.状态转换矩阵,I,I0,I1,a,b,c,d,b,c,d,c,d,c,d,e,c,d,c,d,c,d,e,c,d,e,c,d,f,c,d,e,c,d,f,c,d,c,d,e,g,c,d,e,g,c,d,f,c,d,e,.重命名后的状态转换矩阵,S,0,1,A(始态),B,B,C,D,C,C,D,D,E,D,E,C,F(终态),F(终态),E,D,A,B,1,0,C,1,D,0,1,0,E,1,0,1,0,1,.DFA,1(1010*|1(010)*

8、1)*0,a,b,d,c,1,0,0,1,0,1,f,g,h,i,0,1,1,1,0,j,k,l,m,n,.状态转换图,.状态转换矩阵,.重命名后的状态转换矩阵,.DFA,8、给出下面正规表达式,（1）以01结尾的二进制数串。,(0|1)*01,（2）能被5整除的十进制数。,0|5,(0|5),|(1|2|3|4|5|6|7|8|9),(0|1|2|3|4|5|6|7|8|9)*,（4）英文字母组成的所有符号串，要求符号串中的 字母按字典序排列。,(A|a)*(B|b)*(C|c)*(Z|z)*,（3）包含奇數個1或奇數個0的二進制串,0*1(0|10*1)*|1*0(0|10*1)*,（5）

9、沒有重複出現的數字的數字符號串的全體,令ri=i|,i=0,1,2.9R0|R1|R2|.|R9記為Ri i(0,1,2.,9)P（0,1,2.,9)表示0,1,2.,9的全排列ri0ri1.ri9ri0ri1.ri9 P(0,1,2.,9),8、给出下面正规表达式,（6）最多有一個重複出現的數字的數字符號串的全體,i ri0ri1.ri9 i(0,1,2.,9)ri0ri1.ri9 P(0,1,2.,9),（7）不包含字串abb的由a和b組成的符號串的全體,b*(a*|(ba)*)*,9、对下面情况给出DFA及正规表达式：,（1）0,1上的含有子串010的所有串。,正规式：(0|1)*010

10、(0|1)*,DFA做法同第7题。,（2）0,1上不含子串010的所有串。,正规式：1*(0|11*1)*,1*0*1*,(0|11)*(0|1),1*(0|11)*1*,12、将图3.18的(a)和(b)分别确定化和最少化。,(a),.状态转换矩阵,0,0,1,1,1,0,1,0,1,1,0,.重命名后的状态转换矩阵,0,1,2,2,1,1,2,0,a,2,b,a,b,a,.DFA,.最小化,0=(0,1,2),0,1a=1,0,1b=2,因此，不能再分,2,b,a,a,(b),这道题实质上已经是确定化了的，所以我们只需最小化,：2，3，4，5 0，1,2，3，4，5a=0，1，3，5,分属

11、两区，所以分为2，4 3，5,0，1a=1 0，1b=2，4,所以 0，1等价,2，4a=0，1 2，4b=3，5,所以2，4等价,3，5a=3，5 3，5b=2，4,所以3，5等价,所以分为 0，1 2，4 3，5,14、构造一个DFA，它接受=0,1上所有满足如下 条件的字符串：每个1都有0直接跟在右边。,思路：先写出满足条件的正规式，由正规式构造 NFA，再把NFA确定化和最小化。,满足条件的正规式：(0|10)*,确定化：,给状态编号：,最小化：0,1，20,10=1 0,11=220=0，21=2或0,1所以0,1不可分，用狀態0代表它們,15、给定右线性文法G：求一个与G等价的左线

12、性文法。,S 0S|1S|1A|0BA 1C|1B 0C|0C 0C|1C|0|1,GZ:Z Z0|Z1|B0|A1B A0|0A B1|1,确定化、最小化后的DFA为：,补充：构造一右线性文法，使它与如下文法等价：SAB AUT Ua|aU Tb|bT Bc|cB 并根据所得右线性文法，构造出相应的状态转换图。,思路：先写出原文法所描述的语言 L(G)=ambnck|m,n,k1,GS:S aS|aB B bB|bC C cC|c,chapter4,4.1、考虑下面文法G1：S a|（T）T T，S|S（1）消去G1的左递归；,S a|（T）,T ST,T，S T|,（2）经改写后的文法是否

13、是LL(1)文法，给出预测分析表。,经改写后的文法满足3个条件，所以是LL(1)的,预测分析表构造算法:,1.对文法中的每个产生式A 执行第二步和第三步;,FIRST(S)=a,(FIRST(T)=a,(FIRST(T)=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW(T)=),S a,S,S(T),T ST,T ST,T ST,T,ST,T,预测分析表构造算法:,1.对文法中的每个产生式A 执行第二步和第三步;,2.对每个终结符a FIRST(),把A a加到MA,a中;,S a;S;S(T);T ST;T,ST T,S a,S,S(T),T ST,T ST,T ST,T,S

14、T,3.若 FIRST(),则对于任何b FOLLOW(A)把A 加至MA,b中,FOLLOW(T)=FOLLOW(T)=),T,递归子程序：procedure S;beginif sym=a or sym=then abvance else if sym=(then beginadvance;T;if sym=)then advance;else error;endelse errorend;,procedure T;beginS;TEndprocedure T;beginif sym=,then bengin advance;S;T endEnd,sym:是输入串指针IP所指的符号 adv

15、ance:是把IP调至下一个输入符号error:是出错诊察程序,补充题：有文法：E TE E ATE|T FT T MFT|F（E）|i A+|-M*|/（1）求First、Follow集，判断是否是LL（1）文法？（2）若是构造LL（1）分析表？（3）简述LL（1）分析器的工作原理。,4.2：有文法：E TE E+E|T FT T T|F PF F*F|P(E)|a|b|（1）求First、Follow集，判断是否是LL（1）文法？（2）若是构造LL（1）分析表？（3）简述LL（1）分析器的工作原理。,E TEE ATE|T FTT MFT|F（E）|iA+|-M*|/,FIRST(M)=*

16、，/,FIRST(A)=+，-,FIRST(F)=(，i,FIRST(T)=*，/，,FIRST(T)=(，i),FIRST(E)=+，-，,FIRST(E)=(，i,FOLLOW(E)=#，),FOLLOW(E)=#，),FOLLOW(T)=,+，-，#，),FOLLOW(T)=,+，-，#，),FOLLOW(F)=*，/，+，-，#，),FOLLOW(A)=,(，i,FOLLOW(M)=(，i,P81.2.对文法G:E TE E+E|T FT T T|F PF F*F|P(E)|a|b|,1)FIRST(E)=,FIRST(T),=FIRST(F),=FIRST(P),=(,a,b,FIR

17、ST(E),=+,FIRST(T),=FIRST(T),=(,a,b,FIRST(F),=*,FOLLOW(E),=#,),FOLLOW(E),=FOLLOW(E)=#,),FOLLOW(T),=FIRST(E)FOLLOW(E),=+,#,),FOLLOW(T),=FOLLOW(T)=+,#,),FOLLOW(F),=FIRST(T)FOLLOW(T),=(,a,b,+,#,),FOLLOWF),=FOLLOW(F),=(,a,b,+,#,),FOLLOW(P),=FIRST(F)FOLLOW(F),=*,(,a,b,+,#,),2)考虑下列产生式:FIRST(+E)FIRST()=+=FI

18、RST(+E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T)=(,a,b,+,),#=FIRST(*F)FIRST()=*=FIRST(*F)FOLLOW(F)=*(,a,b,+,),#=FIRST(E)FIRST(a)FIRST(b)FIRST()=所以,该文法式LL(1)文法.,3)預測分析表：,4)程序procedure E;beginif sym=(or sym=a or sym=b or sym=then begin T;E end else errorendprocedure E;beginif sym=+then b

19、egin advance;E end else if sym)and sym#then errorendprocedure T;beginif sym=(or sym=a or sym=b or sym=then begin F;T end else errorend,procedure T;beginif sym=(or sym=a or sym=b or sym=then T else if sym=*then errorendprocedure F;beginif sym=(or sym=a or sym=b or sym=then begin P;F end else errorend

20、procedure F;beginif sym=*then begin advance;F endend,procedure P;beginif sym=a or sym=b or sym=then advance else if sym=(thenbeginadvance;E;if sym=)then advance else errorendelse errorend;,4.3下面文法中，那些是LL(1)文法的，說明理由构造不带回溯的自上而下分析的文法条件 1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A 1|2|n 则 FIRST(i)FIR

21、ST(j)(ij)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(A)FOLLOW(A)=如果一个文法G满足以上条件，则称该文法G为LL(1)文法。,SAbcAa|Bb|是，满足三个条件,SAbAa|B|Bb|对于A不满足条件3,SABBAAa|Bb|A、B都不满足条件3,SaSe|BBbBe|CcCe|d满足条件3,解題思路：構造文法的預測分析表，通常應當按下列步驟進行：1.消除文法的左遞歸（包括所有直接左遞歸和間接左遞歸）2.對消除左遞歸后的文法，提取公因子 3.對經過上述改造后的文法，計算它的每個非終結符的FIRST集合和FOLLOW集合；4.根據FIRST集合和

22、FOLLOW集合構造預測分析表：第1步對文法G的每個產生式A執行第1步和第3步；第2步對每個終結符aFIRST(),把A加至MA,a中；第3步若 FIRST(),則對任何b FIRST(A),把A加至MA,b中；第4步把所有無定義的MA,a標上“出錯標誌”,4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr|Varid VarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id-id(id)分析過程,4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Ex

23、pr|Varid VarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id-id(id)分析過程,4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr|Varid VarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id-id(id)分析過程,(2)給出對句子id-id(id)分析過程,(2)給出對句子id-id(id)分析過程,(2)給出對句子id-id(id)分析過程,(2)給出對句子id-id(id)分析過程,chapter5,1、令文法G1为：EE+T|T TT*F

24、|F F(E)|i 证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。,T*F是句型E+T*F相对于T的短语,E+T*F句型E+T*F相对于E的短语,T*F是句型E+T*F相对于T的直接短语,T*F是句柄,2、考虑下面的表格结构文法G2：Sa|(T)T T,S|S,（1）给出(a,(a,a)和(a,a),(a),a)的最左和最右推导。,(a,(a,a)的最左推导：S(T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a,S)(a,(a,a),(a,a),(a),a)的最左推导：S(T)(T,S)(S,S)(T),S)(T,S),S)(T,

25、S,S),S)(S,S,S),S)(T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),S,S),S)(a,a),S),S)(a,a),a),S)(a,a),a),a),(a,a),(a),a)的最右推导：S(T)(T,S)(S,S)(S,a)(T),a)(T,S,S),S)(S,S,S),S)(T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),S,S),S)(a,a),S),S)(a,a),a),S)(a,a),a),a),(a,(a,a)的最右推导：S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,

26、(S,a)(T,(a,a)(S,(a,a)(a,(a,a),2）指出(a,a),(a),a)的规范归约及每一步的句柄。,S,(,T,),T,S,a,(,T,),S,T,S,T,S,(,T,),S,a,(,T,),S,T,S,a,S,a,a,Sa,(S,a),(a),a),S,TS,(T,a),(a),a),a,Sa,(T,S),(a),a),T,S,TT,S,(T),(a),a),(T),S(T),(S,(a),a),S,TS,(T,(a),a),S,(T,S,(a),a),T,S,TT,S,根据这个规范规约，给出“移进归约”的过程，并给出它的语法树的自下而上的构造过程。,符号栈,输入串：(a

27、,a),(a),a)#,S,(,T,),T,S,a,(,T,),S,T,S,T,S,(,T,),S,a,(,T,),S,T,S,a,S,a,(,(,(,a,S,T,a,S,S,),T,S,T,(,a,S,T,),S,),S,T,a,S,T,),S,3、(1)计算练习2文法G2的FIRSTVT和LASTVT。G2：Sa|(T)T T,S|S,FIRSTVT(S)=a，(,FIRSTVT(T)=，a，(,LASTVT(S)=a，),LASTVT(T)=，a，),T T，S,T T，S,S（T）,S（T）,对待特殊地#,把它看作句型的开始和结束符.根据#S#同理可得,1、文法是算术文法，且不含产生式

28、。2、由优先关系矩阵可知，任何两个终结符之间的优先关系不多于一种。综上，该文法是算术优先文法。,输入串(a,(a,a)的算符优先过程。,(,a,(,a,a,),),#,a,S,#(S,(a,a)#,a,S,#(S,(S,a)#,a,S,#(S,(S,S)#,S,S,T,#(S,(T)#,(T),S,#(S,S)#,S,S,T,#(T)#,(T),S,#S#,确认！,问题：没有依据最左素短语进行规约,P134-5考虑文法SAS|b ASA|a1、列出这个文法的所有LR(0)项目2、构造这个文法的LR(0)项目集规范族及识别或前缀的DFA3、这个文法是SLR的吗？若是，构造出它的SLR分析表4、这

29、个文法是LALR或LR(1)的吗,解答：1、,P134-5考虑文法SAS|b ASA|a1、列出这个文法的所有LR(0)项目2、构造这个文法的LR(0)项目集规范族及识别或前缀的DFA3、这个文法是SLR的吗？若是，构造出它的SLR分析表4、这个文法是LALR或LR(1)的吗,解答：1、,确定化：,P135-6,P135-7证明下面文法是SLR(1)文法，但不是LR(0)文法SA AAb|bBa BaAc|a|aAb解：文法GS：0：SA 1：AAb 2：AbBa 3：BaAc 4：Ba 5：BaAb,p135-8.证明下面的文法是LL(1)的,但不是SLR(1)的。SAaAb|BbBa A

30、B解答:(1)首先该文法无左递归存在,没有公共左因子。其次:对于SAaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=b FIRST(AaAb)FIRST(BbBa)=所以该文法是LL(1)文法。(2)证明该文法不是SLR的。文法的LR(0)项目集规范族为:I0=S.S S.AaAb S.BbBa A.B.I1=S S.I2=SA.aAb I3=SB.bBa I4=SAa.Ab A.I5=SBb.Ba B.I6=SAaA.b I7=SBbB.a I8=SAaAb.I9=SBbBa.考察I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A)FOLLOW(B)=a,b产生规约-规约冲突。所以该文法不是SLR(1)文法。,P135-9,