编译原理(第2)陈意云+张昱编著课后答案

《编译原理(第2)陈意云+张昱编著课后答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理习题2003.41目录chap1基本知识chap3词法分析chap4语法分析chap5语法制导翻译chap6运行时刻环境chap7中间代码生成chap8代码生成2第一章练习1.1文法S(L)

2、aLL,S

3、S(a)指出文法的终结符号,非终结符号,开始符号.文法的四个组成部分:终结符号VT:语言不可再分的基本符号非终结符号VN:语法范畴(语法概念)开始符号S:最终感兴趣的语法范畴产生式P:定义语法范畴的一种书写形式终结符号:(,)a非终结符号:SL开始符号:S元语言符号:表示“定义为”

4、表示“或”3(b)给出

5、句子的分析树分析树:(推导树)表示一个句型的推导(a,(a,a))S(L)L,SS(L)aSa4(c)给出句子的最左推导给出每次推导后得到的句型的短语,直接短语最左推导:推导中任何一步都是对中的最左非终结lm符号进行替换的推导.短语是文法的句型(S*)S*A且A+则是关于A的句型的短语.直接短语是文法的句型(S*)S*A且A则是关于A的句型的直接短语.句柄:一个句型的最左直接短语称为句柄.5S(L)(L,S)(S,S)(a,S)

6、(a,(L))短语(L)L,SSaa(L,S)S,Sa,Sa,(L)(S,S)(a,S)(a,(L))(L)直接(L)L,SSaa短语(L)(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))短语aaaaa,(L,S)a,(S,S)a,(a,S)a,(a,a)(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))L,SSaa(L,S)S,Sa,Sa,a(S,S)(a,S)(a,a)直接aaaa短语L,SSaaa6(d)构造各个句子的最右推导.最右推导(规范推导)(e)这个

7、文法产生的语言是什么?a(a)(a,a)((a,a),a)......a和数据元素为a的广义表全体71.2考虑文法SaSbS

8、bSaS

9、(a)试说明此文法是二义性的.(定义1.5)如果一文法的句子存在两棵分析树,则该句子是二义性的.如果一文法包含二义性的句子,则这个文法是二义性的.可以从句子abab有两个不同的最左推导来说明.SaSbSabSabaSbSababSabablmlmlmlmlmSaSbSabSaSbSabaSbSababSabablmlmlmlmlm句子abab有两个不同的最左推导

10、,该句子是二义性的.所以此文法是二义性的.8(b)对于句子abab构造两个相应的最右推导.SaSbSaSbabSaSbabSabababrmrmrmrmrmSaSbSaSbaSbSaSbaSbaSbabababrmrmrmrmrm(c)对于句子abab构造两个相应的分析树.SSaSbSaSbSbSaSaSbS(d)此文法产生的语言是什么?由相同个数的a和b组成的字符串.91.3考虑文法bexprbexprorbterm

11、btermbtermbtermandbfactor

12、bfacto

13、rbfactornotbfactor

14、(bfactor)

15、true

16、false(a)请指出此文法的终结符号,非终结符号和开始符号.终结符号:or,and,not,(,),true,false非终结符号:bexpr,bterm,bfactor开始符号:bexpr10(b)试对于句子not(trueorfalse)构造一棵分析树.bexprbtermbfactornotbfactor(bexpr)bexprorbtermbtermbfactorbfactorfalsetrue11(c)试说明此文法产生的语言是全体布尔表达

17、式.12练习:长度为n的字符串,分别有多少个前缀,后缀,子串,真前缀,子序列?前缀:n+1后缀:n+1子串:1+n+(n-1)+...+1=1+n(n+1)/2真前缀:n子序列:1+Cn1+Cn2+Cn3+...+Cnn=2n13EE+TT*Fi给出句型E+T*i的短语,直接短语和句柄EE+TFT*F给出句型F+T*F的短语,直接短语和句柄短语:i,T*i,E+T*i直接短语:i句柄:i短语:F,T*F,F+T*F直接短语:F,T*F句柄:F14第三章练习3.3试描述下列正规表达式所表示的语言:(a)0(0

18、1)*0(

19、b)((

20、0)1*)*由0和1组成且以0开始和结束的符号串全体.(c)(0

21、1)*0(0

22、1)(0

23、1)由0和1组成的符号串全体.由0和1组成且以000,001,010或011结束的符号串全体.长度大于等于3且倒数第3个字符为0的01符号串全体.15(d)0*10*10*10*(e)(00

24、11)*((01

25、10)(00

26、11)