班 级 学 号 姓 名 平顶山工学院2005—2006学年第二学期期末考试（试） ☆ 《编译原理》试题（A卷）
☆ 供 计算机科学与技术 专业 0614031/2/3/4/5 班使用 2006年6月 一 二 三 四 五 题 号 总 分 密 得 分 阅卷人 封 线 内 不 要 答 题 ☆ ☆ 1、构造正规式1(0∣1)*101相应的DFA.
2、已知文法G[S]:
S→a∣^∣(T) T→T，S∣S
求(((a,a),^,(a)),a)的最左推导。
本套试卷共 3 页
一、填空题（每空1分，共11分）
1、高级语言编写的程序可以通过（ ）和（ ）两种方式来执行。
2、整个编译过程可划分为（ ）、（ ）、语义与中间代码生成、（ ）和（ ）五个阶段。
3、a+b*（－d＋c）的逆波兰表示为（ ）。
4、“数组下标越界”这个错误信息会在编译的（ ）阶段报告。 5、目前语法分析常用的方法有（ ）和（ ）两大类。 6、词法分析器的输入是源程序，其输出是( )。
二、选择题（每空2分，共10分）
1、文法 G 产生的 （ ）的全体是该文法描述的语言。 A．句型 B. 终结符集 C. 非终结符集 D. 句子 2、描述一个语言的文法是（ ）
A.唯一的 B.不唯一的 C．可能唯一，也可能不唯一
3、Chomsky 定义的四种形式语言文法中， 2 型语言又称 （ ）。
A．短语文法 B．上下文有关文法 C．上下文无关文法D． 正规文法
4、令∑＝{a，b}，∑上的正规式（a∣b）*对应的正规集是（ ）。
A．{aa，ab，ba，bb} B．{ab} C．{a，b} D．{ε，a，b，aa，ab…所有a，b组成的串}
5、简单优先分析每次归约的是（ ）
A. 最左直接短语 B.直接短语 C.最左素短语 D.控制结点
三、计算题（每题6分，共24分）
《编译原理》试题A卷 第 1 页 共 3 页
3、已知文法G[E]为：
☆ E→T∣E+T T→F∣T*F ☆ F→(E)∣i 试确定F+T*i的最左素短语。 密 封 名 线 姓 内 不
号 4、将表达式(a+b)/(a-b)-a(a+b*c)表示成四元式序列。 学 要 答 级 班题 ☆ ☆
四、证明题（每题10分，共20分） 1、证明下面的文法是二义的：
G=({A，B，S}，{a，b，c}P，S)，其中P为： S→Ac∣aB A→ab B→bc
2、证明下述算术表达式文法G[E]是一个算符文法，但不是算符优先文法。G[E]：E→E+E∣E*E∣(E)∣i
A卷 第 2 页 共 3 页
《编译原理》试题
五、综合题（共35分，第1题15分，第2题20分）
☆ 1、正规表达式（a∣b）*(aa∣bb)(a∣b)*的NFA M如图所示，试将其确定化，并最小化。
3☆ aaaa
X密 1256Y22、已知文法G[S]： S→aH
H→aMd∣d M→Ab∣ε A→aM∣e
① 判断G[S]是否为LL（1）文法，若是，请构造相应的LL（1）预测分析表。 ② 给出对输入串aaabd#的预测分析过程，并说明该输入串是否是G[S]的句子
封 名 线 姓 内 不 号 学 要 答 级 班题 ☆ ☆
bbb4 bA卷 第 3 页 共 3 页
《编译原理》试题
因篇幅问题不能全部显示，请点此查看更多更全内容