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

（200 -200 学年第 学期）

课程号： 课程名称： 编译原理 任课教师： 金军 于中华 刘俊

适用专业年级： 2010 学号： 姓名：

1．简答题

1.符号表的作用是什么？为了达到对其插入删除等操作的复杂度为O(1)，需将其组织成什么数据结构。

2.分析树和语法书的区别。

3.什么是正规集。

4.什么叫句子，什么叫句型。

5.二义文法一定不是LL（1）

2．给定文法

S→A

A→A+A|B++

B→y

1.画出句子y+++y++的分析树

2.给出句子y+++y++的最右推导

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

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

2.用子集法对（1）得到的NFA进行确定化和最小化，得到等价的最小DFA。

3.使用双层多分支语句实现（2）得到的DFA。写出伪代码。

4．给定文法

statement→if-stmt|other|e

if-stmt→if(exp)statement else-part

else-part→else statement|e

exp→0|1

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

5．给定文法

S→[SX]|a

X→e|+SY|Yb

Y→e|-SXc

1.对文法中的每一个非终结符构造First集和Follow集。

2.构造LL（1）分析表

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

6．给定文法

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）算法的描述

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