编译原理试题

西南大学育才学院第10届毕业大补考《编译原理》课程考试试题（A）卷 一、填空题（共10题，20分，每题2分）

1. 高级程序设计语言的翻译主要有两种方式：____________和____________。 2. 编译程序的工作过程主要分为如下几个阶段：词法分析、语法分析、语义分析、____________、____________、目标代码生成。

3. 文法G产生的_________________________的全体是该文法描述的语言。 4. 算符优先分析法中每次归约的是当前句型的________________________。 5. 自上而下语法分析方法中会遇到的主要问题有左递归和______________。 6. 假设有文法G[S]：S?Sa|b，对该文法消除左递归后得到的文法为________________________。

7. 以01结尾的二进制串的正规式描述为___________________________。

8. 属性文法中综合属性用于“自下而上”传递信息，而_______________属性用于“自上而下”传递信息。

9. 表达式(a+b)* c的逆波兰式是______________________________________。 10. 以下方法中不能够用于表示源程序中间代码形式的有__________________。 A. 语法分析树 B. 逆波兰表示法 C. 三地址代码 D. 抽象语法树

二、简答题（共4题，每题5分，共20分） 1. 简述文法的形式化定义。 2. 什么是二义性文法？

3. 简述自上而下语法分析过程的含义。 4. 简述FOLLOW集合的定义。 三、综合计算题（共5题，共60分）

1． 请画出编译程序的基本结构框图。（10分）

2． 已知：基本字母表∑={a, b}，则∑*={ε，a，b，aa，ab，bb，aaa，…}， U={ aa,ab}，V={ ba, bb}，U和V都是∑*的子集，请求出如下字符串集合： UV＝｛ ｝，U0={ }，U2 ＝｛ ｝，U3=｛ ｝。（10分） 3． 令文法为G[E]： E? T| E+T | E-T T? F| T*F | T/F F? (E) | i

（1）给出句子i * (i + i )的最左推导和最右推导。 （2）给出句子i * (i + i )的的句柄。（10分）

4． 构造正规式1（0|1）*101相应的DFA。（10分） 5． 已知文法G[S]: S?aH H?aMd |d M?Ab|ε

A?aM|e

（1） 计算文法中每个非终结符的FIRST集合和FOLLOW集合。（5分） （2） 判断该文法是否为LL(1)文法？（5分） （3） 构造该文法的预测分析表。（10分） 一、填空题（共10题，20分，每题2分） 1. 编译、解释

2. 中间代码生成、代码优化 3. 句子 4. 最左素短语 5. 回溯

6. S?bS’, S’?aS’|ε 7. (0|1)*01 8. 继承属性 9. ab+c* 10. A

二、简答题（共4题，每题5分，共20分） 1. 简述文法的形式化定义。

文法G是一个四元组（VN，VT，P，S）。其中VN为非终结符集合，非终结符表示语法实体或语法变量；VT为终结符集合；P为产生式集合，P中每个产生式的形式为α—>β，其中α∈( VN∪VT )*且至少包含一个非终结符，β∈( VN∪VT )*；S称为文法的开始符号。 2. 什么是二义性文法？

某文法若存在一个句子对应两棵不同的语法树，则说这个文法是二义性文法。或者说，若一个文法中存在某个句子，有两个不同的最左推导或最右推导，则该文法是二义的。

3. 简述自上而下语法分析过程的含义。

所谓自上而下语法分析，是从文法的开始符号出发，反复使用各产生式，寻找“匹配”于输入符号串的推导。从语法树的角度来看，自上而下方法是从文法符号开始，将它作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。 4. 简述FOLLOW集合的定义。

文法中非终结符A的FOLLOW集定义为： FOLLOW（A）＝{ a| S ==>*….Aa…., a∈VT }。 若有S ==>*….A，则规定＃∈FOLLOW（A）。 三、综合计算题（共6题，每题10分，共60分） 1. 请画出编译程序的基本结构框图。

2. 已知：基本字母表∑={a, b}，则∑*={ε，a，b，aa，ab，bb，aaa，…}， U={ aa,ab}，V={ ba, bb}，U和V都是∑*的子集，请求出如下字符串集合： UV＝｛aaba, aabb, abba, abbb｝， U0 = {ε}

U2 ＝UU=｛aaaa, aaab, abaa, abab｝

U3 ＝UUU=(UU)U=｛ aaaaaa,aaabaa,abaaaa,ababaa， aaaaab,aaabab,abaaab,ababab｝

3．（1）给出句子i * (i + i )的最左推导和最右推导。 句子i * (i + i )的最左推导为：

E==>T==>T*F==> F*F==> i*F==> i*(E) ==> i*(E+T) ==> i*(T+T) ==> i*(F+T) ==> i*(i+T) ==> i*(i+F) ==> i*(i+i) 句子i * (i + i )的最右推导为：

E==>T==>T*F==> T*(E) ==> T*(E+T) ==> T*(E+F) ==> T*(E+i) ==> T*(T+i) ==> T*(F+i ) ==> T*(i+i) ==> F*(i+i) ==> i*(i+i) (2)则该句子的句柄为：i

4.（1）正规式1（0|1）*101对应的NFA：

（2）从NFA的初始状态X的转换过程：

重新命名状态，令AB为B，AC为C，ABY为D。 得到新DFA的状态转换图如下所示：

5．（1）计算文法中每个非终结符的FIRST集合和FOLLOW集。 非终结符 FIRST集 FOLLOW集 S { a } { # } H { a, d } { # } M { a, e,ε} {d, b} A {a, e } {b}

（2）判断该文法是否为LL(1)文法。 ① 文法不含有左递归；

② 对与如下产生式，候选式的FIRST集的交集为空。 H?aMd |d M?Ab|ε A?aM|e

③ 因为ε∈FIRST( M )，故考察FIRST（M）与FOLLOW(M)的交集为空 综上所述，该文法为LL（1）文法。

（3）构造该文法的预测分析表：(网页显示有问题)

a d b e ＃ S ?aH H ?aMd ?d M ?Ab ?ε ?ε ?Ab A ?aM ?ε