编译原理窦全胜答案

1、学号：_ 班级：_ 专业： _ 姓名：_第4页 共4页。装。订。线。2008 年2009 年第 一 学期 编译原理 试卷 B卷答案解释：编译前端，编译后端、遍(5分)前端：编译过程中，与源语言有关但与目标机无关的那些部分。后端：编译过程中，与目标机有关但与源语言无关的那些部分。遍：是将源程序或源程序的中间结果从头到尾扫描一次,并作加工处理生成新的中间结果或目标程序的过程.给出生成语言 anbn| n=0的上下文无关文法(5分)解：给出正规式的定义. (5分)设是一个有穷字母表，它的每个元素称为一个字符。下面是正规式和正规集的递归定义：1.和 都是 上的正规式，它们所表示 的正规集分别为 和 2

2、.任何，是上的一个正规式，它所表示的正规集为 3.假定U和V都是 上的正规式，它们所表示的正规集分别 L（U）和L（V），那么，（U V）、（U|V）和（U）*也都是正规式，它们所表示的正规集分别为L（U）L（V）、L（U）|L（V）和 （L（U）*（闭包）。 仅由有限次使用上述三步而定义的表达式才是上的正规式， 4、证明下面文法是二义的：(5分)证明：考察句型存在两种不同的最左推导，故文法是二义的 知文法G为： 试写出句型：所有短语、直接短语和句柄(7分)解:短语：直接短语:句柄:若优先顺序从高到低为，同级采用左结合，计算表达式：的值，并画出该表达式的抽象语法树和DAG图(8分)抽象语法树:

3、 DAG:二、已知文法G(E)ET|ETTF|T * FF(E)|i给出句型(T * Fi)的最右推导及画出语法树； 三、试构造以下文法的算符优先表解：FIRSTVT(E)= LASTVT(E)= FIRSTVT(T)= LASTVT(T)=FIRSTVT(F)= LASTVT(F)=FIRSTVT(P)= LASTVT(P)=该文法算符优先表为：+*i()#+*i(#=四、已知NFA如下图所示，试将之确定化、最小化aa10aa|b解：将该NFA改造,生成新的NFA如图所示：aaX0Y1aba利用子集法得：IIaIbX,0,Y0,1,Y10,1,Y0,1,Y110,Y-0,Y0,1,Y1将每个

4、集合看成是一个状态，则得状态转化矩阵如下，该状态转化矩阵确定一个DFA：Sab01211223-312下面将该DFA化简首先，将状态中的终止状态和非终止状态分开，形成分划：考察，故该分划不可再分令状态0代表将原来到达1,3的弧都导入0,由1，3发出的弧都由0发出,同时删去1，3从而形成最简DFASab00220-五、（共20分）已知如下LL(1)文法1、求出文法中所有非终结符的FIRST和FOLLOW集合解:First(E)=, Follow(E)=First(E)=, Follow (E)=First(T)= , Follow (T)=First(T)=, Follow (T)= First

5、(F)= , Follow (F)= 2、构造LL(1)预测分析表,并利用该分析表给出串的分析过程解由1)构造预测分析表如下:#串的分析过程:步骤 符号栈 输入串 产生式 0 #E (i+i)*i# 1 #ET (i+i)*i# 2 #ETF (i+i)*i# 3 #ET)E( (i+i)*i# 4 #ET)E i+i)*i# 5 #ET)ET i+i)*i# 6 #ET)ETF i+i)*i# 7 #ET)ETi i+i)*i# 8 #ET)ET +i)*i# 9 #ET)E +i)*i# 10 #ET)ET+ +i)*i# 11 #ET)ET i)*i# 12 #ET)ETF i)*i# 13 #ET)ETi i)*i# 14 #ET)ET )*i# 15 #ET)E )*i# 1