编译原理试卷(A)--2007

1、编译原理试卷(a)-2007 ? ? 头号?课? ? ? ? ? ? ? 学号? ? ?线 ? ? 名姓 ? ? ? 密 ? ? 级? 班? ? ? ? ? 院? 学? ? ? ? 河南农业大学xxxx年第一学期 编译原理 考试试卷（a 卷） 题号 一 二 三 四 总分 分数 得分 评卷人 一、 填空题（每空1分，共15分） 1、 计算机执行用高级语言编写的程序主要有两种途径：_和_。 2、 正规表达式的“|”读作_，“*”读作_。3、 自下而上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行归约，试图归约到文法的_。 4、 ll(1)分析法中，第一个l的含义是_，第

2、二个l的含义是_。 5、 对于数据空间的存储分配， c采用_存储分配策略。 6、 语法分析最常用的两类方法是_和_-分析法。7、 编译过程中，常见的中间语言形式有_、_、 三元式和树形表示法。 8、 一个lr分析器包括两部分：一个总控程序和_。 9、 语法制导的编译程序能同时进行_分析和_分析。 1 得分 评卷人 二、选择题（每题2分，共20分） 1、编译程序是对_。 a、汇编程序的翻译 b、高级语言程序的解释执行 c、机器语言的执行 d、高级语言的翻译 2、正规式m1和m2等价是指_。 a、m1和m2的状态数相等 b、m1和m2的有向边条数相等 c、m1和m2所识别的语言集相等 d、m1和m

3、2的状态数和有向边条数相等 3、在规范归约中，用_来刻画可归约串。 a、直接短语 b、句柄 c、最左素短语 d、素短语 4、有文法gi: aaab|baa|。下列符号串中是该文法的句子有_。 aaabb b. baaa c. bba d.aaab 5、已知文法g(s) s?ab,a?0a1|,b?1b0|,则以下符号串中，能成为短语的是_。 a010101 b. 0101 c. 0110 d.1001 6、四元式之间的联系是通过_实现的。 a指示器 b临时变量 c符号表 d程序变量 7、ll(1)文法的条件是_。 a.对形如u-xl|x2|?|xn的规则，要求first(xi)first(xj

4、)=，(ij) b.对形如u-xl|x2|?|xn的规则，若xi=*，则要求first(xj)follow(u)= ca和b d都不是 8、已知文法ge e-te e-+te| t-ft t-*ft| f一(e)|id follow(f)=_ a.*，+ b. #， c+，#， d*， +， #, 9、若a为终结符，则a?a为_项目。 a、归约 b、移进 c、接受 d、待约 10、在 lr 分析法中，分析栈中存放的状态是识别规范句型_的 dfa 状态。 a.句柄 b.前缀 c.活前缀 d. lr(0) 项目 2 ? ? ? ? ? 头号课? ? ? ? ? ? ?学号? ?线 ? ? 名?姓?

5、 ? 密 ? ? ?级 班? ? ? ? ? 院? 学? ? ? ? 得分 评卷人 三、简答题（每道7分，共35分） 1、已知文法ge: e et+|t，t tf*|f，f f |a 证明ff *是文法的句型，并给出该句型的短语、直接短语和句柄。（7分） 2、给出语句if a?b 4、消除下列文法的左递归 : s aa|b a 5、某程序的结构如下图所示，其中a、b、c为过程名，请分别填出过程c调用a前后的栈顶活动记录示意图中空白处的内容。（7分） ac|sd （7分） a_top display 表 参数个数：0 全局display表地址 返回地址 a_sp 局部变量:x c_top display 表 参数个数：0 全局display表地址 返回地址 b_sp c_sp 4 课头号 ? 得分 评卷人 四、综合题(每题15分，共30分) 1、设计一个最小化的dfa，其输入字母表是0,1，接受以0开头，以1结尾的所有序列。 （15分） ? ? ? ? ? 学号? ?线