编译原理试卷(A)--2007 - 下载本文

? ? 头号??课?? ? ?? ? ?? ? ? 学号??? ? ?线 ? ? 名姓 ??? ? ?? 密 ? ? 级?? 班? ?? ? ? ??? 院? 学?? ? ? ?

河南农业大学2007—2008学年第一学期 《 编译原理 》考试试卷(A 卷) 题号 一 二 三 四 总分 分数 得分 评卷人 一、 填空题(每空1分,共15分) 1、 计算机执行用高级语言编写的程序主要有两种途径:_____________和_________________。 2、 正规表达式的“|”读作___________,“*”读作_________________。3、 自下而上语法分析方法的基本思想是:从待输入的符号串开始,利用文法的规则步步向上进行归约,试图归约到文法的____________。 4、 LL(1)分析法中,第一个L的含义是_____________________,第二个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和M2的状态数和有向边条数相等 3、在规范归约中,用_________来刻画可归约串。

A、直接短语 B、句柄 C、最左素短语 D、素短语

4、有文法G[I]: A→aAb|bAa|ε。下列符号串中是该文法的句子有________。

A.aabb B. baaa C. bba D.aaab

5、已知文法G(S) {S?AB,A?0A1|ε,B?1B0|ε},则以下符号串中,能成为短语的是________。 A.010101 B. 0101 C. 0110 D.1001 6、四元式之间的联系是通过_____实现的。 A.指示器 B.临时变量

C.符号表 D.程序变量 7、LL(1)文法的条件是______。

A.对形如U->Xl|X2|?|Xn的规则,要求FIRST(Xi)∩FIRST(Xj)=Φ,(i≠j)

B.对形如U->Xl|X2|?|Xn的规则,若Xi=>*ε,则要求FIRST(Xj)∩FOLLOW(U)=Φ C.a和b D.都不是 8、已知文法G[E]

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

? ? ?? ? ? 头号课??? ? ?? ? ? ? ??学号? ?线 ? ? 名???姓? ?? 密 ? ??? ?级 班?? ? ? ? ?? 院? 学?? ? ? ?

得分 评卷人 三、简答题(每道7分,共35分) 1、已知文法G[E]: 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分) ? ?? ? ? ? 学号??? ?线 ? ? 名???姓? ?? 密 ? ??? ?级 班?? ? ? ? ?? 院? 学?? ? ? ? 5

2、已知文法G[A]: A (A)|a,构造该文法的LR(0)分析表。 (15分)

6