编译原理复习例题

编译原理复习例题

ID:33829901

大小:180.50 KB

页数:8页

时间:2019-03-01

编译原理复习例题_第1页
编译原理复习例题_第2页
编译原理复习例题_第3页
编译原理复习例题_第4页
编译原理复习例题_第5页
资源描述:

《编译原理复习例题》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

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定义的语言是。[A

5、]{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]ab@c-

10、*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、S*S

20、i

21、(S)。(

22、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→bB

29、bCC→cC

30、c5.将文

31、法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的相应有限自动机;解:0123baaεε-+(2)构造R的相应确

50、定有限自动机;解:将(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.写出如图所示的自动机描述的语言的正规式1324babab-+0aa+解:abb

60、*

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)∩

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。