资源描述：
《编译原理试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、填空（每题2分，共20分）1．从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。2．扫描器的任务是从（源程序）中识别出一个个（单词符号）。3．所谓最左派生是指（）。4．语法分析最常用的两类方法是（自顶向下）和（自底向上）分析法。5．一个上下文无关文法所含的四个组成部分是（一组终结符号，一组非终结符号、一个开始符号、一组产生式）。6．所谓语法制导翻译方法是（为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序）。7．LR分析法中的两种冲突是（移入—归约）和（归约—归约）。8．产生式是用于定义（语法范畴）的一种书写规则。9．属性定义中有两种性质
2、的属性，分别是（继承属性）和（综合属性）。10．常用的两种动态存储分配方法是（栈式动态分配）和（堆式动态分配）。11.所谓最右推导是指：任何一步αβ都是对α中最右非终结符进行替换的。12.一个过程相应的DISPLAY表的内容为（现行活动记录地址和所有外层最新活动记录的地址。）13.符号表中的信息栏中登记了每个名字的有关的性质，如（类型、种属、所占单元大小、地址）等等。14．运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的
3、diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。二、名词解释（每题3分，共15分）1．编译器预处理――(P4,7)2．LL（K）文法――（P89）3．歧义文法――(p71)4．正则表达式――(P47)1．属性文法――(P260)三、简答题（每题5分，共15分）1．设有L（G）＝{a2n+1b2m+1c2p
4、n>=1,m>＝1,p>=1}1)给出它的正则表达式。2)构造识别该语言的DFA。2．生成语言L（G）＝{apbmcpanbn
5、p>=0
6、,m>=1,n>=2}的文法G是什么？它是chomsky的哪型文法。解：G(3)文法为S->ACA->aAc
7、BB->bB
8、bC->aCb
9、ab它是乔姆斯基2型文法3．已知文法G（S）：S→a
10、b
11、(T)T→T,S
12、S写出句子（（a,b）,b）的规范规约过程及每一步的句柄。解：句型规约句柄（（a,b）,b）（（S,b）,b）S->aa((T,b),b)T->SS((T,S),b)S->bb((T),b)T->T,ST,S(S,b)S->(T)(T)(T,b)T->SS(T,S)S->bb(T)T->T,ST,SSS->(T)(T)四、计算题（每题10分，共20分）1．已知文法G（
13、E）E→T
14、E+TT→F
15、T*FF→(E)
16、i给出句型α＝（T*F+i）的最右派生及画出语法树。解：1.(4分)EÞTÞFÞ(E)Þ(E+T)Þ(E+F)Þ(E+i)Þ(T+i)Þ(T*F+i)2.(4分)短语：(T*F+i),T*F+i,T*F,i直接短语：T*F,i句柄：T*F素短语：T*F,i2．说明下面的文法不是SLR(1)文法，并重写一个等价的SLR(1)文法。S®Ma
17、bMc
18、dc
19、bdaM®d解：S’®SS®Ma
20、bMc
21、dc
22、bdaM®dS’®.SS®.MaS®.bMcS®.dcS®.bdaM®.dS®b.McS®b.daM®.dS®bd.aM®d.bd因为a是M
23、的后继符号之一，因此在上面最右边一个项目集中有移进-归约冲突。等价的SLR(1)文法是S®da
24、bdc
25、dc
26、bda五、设计题（每题15分，共30分）1．下面的文法定义语言L={anbncm
27、m,n³1}。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L1={anbncn
28、n³1}的句子，打印出错信息。S®DCD®aDb
29、abC®Cc
30、c解：语法制导的定义如下：S®DCifD.length¹C.lengththenprint(“error”)D®abD.length:=1D®aD1bD.length:=D1.length+1C®cC.length:=1C®C1cC.
31、length:=C1.length+12.给出文法G（L）的翻译模式，它分别计算字符串中0与1的个数。（要求ANTLR代码）S→L.L
32、LL→BLL→εB→0
33、1GrammerL01@members{intn0;intn1;}Start:{n0=0;n1=0;}j{system.out.println(n0);system.out.println(n1);};j:‘0’j{n0+=1;}
34、‘1’j{n1+=1;}
35、‘a’;ws:(‘’
36、‘t’
37、‘’
38、‘r’)+{skip(
