四川大学编译原理期末试卷4套+复习资料.pdf

四川大学期末考试试题A(闭卷)

(2012-2013学年第2学期)

一．简答题

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)statementelse-part

else-part→elsestatement|e

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

四川大学期末考试试题(闭卷)

(2010-2011学年第2学期)

1.简答题(12分)

(1)编译器的前端和后端分别包括哪几个阶段？前后端分开有什么好处？

(2)解释器和编译器有什么本质区别？

(3)词法分析和语法分析的功能分别是什么？

(4)分析树与抽象语法树有什么不同？

2.已知字母表∑={a,b,c}∑上的语言L具有以下特征：(5分)

(1)若出现a，则其后至少紧跟两个c；

(2)若出现b，则其后至少紧跟一个c。

试给出可以产生语言L的正规表达式。

3.文法如下：(8分)

exp→expaddopterm|term

addop→+|-

termterm→mulopfactor|factor

mulop→*

factor→(exp)|number

(1)给出句子3*)58(

(2)构造(1)中句子的抽象语法树。

4.文法如下：(10分)

exp→expandexp|exporexp|notexp|(exp)|TRUE|FALSE

(1)此文法是否为二义文法？为什么？

(2)试将文法改写为非二义文法，要求运算符优先级由低到高分别是or、and、not，且and

和or是左结合的，not是右结合的。

5.DFA构造题(20分)已知正规表达式bbca*)|(

(1)使用Thompson构造方法构造对应的NFA；(2)用子集构造法将得到的NFA确定化为

DFA；(3)将得到的DFA最小化。

6.LL(1)分析题(20分)

文法如下：A→PaP→bPa|bQbQ→Qa|a

(1)消除文法左递归，提左因子；

(2)为所得文法的每个非终结符构造First集和Follow集；(3)所得文法是LL(1)文法吗？为

什么？(4)构造所得文法的LL(1)分析表。

7.LR(k)分析题(25分)文法如下：

declaration→typelist-var

type→int|float

var-list→id,var-list|id

(1)构造文法的LR(0)项目的DFA；(2)构造SLR(1)分析表；

(3)这个文法是SLR(1)文法吗？如果不是，请说明原因；

(4)给出对应输入串intx,y,z进行SLR(1)分析的步骤(要求给出分析过程中每一步的详细情

况，包括：分析栈、输出串及执行的动作)。

四川大学期末考试试题A(闭卷)

(