编译原理试卷.doc

一、填空（每题2分，共20分）1从功能上说，程序语言的语句大体可分为（ 执行性 ）语句和（ 说明性 ）语句两大类。2扫描器的任务是从（ 源程序 ）中识别出一个个（ 单词符号 ）。3所谓最左派生是指（ ）。4语法分析最常用的两类方法是（ 自顶向下 ）和（ 自底向上 ）分析法。5一个上下文无关文法所含的四个组成部分是（一组终结符号，一组非终结符号、一个开始符号、一组产生式 ）。6所谓语法制导翻译方法是（ 为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序 ）。7LR分析法中的两种冲突是（ 移入归约 ）和（ 归约归约 ）。8产生式是用于定义（ 语法范畴 ）的一种书写规则。9属性定义中有两种性质的属性，分别是（ 继承属性 ）和（ 综合属性 ）。10常用的两种动态存储分配方法是（ 栈式动态分配 ）和（ 堆式动态分配 ）。11. 所谓最右推导是指：任何一步都是对中最右非终结符进行替换的。12. 一个过程相应的DISPLAY表的内容为 （现行活动记录地址和所有外层最新活动记录的地址。）13. 符号表中的信息栏中登记了每个名字的有关的性质，如（ 类型、种属、所占单元大小、地址 ）等等。14运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。二、名词解释（每题3分，共15分）1 编译器预处理(P4,7)2 LL（K）文法（P89）3 歧义文法(p71)4 正则表达式(P47)5 属性文法(P260)三、简答题（每题5分，共15分）1 设有L（G）a2n+1b2m+1c2p | n=1, m1, p=11) 给出它的正则表达式。2) 构造识别该语言的DFA。2 生成语言L（G）apbmcpanbn | p=0, m=1, n=2的文法G是什么？它是chomsky的哪型文法。解：G(3)文法为S-ACA-aAc|BB-bB|bC-aCb|ab它是乔姆斯基2型文法3 已知文法G（S）： Sa|b|(T) TT,S|S 写出句子（a,b）,b）的规范规约过程及每一步的句柄。解：句型 规约 句柄（a,b）,b） （S,b）,b） S-a a(T,b),b)T-S S(T,S),b)S-b b(T),b)T-T,ST,S(S,b) S-(T)(T)(T,b) T-SS(T,S) S-bb(T)T-T,ST,SS S-(T) (T)四、计算题（每题10分，共20分）1 已知文法G（E）ET|E+TTF|T*FF(E)|i给出句型（T*F+i）的最右派生及画出语法树。解：1. (4分)ETF(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 M a | b M c | d c | b d aM d解：S S S M a | b M c | d c | b d aM dS .SS .M aS .b M cS . d cS . b d aM .dS b .M cS b .d aM .dS b d .aM d .bd因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进-归约冲突。等价的SLR(1)文法是S d a | b d c | d c | b d a五、设计题（每题15分，共30分）1下面的文法定义语言L = anbncm | m, n 1。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L1= anbncn | n 1的句子，打印出错信息。S D CD a D b | a bC C c | c解：语法制导的定义如下：S D Cif D.length C.length then print (“error”)D a bD.length := 1D a D1 bD.length := D1.length + 1C cC.length := 1C C1 cC.length := C1.length + 12. 给出文法G（L）的翻译模式，它分别计算字符串中0与1的个数。（要求ANTLR代码）SL.L| LLBLLB0|1Grammer L01members int n0; int n1;Start: n0=0; n1