编译原理复习例题.doc

《编译原理复习例题.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。但要求至少要按照作业题的范围复习。)一选择题1．编译的各阶段工作都涉及。[A]词法分析[B]表格管理[C]语法分析[D]语义分析2．型文法也称为正规文法。　[A]0[B]1[C]2[D]33．文法不是LL(1)的。　[A]递归[B]右递归[C]2型[D]含有公共左因子的4．文法E→E+E

2、E*E

3、i的句子i*i+i*i有棵不同的语法树。　[A]1[B]3[C]5[D]75．文法S→aaS

4、abc定义的语言是

5、。[A]{a2kbc

6、k>0}[B]{akbc

7、k>0}[C]{a2k-1bc

8、k>0}[D]{akakbc

9、k>0}6．若B为非终结符，则A→a.Bb为。[A]移进项目[B]归约项目[C]接受项目[D]待约项目7．同心集合并可能会产生新的冲突。[A]二义[B]移进/移进[C]移进/归约[D]归约/归约8．代码优化时所依据的是。[A]语法规则[B]词法规则[C]等价变换规则[D]语义规则9．表达式a-(-b)*c的逆波兰表示（@为单目减）为。[A]a-b@c*[B]ab@c*-[C]ab@-[D

10、]ab@c-*10．过程的DISPLAY表是用于存取过程的。[A]非局部变量[B]嵌套层次[C]返回地址[D]入口地址-8-二填空题1．词法分析阶段的任务式从左到右扫描　字符流　，从而逐个识别一个个的单词　。2．对于文法G[E]：E→T

11、E+TT→F

12、T*FF→P^F

13、PP→(E)

14、i，句型T+T*F+i的句柄是　　。3．最右推导的逆过程称为规范归约，也称为最左归约。4．符号表的每一项是由名字栏和两个栏目组成。在目标代码生成阶段，符号表是的依据。三判断题（认为正确的填“T”，错的填“F”）【】1

15、．同心集的合并有可能产生“归约/归约”冲突。【】2．一个文法所有句子的集合构成该文法定义的语言。【】3．非终结符可以有综合属性，但不能有继承属性。【】4．逆波兰表示法表示表达式时无需使用括号。【】5．一个有穷自动机有且只有一个终态。【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。四解答题1．给定文法G和句型(T+F)*i+T,G:E→E+T

16、TT→T*F

17、FF→(E)

18、i（1）画出句型的语法树；（2）写出句型的全部短语、简单短语和句柄。解：（略）2．设有文法G：S→S+S

19、

20、S*S

21、i

22、(S)。（1）对于输入串i+i*i给出一个最左推导；（2）该文法是否是二义性文法？请证明你的结论。解：（1）i+i*i的最左推导：S=>S+S=>i+S=>i+S*S=>i+i*S=>i+i*i（2）该文法是二义性的。因为对于句子i+i*i可以画出两棵语法树（语法树略）。3．给出语言{ambmcn

23、m≥1,n≥0}的上下文无关文法（2型）。-8-解：G:S→AB

24、AA→aAb

25、abB→cB

26、c4．给出语言{akbmcn

27、k,m,n≥1}的正规文法（3型）。解：G:A→aA

28、aBB→

29、bB

30、bCC→cC

31、c5．将文法G改写成等价的正规文法（3型）。G:S→dABA→aA

32、aB→bB

33、b解：G:S→dAA→aA

34、aBB→bB

35、b6．构造一文法产生任意长的a，b串，使得

36、a

37、≤

38、b

39、≤2

40、a

41、其中，“

42、a

43、”和“

44、b

45、”分别表示串中的字符a和b的个数。解：b的个数在a的个数和其2倍之间，串的结构形如aSBS和BSaS，其中B为1或2个b。故得文法G:S→aSBS

46、BSaS

47、εB→b

48、bb7．设有字母表{a，b}上的正规式R=(ab

49、a)*。（1）构造R的相应有限自动机；解：012

50、3baaεε-+（2）构造R的相应确定有限自动机；解：将（1）所得的非确定有限自动机确定化εab-01131221+3ab-8--+013123+12312313+13123012aaba-+++（3）构造R的相应最小确定有限自动机；解：对（2）得到的DFA化简，合并状态0和2为状态2：12aab-++（4）构造与R等价的正规文法解：令状态1和2分别对应非终结符B和AG:A→aB

51、a

52、εB→aB

53、bA

54、a

55、b

56、ε可化简为：G:A→aB

57、εB→aB

58、bA

59、ε8．写出如图所示的自动机描述的语言的正规

60、式1324babab-+0aa+解：abb*

61、abb*aa*b

62、aaa*b9．写出在{a,b}上，不以a开头，但以aa结尾的字符串集合的正规式（并构造与之等价的最简DFA）。解：依题意，“不以a开头”，则必以b开头，又要“以aa结尾”，故正规式为：b(a

63、b)*aa（构造与之等价的最简DFA，此略）-8-10．写一个LL(1)文法G，使其语言是L(G)={ambnc2n

64、m>=0,n>0}并证明文法是LL(1)。解：文法G（S）：S®aS

65、EE®bE’E’®Ecc

66、ccSelect(S®aS)∩