《20061编译原理A卷答案》由会员分享，可在线阅读，更多相关《20061编译原理A卷答案（5页珍藏版）》请在金锄头文库上搜索。
1、 2006年期末考试A卷参考答案一、（12分）简答题：1 简述编译程序分成哪几个阶段。答： 编译过程通常需要经过词法分析、语法分析、中间代码生成、代码优化和目标代码生成五个阶段。另外还包括表格管理和出错处理。2 为什么要将词法分析与语法分析分离？答：将编译过程的分析工作划分成词法分析和语法分析两个阶段的理由如下：（1）使整个编译程序的结构更简洁、清晰和条理化（2）编译程序的效率会改进 ；（3）增强编译程序的可移植性。二、（6分）叙述由下列正规式描述的语言：1 (a|b)*(aa|bb)(a|b)*。含有相继2个a或b的a,b上的任意串。2 （0|1）（0|1）（0|1）0（0|1）* 第四位为
2、0的0，1上的任意串。三、（12分）构造一个DFA，它接受=a，b上所有满足下面条件的字符串，其条件是字符串中的每个b都有a直接跟在右边。解：正规式为V=(a|ba)*首先构造如下图所示的NFA MXY(a|ba)*X1abaYX1aY2ba再构造转换矩阵如下表、下图所示。012aabbIIaIbX,1,Y1,Y21,Y1,Y221,Y即：见下表Sab01211221化简，先将状态分终态组J1=0,1和非终态组J2=2考察J1，0,1a=10,1 0,1b=23不能再分组。重新命名上述状态子集将0,1用1代替 将2用1代替，见下表。这样得到如图所示的简化后的DFA M。10ba0Sab0011
3、01四、 （20分）对于文法G(E)E E + T | T T T *F | F F PF | PP (E) | i1 计算FIRSTVT和LASTVT；2 该文法是算符优先文法吗？3 计算优先关系。解：（1）构造FIRSTVT集合的LASTVT集合。FIRSTVT(P)=(,i),FIRSTVT(F)=,(,i),FIRSTVT(T)=*,(,i),FIRSTVT(E)=+,*,(,i);LASTVT(P)=,i,LASTVT(F)= ,i,LASTVT(T)=*, ,i,LASTVT(E)=+,*, ）(2)是算符优先文法。（3）构造算符优先表如下。 +*（）i#+*(= =) i#= =
4、五、(14分)设有文法G(E)：E a|b|(F)F F,E| E1 给出句子(a,a),b,(a,b)的最右推导；2 消除文法的左递归；3 改写后的文法是否是LL（1）的？为什么？4 出G的预测分析表。解：（1）最右推导为：E(F) (F,E) (F,(F) (F,(F,E) (F,(F,b) (F,(E,b) ( F,(a,b) (E,(a,b) (F,E,(a,b) (F,b,(a,b) (E,b,(a,b) (F),b,(a,b) (F,E),b,(a,b) (F,a),b,(a,b) (E,a),b,(a,b) (a,a),b,(a,b)(2)消除左递归，将文法改为：Ea|b|(F)
5、FEFF,EF| (3)构造该文法的FIRST集和FOLLOW集：FIREF(E)=FIREF(F)=a,b,()FIREF(F)=，, FOLLOW(E)=#, ，,FOLLOW(F)=FOLLOW(F)=) 改写后的文法是LL(1)的。(4)该文法的预测分析表如下表所示。ab(),#EEaEbE(F)FFEFFEFFEFFFF,EF六、（16分）对下述文法构造LR型的错误校正分析程序。（*优先级高于+，同级运算左结合）EE+EEE*EE(E)Ei并给出输入串 (i+(*i) 的错误校正处理过程。解：使用LR分析法进行语法分析，当输入符号既不能移入栈顶，而栈内符号又不能归约时，就意味着发现了
6、输入串中的语法错误，立即调用相应的错误处理子程序进行错误处理。前面给出的表达式文法G是一个二义性文法。下面给出与此文法相应的包含错误处理子程序的LR分析表。表中：Si表示把下一状态i和现行输入符号移进栈；ri表示按第i个产生式进行归约，acc是接受状态；e1、e2、e3和e4是相应的错误处理子程序，其功能分别为：e1：/*处在状态0、2、4、5时，当遇到+、*或#等符号时，调用此程序*/将一假想的i和状态3移进栈，并打印错误信息：“缺少运算量”。e2：/*当处在状态0、1、2、4、5而遇到右括号时，调用此程序*/从输入端删除右括号），并打印错误信息：“右括号不配对”。输入符号状 态ACTION
7、GOTOi + * ( ) #E0S3 e1 e1 S2 e2 e111e3 S4 S5 e3 e2 acc2S3 e1 e2 S2 e2 e163r4 r4 r4 r4 r4 r44S3 e1 e1 S2 e2 e175S3 e1 e1 S2 e2 e186e3 S4 S5 e3 S9 e47r1 r1 S5 r1 r1 r18r2 r2 r2 r2 r2 r29r3 r3 r3 r3 r3 r3e3：/*当处在1或6状态而又遇到i或左括号）时，调用此程序*/将运算符+和状态4移进栈，并打印错误信息：“缺少运算符”。e3：/*当处在1或6状态而又遇到i或左括号）时，调用此程序*/将运算符+和
8、状态4移进栈，并打印错误信息：“缺少运算符”。e4：/*当处在状态6，遇到#时，调用此程序*/将右括号）和状态9移进栈，并打印错误信息：“缺少右括号”。下面给出出错处理过程，在此使用了一个状态栈和一个符号栈，从而使分析过程更为清楚醒目。对输入串 (i+(*i)的错误校正处理过程如表所示：步 骤状 态 栈符 号 栈输 入 串附 注00#(i+(*i)#移进102#(i+(*i)#移进2023#(i+(*i)#归约3026#(E+(*i)#移进40264#(E+(*i)#移进502642#(E+( *i)#调用e1，将i和状态3移进栈，并打印“缺运算量”6026423#(E+(i *i)#归约70
9、266426#(E+(E *i)#移进80264065#(E+(E* i)#移进902642653#(E+(E*i )#归约步 骤状 态 栈符 号 栈输 入 串附 注1002642658#(E+(E*E )#归约11026426#(E+(E )#移进120264269#(E+(E) #归约1302647#(E+E #归约14026#(E #调用e4，将)和状态9移进栈，并打印“缺右括号150269#(E) #归约1601#E #分析完毕七、(12分) 将下列语句if AB then z:=x-y else z:=x+y 翻译成四元式序列.解： 100(J),A,B,102)101(J,，105
10、)102(-,x,y, T1)103(:=,T1，z)104 ( J,，107)105(+,x,y, T2)106(:=, T2，z)107八、（8分）给出算术表达式a+b*(c-d)+e/(c-d)的三元式、间接三元式、树、四元式表示。解：三元式间接三元式 间接码表 四元式(1) (-,c,d)(1) (-,c,d)(1) (1) (-,c,d,T1)(2) (*,b,(1)(2) (*,b,(1)(2) (2) (*,b, T1,T2)(3) (+,a,(2) (3) (+,a,(2) (3) (3) (+,a,T2,T3)(4) (-,c,d) (4) (/,e,(1) (1) (4) (-,c,d,T4)(5) (/,e,(4) (5) (+,(3),(4)(4) (5) (/,e, T4,T5)(6) (+,(3),(5) (5) (6) (+,T3, T5,T6)
