南京邮电大学编译原理课后习题答案和讲解

《南京邮电大学编译原理课后习题答案和讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、Chomsky定义的四种形式语言文法中，0型文法又称为（）文法；A.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法2、文法：G：S→xSx

2、y所识别的语言是（）。A.{xyx}B.

3、（xyx）*

4、C.

5、x*yx*

6、D.{xnyxn

7、n≥0}3、算符优先分析每次归约的是（）A.最左直接短语B.直接短语C.最左素短语D.控制结点4、在下面的状态转换图中，可以区分的两个状态是（）。A.1和2B.3和4C.4和5D.5和65、对文法规则Z::=AB

8、AC

9、A用扩充的BNF可表示为Z::=A（B

10、C

11、ε）（或是Z::=A[B

12、C]）6、语法制导翻译是在文法规则中再配上（语义动作）

13、。7、将ifa-bthenc:=1elsed:=2翻译成后缀表达式并填入到POST数组中，假设数组元素下标从0开始。8、有文法G[Z]:Z::=ZaA

14、A

15、bA::=A+B

16、B

17、CB::=cZd

18、e，C::=ab

19、cC采用改写法消除该文法的左递归。解：采用改写法：Z::=AZ’

20、bZ’Z’::=aAZ’

21、εA::=BA’

22、CA’A’=+BA’

23、εB::=cZd

24、eC::=ab

25、cC已知文法G[S]:S->(AS)

26、(b)A->(SaA)

27、(a)试分析句型(A((SaA)(b)))的短语、简单短语、句柄、最左素短语画出正规式(b*abb*)*对应的DFA状态转换图，并化简试利用算符优先关系

28、，分析句子(a,(a,a))写出表达式(a+b)/(a-b)-(a+b*c)的三元序列及四元序列。解：（1）三元式：①（＋，a，b）②（－，a，b）③（/，①，②）④（*，b，c）⑤（＋，a，④）⑥（－，③，⑤）（2）四元式：①（＋，a，b，T1）②（－，a，b，T2）③（/，T1，T2，T3）④（*，b，c，T4）⑤（＋，a，T4，T5）⑥（－，T3，T5，T6）