程序设计语言与编译教学指导.doc

程序设计语言与编译语言的设计和实现（第2版）教师用教学参考指南龚天富 编（本内容版权归作者所有，为非买品，只免费提供给教师教学之用，使用者不得随意翻印）本指南包括三个部分。第1部分给出本教材的知识点与教学重点；第2部分为必须布置的习题的参考答案。书中出现的程序不是教学重点，只需讲清思路即可。第3部分为参考试卷及其参考答案。第1部分 知识点与教学重点笔者将各章的知识点分为三级重点理解、理解和知道。对重点理解的知识点应讲深讲透，对知道的知识点可以不讲，或在其他课程（如高级程设计语言概论）中去讲，或由学生自学。第1章 绪 论重点理解 引言，强制式语言，程序单元。知道 程序设计语言发展简介（学生必须自学）。第2章 数据类型重点理解 引言，内部类型，用户定义类型，Pascal数据类型结构，C语言类型结构，SIMULA 67语言类机制，CLU语言的抽象数据类型，C+语言的抽象数据类型，类型检查，类型转换，类型等价。知道 Ada语言的抽象数据类型（自学），Modula-2语言的抽象数据类型（自学），实现模型（自学）。第3章 控制结构重点理解 引言，顺序结构，选择结构，重复结构，语句级控制结构分析，显式调用从属单元，异常处理（异常处理的5个问题），PL/1语言的异常处理机制，CLU语言的异常处理机制，Ada语言异常处理机制（主要讨论三种语言异常处理机制的异同），SIMULA 67语言协同程序，并发单元，信号灯，会合。知道 管程。第4章 程序语言的设计重点理解 全章。第5章 非过程式程序设计语言知道 全章（可以不要求，自学，作为高级程序设计语言概论课的内容）。第6章 形式语义学简介知道 全章（同第5章）。第7章 编译概述重点理解 全章。第8章 词法分析重点理解 全章。第9章 自上而下的语法分析重点理解 回溯分析法，预测分析法。理解 递归下降分析法。第10章 自下而上的语法分析重点理解 全章。第11章 语义分析和中间代码生成重点理解 全章。第12章 代码优化和目标代码生成重点理解 全章。第13章 运行时存储空间的组织重点理解 程序的存储空间，栈式分配。理解 静态分配。知道 符号表（自学）。附录A Java语言概述知道 整个附录A（自学）。第2部分 部分习题参考答案本书习题可分为思考题和必做题，这里仅给出必做题的参考答案。习题11-1至1-11均为思考题。习题22-1至2-14均为思考题。习题33-1至3-13均为思考题。习题44-1至4-4均为思考题。4-5 解：上下文有关文法（1型文法），产生的语言L（G）=aibici | i1,i为整数4-6 解：3型文法，L（G）=ai | i1,i为奇数4-7 解：2型文法，L（G）=aibi | i1,i为整数4-8 解：1型文法，L（G）=aibici | i1,i为整数4-9 解：1. 最左推导最右推导S (A) (B) (SdB)S (A) (B) (SdB) (A)dB) (B)dB) (SdS) (Sda) (S)dB) (b)dB) (A)da (B)da) (b)dS) (b)da) (s)da (b)da)2. 语法树4-10解：1. 因为存在推导S SbF SbP Sbc Fbc FaPbc所以FaPbc是文法G (S) 的一个句型。2. 语法树4-11解：因为串aaabaa可有下列两棵不同的语法树所以文法G (S)是二义文法。4-12解：因为串i (*可有下列两棵不同的语法树4-13解：假定所设计的语言面向的机器为一般通用机。按照题目给出的问题，如果不考虑输入和输出语句，那么所要设计的语言仅包含字符串数据类型和赋值语句。语言设计如下：begin；end|；string说明：string是变量的类型，表示变量为字符串。|一切可由键盘输入的字符|，；|：=|说明：符号“”为字符串连接运算符，例如字符串abc和字符串xyz经过连接运算的结果为abcxyz。|a|b|x|y|z0|1|2|3|4|5|6|7|8|9说明：本语言未设置任何控制语句，若要进行较为复杂的程序设计，必须增加控制语句，本语言的程序只能完全顺序执行。例：将字符串abc和xyz连接成字符串abcxyz。beginstring A1, A2, A3, A4；string B1, B2 B3, B4；A1:=a；A2:=b；A3:=c；B1:=x；B2:=g;B3:=z;A4:=A1A2；A4:=A4A3；B4:=B1B2；B4:=B4B3；B4:=A4B4end要求的结果字符串在B4中。习题55-1至5-19均为思考题。习题66-1至6-4均为思考题。习题77-1至7-5均为思考题。7-6解：设x, y, z对应的形式单元为J1（和J1），J2（和J2），J3（和J3）。1. 引用调用A:=2B:=3T:=A+B（T的值为5）J1:=T的地址J2:=A的地址J3:=A的地址J2:=J2+1（A的值为3）J3:=J3+J1（A的值为3+5=8）打印A的值为8。2. 传值A:=2B:=3T:=A+B（T的值为5）J1:=T（J1的值为5）J2:=A（J2的值为2）J3:=A（J3的值为2）J2:=J2+1（J2的值为3）J3:=J3+J1（J3的值为7）打印A的值为2。3. 结果调用形式单元J1, J2, J3无初始化值，计算是不确定的，打印A的值仍为2。4. 传值得结果A:=2B:=3T:=A+B（T的值为5）J1:=T（J1的值为5）J1:=T的地址J2:=A（J2的值为2）J2:=A的地址J3:=A（J3的值为2）J3:=A的地址J2:=J2+1（J2的值为3）J3:=J3+J1（J3的值为7）J3:=J1（T的值为5，未变）J2:=J2（A的值为3）J3:=J3（A的值为7）打印A的值为7。5. 名调用计算时用实参原文替换形参A:=2B:=3B:=A+1 （A替换y, A的值为3）A:=A+A+B（A的值为9）打印A的值为9。习题88-1为实验题。8-2为实验题。8-3为实验题。8-4为实验题。8-5为思考题。8-6为思考题。习题99-1为思考题。9-2解：（1）消除文法G的产生式直接左递归。ASeA | fA AdA | e （2）消除间接左递归：按S.A排序（按书上P116页的算法i=2,j=1时）将S的产生式代入有AAaeA | AbeA | ceA | fA （3）消除的直接左递归有AceAA | fAA AaeAA | beAA | e （4）对S的产生式提公因子有SAB | c B| a | b （5）最后，文法G提取公因子，消除左递归后的产生式由, , , 和组成，无多余的产生式。（6）若按A.S排序，得到的产生式组合是另外的形式，但它们是等价的文法，读者可以试试。9-3解：消除左递归后，得文法G:S(L) | aLSLL, SL | e递归下降过程： Procedure match(t:token); begin if lookahead=t then lookahead=nexttoken else error end procedure S; begin if lookahead=a then match(a) else if lookahead=( then begin match(c); L; if lookahead=) then match() else error end end procudure L; begin S; L; end procudure L; begin if lookahead=, then begin match(,) S; L end end9-4解：这里只给出消除直接右递归的一般形式。G：有产生式Aa1A | a 2A | | a nA | b消除直接右递归时得产生式AAbAAa1 | Aa2 | | Aan | e9-5为思考题。9-6解：（1）G（S）：SAS SiAS | e ABA A+BAe AbS* | a （2）FIRST集和FOLLOW集FIRSTFOLLOWSb，a#，*Si，e#，*Ab，a#，*，iA+，e#，*，iBb，a#，*，i，+预测分析表ai+b*#SSASSASSSiASSeSeAABAABAAAeA+BAAeAeBBaBbS*（3）因为预测分析表无多重定义入口，所以G是LL（1）文法。9-7解：对习题9-3的文法G消除左递归后，得文法G： S(L) | a LSL L,SL | e FIRST集和FOLLOW集FIRSTFOLLOWS(，a)，#L(，a)L，e)预测分析表（）a,#SS(L)SaLLSLLSLLL)L,SL因为预测分析表无多重定义入口，所以文法G是LL（1）文法。习题1010-1解：（1）规范规范推导（最右推导）最右推导SABASbAABbbBABb（2）语法树（推导树）（3）短语 bB, AB, Abb, bBABb 直接短语 bB, AB 句柄 bB 最左素短语 bB10-2解：（1）因为存在推导SSbFFbFFaPbFFaPbPFaPbc所以FaPbc是文法G的一个句型。（2）语法树（3）短语 FaP, c, FaPbc 直接短语 FaP, c 句柄 FaP 最左素短语 FaPbc10-3解：拓广文法0.SS1.SAS2.Sb3.ASA4.AaLR（0）项目集规范族I0=closureSS I1=GO(I0,S) I2=GO(I0,A) I3=GO(I0,b)I0:SS SS SAS SbSAS ASA SAS GO(I1,a)=I4Sb ASA Sb GO(I2,A)=I2ASA Aa ASA GO(I2,b)=I3Aa SAS Aa SbI4=GO(I0,a) I5=GO(I1,A) I6=GO(I1,S) I7=GO(I2,S)Aa ASA ASA SAS SAS ASA ASA SAS Ab ASA Sb SAS Aa ASA Sb SAS Aa Sb GO(I1,b)=I3 GO(I2,a)=I4FOLLOW(S)=a, b, #FOLLOW(A)=a, b 状态5在输入a时有S4和r3的移进归约矛盾。 状态5在输入b时有S3和r3的移进归约矛盾。 状态7在输入a时有S4和r1的移进归约矛盾。 状态7在输入b时有S3和r1的移进归约矛盾。 文法G既不是LR（0）文法，也不是SLR（1）文法。10-4解：（1）最左推导 S(T)(T,S)(S,S)(a,S)(a,(T) (a,T,S)(a,(S,S)=(a,(a,S)(a,(a,a) 最右推导 S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a) (T,(S,a)(T,(a,a)(S,(a,a)(a,(a,a) 最左推导 S(T)(T,S)(S,S)(T),S)(S),S)(T,S),S) (T,S,S),S)(S,S,S),S)(T),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),(T),S) (a,a),(S),S)(a,a),(a),S) =(a,a),(a),S)(a,a),(a),a)最右推导S(T)(T,S)(T,a) (S,a)(T),a)(T,S),a) (T,(T),a)(T,(S),a)(T,(a),a)(T,S,(a),a) (T,(a),a)(S,(a),a)(T),(a),a) (T,S),(a),a)(T,a),(a),a)(S,a),(a),a) (a,a),(a),a)（2）对句子(a,(a,a)的移进归约栈的变迁如下：其中，（3），（4），（8），（9），（12），（13），（15），（16），（18）共进行9次归约，最右推导也是9次推导，正好是递过程。归约（3）的句柄是a，语法树如图（1）所示。归约（4）的句柄是S，语法树如图（2）所示。归约（8）的句柄是a，语法树如图（3）所示。归约（9）的句柄是S，语法树如图（4）所示。归约（12）的句柄是S，语法树如图（5）所示。归约（13）的句柄是T,S，语法树如图（6）所示。归约（15）的柄是(T)，语法树如图（7）所示。归约（16）的句柄是T,S，语法树如图（8）所示。归约（18）的句柄是(T)，语法树如图（9）所示。图（9）即是完整的语法树。图中的下标是为了区分归约过程中同名文法符号和便于理解而添加的，实际是没有的，对句子(a,a),(a),a)的规约栈变迁如图(10)所示。图(10)规范推导（最右推导）一共进行17步推导，归约过程也进行了17次归约，语法树如图(11)所示，其中的下标可表明其形成的先后。图(11)10-5解：算符优先关系表构造如下：该文法的产生式没有两个非终结符相邻，没有e产生式，它是算符文法，在其算符优先关系表中，任何两个终结符之间至多只存在一种优先关系，故它是算符优先文法。10-6解：FIRSTVT(B)=,乛,(,iLASTVT(B)=,乛,),i在规则BBB中，FIRSTVT(B),又在规则BBB中，LASTVT(B),因此，在与之间存在两种优先关系，故G不是算符优先文法。若令，为右结合，则有，优先级由低到高为乛, , ，则有乛, 乛, ，构造优先关系表如下：10-7解：0.SSFOLLOW(S)=$1.SABFOLLOW(A)=b,c2.BcBdFOLLOW(B)=d,$3.Bcd4.AaAb5.AabI0=closureSSI0:SSI4=GO(I2,B)I9=GO(I5,d) SAB SAB Bcd AaAbI5=GO(I2,c)I10=GO(I6,b) Aab BcBd AaAbI1=GO(I0,S) BcBdI11=GO(I8,d) SS BcBd BcBdI2=GO(I0,A) Bcd SABI6=GO(I3,A) BcBd AaAb Bcd GO(I3,a)=I3I3=GO(I0,a)I7=GO(I3,b) AaAb Aab AabI8=GO(I5,B) AaAb BcBd Aab GO(I5,c)=I5上述状态集没有移进归约冲突，（a）是SLR文法，分析表如下：abcd$SAB0S3121acc2S543S3S764r15S5S986S107r5r58S119r3r310r4r411r2r210-8解： 拓广文法 0.SSFOLLOW(S)=a,b,$I1=GO(I0,S) 1.SbAFOLLOW(A)=a,b,$ SS 2.SaBFOLLOW(B)=a,b,$I2=GO(I0,b) 3.ASaI0=closureSS SbA 4.AaI0:SS ASa 5.BSb SbA Aa 6.Bb SaB SbA SaBI3=GO(I0,a)I5=GO(I2,S)I7=GO(I3,B)I10=GO(I5,a) SaB ASa SaB ASa BSbI6=GO(I2,a)I8=GO(I3,S) GO(I6,B)=I7 Bb Aa BSb GO(I6,S)=I8 SbA SaBI9=GO(I3,b) GO(I6,b)=I9 SaB BSb Bb GO(I6,a)=I3I4=GO(I2,A) Bb SbAI11=GO(I8,b) SbA SbA ASa BSb SaB Aa GO(I9,A)=I4 GO(I2,b)=I2 SbA GO(I9,B)=I5 SaB GO(I9,a)=I6 GO(I3,a)=I3 GO(I9,b)=I2因为在I6和I9中，有依靠FOLLOW集无法解决的移进归约矛盾（对输入字符a），所以G不是SLR文法。10-9，同习题10-3。10-10解：（1）FIRSTVT(P)=A,(LASTVT(P)=a,) FIRSTVT(F)=aLASTVT(F)=a（2）优先关系表：习题1111-1解：11-2解：首先给出语法树，对语法树的句柄剪枝进行归约。考虑简单的表达式文法：EE+E | E-E | E*E | -E | (E) | i（1）EiEVAL=a设四元式的初始编号ip=100（2）EiEVAL=b（3）EE+EEVAL=T1(100)(+,a,b,T1)（4）E(E)EVAL=T1（5）E-EEVAL=T2(101)(,T1,-,T2) 为一元负（6）EiEVAL=c（7）EiEVAL=d（8）EE+EEVAL=T3(102)(+,c,d,T3)（9）E(E)EVAL=T3（10）EE*EEVAL=T4(103)(*,T2,T3,T4)（11）EiEVAL=a（12）EiEVAL=b（13）EiEVAL=c（14）EE+EEVAL=T5(104)(+,b,c,T5)（15）EE+EEVAL=T6(105)(+,a,T5,T6)（16）E(E)EVAL=T6（17）EE-EEVAL=T7(106)(-,T4,T6,T7)因为文法有二义性，可有不同的语法树，但对此题结果T7是一样的。11-3解： 推导树如下：（1）EiEVAL=B设四元式初始编号ip=100（2）EiEVAL= C（3）E-EEVAL=T1(101)(,c,-,T1)（4）EiEVAL=D（5）EE+EEVAL=T2(101)(+,T1,D,T2)（6）EE*EEVAL=T3(103)(*,B,T2,T3)（7）Si:=E(104)(:=,T3,-,A)11-4解：结果为333645211。11-5解：（1）E1CDE1F=101(100)(BE2F=103(102)(,A,B,104)（4）E1E*EE1VAL=T1(103)(j,-,-,0)（5）E2E+EE2VAL=T2(104)(*,2,z.T1)（6）Ai:=E2Achain=0(105)(+,y,T1,T2)（7）SAS1chain=0(106)(:=,T2,-,x)（8）SWS1S1chain=103(107)(j,-,-,102)（9）Sif E1 thenS1Schain=10111-6解：其中，1和N都是常量，其语义为i:=1;again:if iN then begin S1; i:=i+l; goto again end目标结构： (:=,1,-,i)again:(j,i,N,ip+2) (j,-,-,0)S的四元式 (+,i,1,i) (j,-,-,again)语义子程序：（1）F1for i:=1gen(:=,1,-i)（2）F2F1 to NF2again:=ip,q:=ip+2;gen(j,i,N,j); F2chain:=ip;gen(j,-,-,0)（3）SF2 do S1gen(+,i,1,i);gen(j,-,-,F2code);S1chain:=F2chain; gen(j,-,-,0);Schain:=F2chain11-8解：语句格式 repeat S until E语义： S1； if E then goto again;目标结构：语义子程序： RrepeatRagain:=ip SRS1 until ES1chain:=EPLACE(即ET),Schain:=ET; backpatch(EF,Ragain)11-9解：为了达到题目的要求，必须规定原文法的语义，即E2和E3不含变量，若含有变量，则这些变量的值在循环，体内不会改变，因此，其语义为 i:=E1; T1:=E2; T2:=E3;again:if iT2 then begin S1; i:=i+T1 goto again end语义子程序：F1for i:=E1gen(:=,E1PLACE,-,i); F1PLACE:=iF2F1 step E2T1:=E2PLACE,F2PLACE:=F1PLACEF3F2 until E3T2:=E3PLACE,q:=ip,gen(j,F2PLACE,T2,q+2); F3chain:=ip;gen(j,-,-,0),F3again:=qSF3 do S1gen(j,-,F3again,backpatch(S1chain,F3again); Schain:=F3chain习题12回边749110712-1解：（a）基本块程序流图B1 (1)(3)B2 (4)B3 (5)B4 (6)B5 (7)(8)B6 (9)B7 (10)(11)B8 (12)(13)B9 (14)(15)B10 (16)(17)（b）必经结点D(1)=1D(2)=1,2D(3)=1,3D(4)=1,3,4D(5)=1,3,4,5D(6)=1,3,4,6D(7)=1,3,4,7D(8)=1,3,4,7,8D(9)=1,3,4,7,8,9D(10)=1,3,4,7,8,10由回边74组成的循环7,4,5,6,8,10。（3）优化结果(3) B:=10(4) A:=A+8(5) if B100 then goto (8)(6) B:=B+10(7) goto (4)(8) write A12-2解：（1）基本块（2）程序流图 B1 (1)(3) B2 (4)(5) B3 (6)(7) B4 (8)12-312-4均为思考题12-5解：合并已知量，由（1）F:=1，可得最后化简为(2) C:=1+E (2) C:=1+E(3) D:=4 (4) B:=A*A(5) G:=B-4 (5) G:=B-4(8) J:=1 (7) I:=E*G(9) K:=1+C (9) K:=1+C(11) L:=I-1 (11) L:=I-1删除子表达式，从(6)将(7)改为(7)I:=E*G将(10)删除，F，D，J定值后不再发生变化，可删去。12-6解：12-7解：MOVbR0ADDR0cMOVaR1SVBR1R0MOVR0t1MOVdR0ADDR01MOVR1t2MOVeR1MVLR1fADDR0R1MOVt2R1DIVR1R012-8解：abcdefB1122211B212111B312212B422211B5111122698637分配给b, c, f，执行代价最省。习题1313-1为思考题。13-2解：当运行到C调用B时，活动记录栈的状态如下图。13-3为思考题。13-4解：静态作用域规则下输出 0.250 0.250 0.250 0.250动态作用域规则下输出 0.250 0.125 0.250 0.12513-5至13-7均为思考题。第3部分 参考试卷及其参考答案参考试卷一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在括号内。每小题1分，共10分）1. 词法分析器的输出是（ ）。 字符串 二元式 三元式 四元式2. 下述方法中，（ ）不是自下而上的分析方法。 规范归约 算符优先分析法 递归下降分析法 LR分析法3. =A, B, 0, 1上的正规式（A | B）（A | B | 0 | 1）*表示（ ）。 字符串 整数 数字串 标识符4. 句型是由（ ）推导出的符号串。 非终结符 终结符 任何符号 开始符号5. 项目Aaab称为（ ），其中aVT。 移进项 归约项 待约项 接受项6. LR分析法的核心部分是（ ）。 总控程序 分析表 分析栈 可归约串7. 把一个高级语言程序翻译成机器可执行的目标程序的工作由（ ）完成。 汇编器 解释器 编译器 预处理器8. 编译时能进行的类型检查称为（ ）。 错误检查 动态检查 静态检查 随机检查9. 若过程P调用过程Q，其参数传递方式是传名，同以（ ）来实现。 传地址 传值 调用过程P 参数子程序10. 在一棵语法树中，仅有两层的子树叶结点的自左至右排列称为（ ） 短语 直接短语 句柄 素