编译原理试卷.doc

常 州 工 学 院 试 卷D卷 共5页 第5页班 级_姓 名_学 号 _装 订 线班 级_姓 名_学 号 _装 订 线 一、单项选择题。（10分）1.动态存储分配时，可以采用的分配方法有_ C _。 以过程为单位的栈式动态存储分配 堆式存储分配 最佳分配方法 A、 B、 C、 D、2.面向机器语言的特点是_ D _。 A、程序的执行效率低，编制效率低，可读性差 B、程序的执行效率高，编制效率高，可读性强 C、程序的执行效率低，编制效率高，可读性强 D、程序的执行效率高，编制效率低，可读性差3. 下面关于解释程序的描述正确的是 B 。 解释程序的特点是处理程序时不产生目标代码。 解释程序适用于COBOL和FORTRAN语言。 解释程序是为打开编译程序技术得僵局而开发的。A、 B、 C、 D、 4. 编译过程中，语法分析器的任务是 B 。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构A、 B、 C、 D、 5. 一个句型中的最左 B 成为该句型的句柄。 A、短语 B、简单短语 C、素短语 D、终结符号 二、填空题 （15分）1. 如果在一个文法中存在某个句子，它有 二个以上 得最左（最右）推导，也就是说，若该句子对应两棵不同的 语法树 ，则这个文法是 二义性 文法。 2. 对编译程序而言，输入数据是源程序，输出结果是 目标程序 。3. LR(1)分析法中，L的含义是 自左向右进行分析 ，R含义是采用最右推导的逆过程最左归约，“1”的含义是 至多向前查看一个输入符号。4. 语法分析是依据语言的语法 规则进行的，中间代码产生是依据语言的语义 规则进行的。5. 编译过程中，常见的中间语言形式有 三元式 、逆波兰式和 四元式 。6. 编译过程中扫描器所完成的任务是从 源程序 中识别出一个一个具有独立 语法意义的单词 。 三、简答题。（30分） 1、简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树的角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。2、设有文法GA的产生式集为: ABaC|CbB BAc|c CBb|b 试消除GA的左递归。 提示：不妨以A、B、C排序.先将A代入B中，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。 最后结果为:GA: ABaC|CbB BCbBcB|cB BaCcB| CcBbC|bC CbBcBbC|3、写出表达式a+b*(c-d)+e/(c-d)*n的三元式序列或P代码表示。(1)（_,c,d）(2) (*,b,(1)(3) (+,a,(2)(4) (_,c,d)(5) (/,e,(4)(6) (*,n,(5)(7)(+,(3),(6)4、什么样的文法是算符优先文法，请举个算符优先文法的例子。设文法G，如果它的产生式右部不包含相邻非终结符号，则称文法G为算符文法，如果算符文法的终结符号集中任意两个符号之间至多存在一种优先关系，则称该算符文法为算符优先文法。例如：E-E+T|TT-T*F|FF-(E)|i+*()i+(=i5、解释什么是归约？我们称直接归约出A，仅当A 是一个产生式， 且、(VNVT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。 四、为以下字符集编写正规表达式，并构造其Thompson结构图以及与之等价的最简DFA（写出详细的具体过程）： 在字母表S = 0,1上的包含偶数个0且含有任意数目1的所有字符串。（15分）正规表达式： (1*01*01*)* 最简DFA： 1 0 1 0 五、已知文法G： （15分） S LaR|R L bR|c RL1） 判断该文法是否为LR(1)文法。2）若是则构造文法G的LR(1)项目集规范族。3）若是则构造文法G的LR(1)预测分析表。 （15分）因为状态机中没有冲突，所以是LR(1)文法。 LR(1)分析表如下： (1) S LaR (2) S R (3) L bR (4) L c (5) R L a b c # S L R 1 S6 S4 2 5 3 2 Acc 3 R2 4 R4 R4 5 S7 R5 6 S6 S4 8 9 7 S12 S13 11 10 8 R5 R5 9 R3 R3 10 R1 11 R5 12 S12 S13 11 14 13 R4 14 R3 六、把下面程序段：for I:=1 setp 1 until N dowhile AD then x:= C else X:= D 翻译成四元式序列。（写上注释，15分）100（:=,1_,i）101(j,_,_,103)102(+,I,1,I)103(j,I,N,105)104(j,_,_,114)105(j,C,D,