四川大学计算机学院2012—2013年编译原理期末考试题 金军 于中华 刘俊 罗以宁

四川大学期末考试试题（闭卷）

（200 -200 学年第 学期）

课程号：

课程名称： 编译原理

学号：

任课教师： 金军 于中华 刘俊

姓名：

适用专业年级： 2010

考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。 四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。 题 号 得 分 阅卷教师 阅卷时间 一 二 三 四 五 六 七 八 卷面成绩 一．简答题 1.符号表的作用是什么？为了达到对其插入删除等操作的复杂度为O(1)，需将其组织成什么数据结构。 2.分析树和语法书的区别。 3.什么是正规集。

4.什么叫句子，什么叫句型。 5.二义文法一定不是LL（1）

二．给定文法 S→A

A→A+A|B++ B→y

1.画出句子y+++y++的分析树 2.给出句子y+++y++的最右推导

三．给定正则表达式（a|b）*abb

1.使用thompson构造法构造等价的NFA。

2.用子集法对（1）得到的NFA进行确定化和最小化，得到等价的最小DFA。 3.使用双层多分支语句实现（2）得到的DFA。写出伪代码。

四．给定文法

statement→if-stmt|other|e

if-stmt→if(exp)statement else-part else-part→else statement|e exp→0|1

写出递归下降子程序的伪代码。

注：试题字迹务必清晰，书写工整。 本题2页，本页为第1页

教务处试题编号：

课程名称：

任课教师： 学号： 姓名：

------------------------------------------------------------------------------------------------------------------------

五．给定文法 S→[SX]|a X→e|+SY|Yb Y→e|-SXc

1.对文法中的每一个非终结符构造First集和Follow集。 2.构造LL（1）分析表

3.基于分析表，使用LL(1)对句子[a+a-ac]进行自顶向下的语法分析，给出每一步的动作及分析栈和输入串的变化情况。

六．给定文法 E→E+T|T T→T*F|F F→(E)|id

1.构造LR（0）项目的DFA： 2.构造SLR（1）的分析表

3.利用2得到的分析表对id+id*id进行自顶向下的语法分析。 七．

1.给出构造Follow集合的算法描述 2.给出SLR（1）算法的描述

本题2页，本页为第2页 教务处试题编号：