北航计算机学院编译习题讲解.pdf

《北航计算机学院编译习题讲解.pdf》由会员分享，可在线阅读，更多相关《北航计算机学院编译习题讲解.pdf（46页珍藏版）》请在装配图网上搜索。

1、2008年6月27日1 北京航空航天大学计算机科学与工程系 1、复习 2、习题讲解 习题课 习题课 (1-3章） 章） 2008年6月27日2 北京航空航天大学计算机科学与工程系 第一章 第一章 概论 (介绍名词术语、了解编译系统的结构和编译过程） 2008年6月27日3 北京航空航天大学计算机科学与工程系 所谓编译过程是指将 高级语言程序 翻译为等价的 目标程 序 的过程。 1.2 编译过程 编译过程 词法分析 语法分析 语义分析、生成中间代码 代码优化 生成目标程序 习惯上是将编译过程划分为5个基本阶段： 2008年6月27日4 北京航空航天大学计算机科学与工程系 典型的编译程序具有 7个

2、逻辑部分 S.P O.P 语义分析、生成中间代码 生成目标程序 代码优化 语法分析程序 词法分析程序 出 错 处 理 符 号 表 管 理 2008年6月27日5 北京航空航天大学计算机科学与工程系 第二章 第二章 掌握符号串和符号串集合的运算、文法和 语言的定义 几个重要概念：递归、短语、简单短语和 句柄、语法树、文法的二义性、文法的实 用限制等。 掌握文法的表示：BNF、扩充的BNF范式、 语法图。 了解文法和语言的分类 2008年6月27日6 北京航空航天大学计算机科学与工程系 3.1 词法分析的功能 3.2 词法分析程序的设计与实现 状态图 3.3 词法分析程序的自动生成 有穷自动机、L

3、EX 第三章 第三章 :词法分析 词法分析 2008年6月27日7 北京航空航天大学计算机科学与工程系 补充 补充 正则文法 正则文法 NFA NFA 正则表达式 正则表达式 1 2 3 4 5 6 DFA DFA 最小化 2008年6月27日8 北京航空航天大学计算机科学与工程系 习题 习题 1 3章 章 2008年6月27日9 北京航空航天大学计算机科学与工程系 第一章 第一章 2典型的编译程序可划分为哪几个主要 的逻辑部分？各部分的主要功能是什么？ 2008年6月27日10 北京航空航天大学计算机科学与工程系 所谓编译过程是指将 高级语言程序 翻译为等价的 目标程 序 的过程。 1.2

4、编译过程 词法分析 语法分析 语义分析、生成中间代码 代码优化 生成目标程序 习惯上是将编译过程划分为5个基本阶段： 2008年6月27日11 北京航空航天大学计算机科学与工程系 典型的编译程序具有 7个逻辑部分 S.P O.P 语义分析、生成中间代码 生成目标程序 代码优化 语法分析程序 词法分析程序 出 错 处 理 符 号 表 管 理 2008年6月27日12 北京航空航天大学计算机科学与工程系 P19：4.试证明：A + =AA * =A * A 证： A * =A 0 A + ，A + =A 1 A 2 A n 得：A * =A 0 A 1 A 2 A n AA * =A（A 0 A

5、1 A 2 A n ） = AA 0 AA 1 AA 2 A A n =AA 2 A 3 A n +1 =A + 同理可得： A * A =(A 0 A 1 A 2 A n )A =A 0 AA 1 AA 2 A A n A = AA 2 A 3 A n+1 =A + 因此： A + =AA * =A * A 2008年6月27日13 北京航空航天大学计算机科学与工程系 P26:1.设G标识符的规则是 ： 标识符:=a|b|c| 标识符a|标识符c| 标识符0|标识符1 试写出V T 和V N ， 并对下列符号串a,ab0,a0c01,0a,11,aaa给出可能的一些推导。 解：V T =a,

6、b,c,0,1， V N =标识符 (1) 不能推导出ab0,11,0a (2)标识符=a (3)标识符=标识符1 =标识符01 =标识符c01 =标识符0c01 = a0c01 (4)标识符=标识符a =标识符aa =aaa 2008年6月27日14 北京航空航天大学计算机科学与工程系 P26： ： 2 写一文法，其语言是偶整数的集合 写一文法，其语言是偶整数的集合 常见错误： 1.终结符集中没有奇数。 2.如下定义： = ， = | 不能 =。 3.忽略负偶数。 2008年6月27日15 北京航空航天大学计算机科学与工程系 作法一： :=2 := := :=0|1|2|3|4|5|6|7|

7、8|9 作法二： z=偶整数 G(z)=0|2|2Z|2(Z+1)|2(Z-1) 或： G(Z)=0|2|Z+2|Z-2 2008年6月27日16 北京航空航天大学计算机科学与工程系 解： G： := | := + | | := | := | 1 | 3 | 5 | 7 | 9 :=0 | 2 | 4 | 6 | 8 3. 写一文法，使其语言是偶整数的集合，但不允许有以 0 开头的偶 整数。 2008年6月27日17 北京航空航天大学计算机科学与工程系 4.设文法 G的规则是： A :=b| cc 试证明： cc, bcc, bbcc, bbbcc LG 证：（ 1） A =cc （ 2） A

8、 =b A =bcc （ 3） A =b A =bb A =bbcc （ 4） A =b A =bb A =bbb A =bbbcc 又 cc, bcc, bbcc, bbbcc Vt* 由语言定义， cc, bcc, bbcc, bbbcc LG 2008年6月27日18 北京航空航天大学计算机科学与工程系 5 试对如下语言构造相应文法： （ 1） a(b n )a | n=0,1,2,3,其中左右圆括号为终结符。 （ 2） （ a n ）（ b n ） | n=1,2,3, 解：（ 1）文法 G S ： S:= a(B)a B:= bB | ( 2 ) 文法 G S ： -错了，两个 n不

9、等 S := (A)(B) A:= aA|a B:= bB|b S := (B) B:= aBb|a)(b 2008年6月27日19 北京航空航天大学计算机科学与工程系 7.对文法G 3 表达式 表达式:=项|表达式+项|表达式-项 项:=因子|项*因子|项/因子 因子:=（表达式）| i 列出句型表达式+项*因子的所有短语和简单短语。 = + = + * + * 短语有： 表达式+项*因子和项*因子 简单短语是：项*因子 2008年6月27日20 北京航空航天大学计算机科学与工程系 8 文法 V:= aaV | bc的语言是什么？ 解： L（ GV） = a 2n bc | n=0,1,2,

10、 V aaV aaaaV . a 2n bc (n 1) V bc (n=0) 2008年6月27日21 北京航空航天大学计算机科学与工程系 P33： 5.已知文法GE： E:=ET+ | T T:=TF* |F F:=FP |P P:=（E）| i 有句型TF*PP+， 问此句型的短语，简单短语，和句柄是什么？ 解：此句型的短语有：TF*PP+，TF*，PP，P 简单短语有：TF*，P 句柄是：TF* 常见错误： 1.认为下列是短语： TF*PP、 PP+、 + 2.认为 TF*PP+不是短语。 3.认为 PP是简单短语。 4.不能正确识别句柄 2008年6月27日22 北京航空航天大学计算

11、机科学与工程系 8.证明下面的文法G是二义的： S:= iSeS | iS | i 证：由文法可知iiiei是该文法的句子， 又由文法可知iiiei有两棵不同的语法树。 所以该文法是二义性文法。 2008年6月27日23 北京航空航天大学计算机科学与工程系 P39 3试构造一个从文法中删除 无用符号 的算法。 2008年6月27日24 北京航空航天大学计算机科学与工程系 多余规则 ：（ 1）在推导文法的所有句子中，始终用不到的 规则。即该规则的左部非终结符不出现在任何句型中。 -不可达 （ 2）在推导句子的过程中，一旦使用了该规则，将推 不出任何终结符号串。即该规则中含有推不出任何终结符号串

12、的非终结符。 -不活动 例如给定 GZ，若其中关于 U的规则 只 有如下一条： U:=xUy 该规则是多余规则。 若还有 U:=a，则此规则 并非多余 若某文法中无有害规则或多余规则，则称该文法是 压缩过的 。 2008年6月27日25 北京航空航天大学计算机科学与工程系 判断U是否为无用符号 条件 条件 检查文法中每一条规则左部的每个非终结 符U是否满足下述两个条件： 条件1：Z xUy, x,y V*,Z为识别符号 （即：要求 U必须出现在某个句型中） 条件 2： U t, t Vt * （即：能从 U推出终结符号串） * 2008年6月27日26 北京航空航天大学计算机科学与工程系 判断

13、条件 判断条件 2的算法 的算法 算法思路：对满足条件的符号作标记，最 后没有标记的符号为无用符号。 加标记的方法如下： 对于形如U:=u (u Vt *)的规则，左部U自然满足条件 2，因此对U标记。 当一规则U:=W的右部W中包含的非终结符全被加标 记时，即满足条件2时，左部U也满足条件2，对U加 标记。 2008年6月27日27 北京航空航天大学计算机科学与工程系 流程图 流程图 开始 对所有U:=W的左部加标记， If W中仅包含终结符和 已被加标记的非终结符 所有U Vn 已全部被标记 最近一次执行 框1未对任何 U Vn加标记 1 2 3 否 否 是 是 停机 2008年6月27日

14、28 北京航空航天大学计算机科学与工程系 举例 举例 例：对于文法 Z := Be A := Ae A := e B := Ce B :=Af C := Cf D := f * 第一遍 第二遍 * * * 第三遍 * 所以：B := Ce 和 C := Cf 是多余 也多余，未查出。不满足 条件1，不是条件2 2008年6月27日29 北京航空航天大学计算机科学与工程系 练习 练习 写一文法，使其语言是偶整数的集合，但 不允许有以0 开头的偶整数。 2008年6月27日30 北京航空航天大学计算机科学与工程系 第三章 词法分析 P67.1画出下述文法的状态图 Z:=Be B:=Af A:= e

15、 |Ae 使用该状态图检查下列句子是否是该文法的合法句子 f，eeff，eefe 解： S A e B Z e f e f，eeff不是该文法的合法句子，eefe是该文法的合法句子 2008年6月27日31 北京航空航天大学计算机科学与工程系 解：（1） ZA1|0 AA0|0 （2） V=A,Z,0,1 Vn=A,Z Vt=0,1 （3） L (GS)= 0或0 n 1,n1 L (GS)= 0|00 * 1 2、有下列状态图，其中S为初态，Z为终态。 （1） 写出相应的正则文法： （2） 写出该文法的V，V n 和V t ； （3） 该文法确定的语言是什么？ S 开始 A 0 0 Z0 1

16、 2008年6月27日32 北京航空航天大学计算机科学与工程系 5 令 A， B， C是任意正则表达式，证明 以下关系成立： A|A=A （ A*） *= A* A*= | AA* （ AB） *A = A（ BA） * （ A|B） * =（ A*B*） *=（ A*|B*） 2008年6月27日33 北京航空航天大学计算机科学与工程系 证明： A A x x L(A)或 x L(A) x x L(A) A （ A*） *（ A*） 0 （ A*） 1 （ A*） 2 （ A*） n (A 0 A 1 A2 An) (A1) A0 A 1 A2 An A* 2008年6月27日34 北京航空

17、航天大学计算机科学与工程系 AA*所表示的语言是 : LALA* LA0 LA（ LA0 LA1 LA2 ） LA0 LA1 LA2 LA* 故 AA* A* (LALB)*LA=( L(A)LB LALBLALB LALBLALBLALB ) LA =LA LALBLA LALBLALBLA LALBLALBL ALB LA = LA ( LBLA LBLALBLA ) = L(LBLA) (AB)*A=A(BA)* 2008年6月27日35 北京航空航天大学计算机科学与工程系 三个表达式所描述的语言都是 LALB中 任意组合 （ A|B） *=(A*B*)=(A*|B*)* 2008年6月

18、27日36 北京航空航天大学计算机科学与工程系 6、构造下列正则表达式相应的DFA （1）1（0|1）*|0 （2）1（1010*|1（010）*1）*0 2008年6月27日37 北京航空航天大学计算机科学与工程系 （1）与1（0|1）*|0对应的NFA为： 0,1 2008年6月27日38 北京航空航天大学计算机科学与工程系 8 把图3.24的（a）和（b）分别确定化 2008年6月27日39 北京航空航天大学计算机科学与工程系 10、构造一 、构造一 DFA， ， 它接受 它接受 =0,1上所有满足如下条 上所有满足如下条 件的字符串：每个 件的字符串：每个 1都有 都有 0直接跟在右边

19、。 直接跟在右边。 Z A 1 0 0 2008年6月27日40 北京航空航天大学计算机科学与工程系 第四章 语法分析 P80习题 a) 部分同学对不能正确的设计语法分析程序 （不会设计递归程序）。 b) 有些人在求first 集和follow 集时出错较多。 c) 在学习递归向下分析法时，不少人习惯于把文法最后归结 为一个很长的右部，例如：S := (cc)|dcce, 实际上写成如 S:= A|dAe ; A:= cA|c的形式更易于写出分析程序，也更合 理。 2008年6月27日41 北京航空航天大学计算机科学与工程系 P87习题 a) 对LL(1), SLR(1),算符优先文法的定义理

