编译原理课后习题解答(2)

《编译原理课后习题解答(2)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、龙书本科教学版习题解答仅供教学参考编译原理课后习题解答第2章2.2节语法定义解：1）生成aa+a*的推导如下：SSS*SS+S*aS+S*aa+S*aa+a*2）语法分析树如图3）文法生成的语言是以a为基本运算分量的+和*运算表达式的后缀形式。证明：用对生成符号串中的运算符个数的归纳法证明①归纳基础：当运算符个数=0时，即Sa，a是表达式a的后缀形式②归纳步骤：假设运算符个数=k时，S能推导出α，α是含有k个运算符的表达式A的后缀形式；那么当符号串w中的运算符个数=k+1时，可能的最右推导有两种(1)SSS+Sa+...βa+(2)SSS*S

2、a*...βa*显然符号串β由一个S推导得到，β中的运算符个数为k个，根据假设，β是某个表达式B的后缀式；那么(1)βa+是表达式B+a的后缀式(2)βa*是表达式B*a的后缀式证毕。1／7西北大学GongXq龙书本科教学版习题解答仅供教学参考解答：nn1）L={01

3、n>=1}证明：①考虑，推导1步时，有S01推导2步时，S0S10011以此类推，推导n步时，S0S100S11...0...0S1...10...01...1可以得到n个0和n个1nn②对任意串01都存在一个推导S...0...01...12）文法生成以a为基本运算分量的+和-

4、运算的前缀表达式。证明略。3）文法生成具有对称括号对的串。证明略。4）文法生成a和b的个数相等的串。证明：用关于a和b个数的归纳法证明。①归纳基础：一步推导时，Sϵ，其中a和b的个数都为0。②归纳步骤：设S经过少于n步推导得到的串α中a和b的个数相等；则>=n步的推导形如SaSbS…x或SbSaS…yaSbS和bSaS中的S经过少于n步能推出终结符号串，且其中a和b的个数都相等；所以经过aSbS和bSaS推导出的x和y中的a和b个数也相等。证毕。5）文法生成基本运算分量为a的由二元运算+、连接和一元运算*构成的表达式，表达式可以加括号。证明略。2／7西

5、北大学GongXq龙书本科教学版习题解答仅供教学参考解答：文法3）、4）、5）有二义性。证明：3）对文法的句子()()，存在两棵不同的语法分析树如下：SSS(S)SS(S)SεεεεS(S)SS(S)Sεεεεεε所以文法是二义的。4）对文法的句子abab，存在两棵不同的语法分析树如下：SSaSbSaSbSεεaSbSbSaSεεεε所以文法是二义的。5）对文法的句子aaa，存在两棵不同的语法分析树如下：SSSSSSSSaaSSaaaa所以文法是二义的。3／7西北大学GongXq龙书本科教学版习题解答仅供教学参考解答：1）S→SS+

6、SS*

7、SS-

8、SS/

9、id

10、n

11、um2）list→list,id

12、id3）list→id,list

13、id4）E→E+T

14、E–T

15、TT→T*F

16、T/F

17、FF→id

18、num

19、(E)5）E→E+T

20、E–T

21、TT→T*F

22、T/F

23、FF→-E

24、+E

25、id

26、num

27、(E)1）证明：对语法分析树的结点数目使用数学归纳法。①归纳基础：当语法分析树有两个结点时，形如numnum111001生成的串分别为11和1001，表示的值为3和9，能被3整除。②归纳步骤：假设语法分析树的结点数目少于n时生成的二进制串的值能被3整除，那么当结点数目等于n时，语法分析树的根有下面两种可能的形式：4／7西北大学GongXq龙书本科教

28、学版习题解答仅供教学参考numnumnum10num1num2（1）对第一种情况，以num1为根的子树中结点数目少于n，生成的二进制串x的值能被3整除；那么num为根的语法分析树生成的二进制串为x0，值为x的值乘以2，能被3整除。（2）对第二种情况，以num1和num2为根的子树中结点数目都少于n，生成的二进制串x和y的值都能被3整除；

29、y

30、那么，以num为根的语法分析树生成的二进制串为xy，其值为xval*2+yval，也能被3整除。所以，文法生成的二进制串能被3整除。证毕。2）文法不能生成所有能被3整除的二进制串，例如串10101的值为21，能被3整除，但不能由

31、文法生成。产生式说明S→R

32、Q

33、P

34、NS是开始符号，生成5000以内的罗马数字B→I

35、II

36、III1~3E→IV

37、V

38、VB

39、IX4~9F→X

40、XX

41、XXX10,20,30G→XL

42、L

43、LF

44、XC30,40,50,60,70,80,90H→C

45、CC

46、CCC100,200,300J→CD

47、D

48、DH

49、CM400,500,600,700,800,900K→M

50、MM

51、MMM

52、MMMM1000,2000,3000,4000N→B

53、E一位数P→FN

54、GN

55、F

56、G两位数Q→HP

57、JP

58、HN

59、JN

60、H

61、J三位数R→KQ

62、KP

63、KN

64、K四位数5／7西北大学GongXq龙书本科教学版