20、解不 清。很多同学做题的时候根本不考虑文法是否 满足这几种文法（LL(1), SLR(1),算符优先文法 ）的要求，以及是否需要改写文法，便开始做 题了。 b) 几种文法（如LL(1), SLR(1),算符优先）的判 断应该归纳一下，有些人在判断时条件不充分 就得出结果。 c) 对于构造LL(1)分析表的步骤很模糊，很多同 学写出来的分析表不够规范。 2008年6月27日42 北京航空航天大学计算机科学与工程系 P88页证明题，证明的人很少。证明思路 仍然有问题，建议此题讲解一下。 在涉及到有关是否为LL(1)文法的证明时 ，约1/4的同学不知道正确证明的方式。 2008年6月27日43 北京

21、航空航天大学计算机科学与工程系 P100、P108、P115习题 a) 短语、素短语概念不清。 b) 部分同学不会设计SLR(1)分析器。 c) 活前缀概念不清，很多同学不能正确求 出活前缀的有效项目集。 2008年6月27日44 北京航空航天大学计算机科学与工程系 第五章 第五章 2、试分别构造一个符号串翻译文法，它将由一般中 缀表达式文法所定义的中缀表达式翻译成波兰前 缀表达式和波兰后缀表达式。 解：构造的波兰前缀表达式为： E-+E+T T-F E-T F-ii T-*T*F F-(E) 构造的波兰后缀表达式为： E-E+T+ T-F E-T F-ii T-T*F* F-(E) 2008年6月27日45 北京航空航天大学计算机科学与工程系 3、构造一符号串翻译文法，它将接受由0 和1组成的任意输入符号串，并产生下面 的输出符号串： a)输入符号串倒置。 b)空符号串。 c)输入符号串本身。 d)符号串0 n 1 m 。 c) E-00E E-11E E- d) S-00S S-1S1 S- a) S-0S0 S-1S1 S- b)S-T T-1T|0T T-0|1| 2008年6月27日46 北京航空航天大学计算机科学与工程系 h P138习题 a) 第2题很多同学没做对。 p185习题 第六题：很多同学不清楚栈式符号表的由 那些部分组成。