编译原理作业标准答案

1、编译原理 作业标准答案第一章 引 言一、解释下列各词源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序（结果程序）一般可由计算机直接执行。低级语言：机器语言和汇编语言。高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。翻译程序: 能够把某一种语言程序（源语言程序）改变成另一

2、种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言），然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。二、什么叫“遍”？指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。三、简述编译程序的基本过程的任务。编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分

3、5个阶段。词法分析：输入源程序，进行词法分析，输出单词符号。语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。优化：对中间代码进行优化处理。目标代码生成：把中间代码翻译成目标语言程序。四、编译程序与解释程序的区别？编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。五、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间

4、代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码、六、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。 第二章 高级语言及其语法描述一、P36 6、令文法为N ® D½NDD ® 0½1½2½¼½9 文法描述的语言L（G）是什么？ 给出句子34，568的最左推导和最右推导。解： L（G）=a½a为可带前导0的正整数或L（G）=（0½1½2½¼½9）+ 或

5、 L（G）=a½a为数字串 最左推导：NÞNDÞDDÞ3DÞ34NÞNDÞNDDÞDDDÞ5DDÞ56DÞ568最右推导：NÞNDÞN4ÞD4Þ34NÞNDÞN8ÞND8ÞN68ÞD68Þ5687、写出一个文法，使其语言是奇数集，且每个奇数是不以0开头。解：N ® C½AC½ABCC ® 1½3½5½7½9A

6、 ® 1½2½¼½9B ® B½BBB ® 0½A8、令文法为 E ® T½E+T½E-TT ® F½T*F½T/FF ® （E）½i 给出i+i*i，i*（i+i）的最左推导和最右推导。给出i+i+i，i+i*i的语法树。解：最左推导EÞE+TÞT+TÞF+TÞi+TÞi+T*FÞi+F*FÞi+i*FÞi+i*iEÞTÞT*

7、FÞF*FÞi*FÞi*(E)Þi*(E+T)Þi*(T+T)Þi*(F+T)Þi*(i+T)Þi*(i+F)Þi*(i+i)最右推导EÞE+TÞE+T*FÞE+T*iÞE+F*iÞE+i*iÞT+i*iÞF+i*iÞi+i*iEÞTÞT*FÞT*(E)ÞT*(E+T)ÞT*(E+F)ÞT*(E+i)ÞT*(T+i)ÞT*(F+i)ÞT*

8、(i+i)ÞF*(i+i)Þi*(i+i) 构造语法树 E 最左推导构造语法树 E + T E + T i T i i10、把下列文法改写为无二义的：S ® SS½（S）½（）解：改写后的文法S ® SA½（S）½（）A ® （S）½（） 第三章 词法分析一、P647、构造下列正规式相应的DFA M构造相应的NFA MYX 1（0½1）*101 Y5431X 1 （0½1）* 1 0 1 Y3221X45 1 e e 1 0 1 0½1 0 Y54321X 1 e

9、e 1 0 1 1构造转换矩阵表（用子集法） I I0 I1 S 0 1X 1,2,3 0 11,2,3 2,3 2,3,4 1 2 32,3 2,3 2,3,4 2 2 32,3,4 2,3,5 2,3,4 3 4 32,3,5 2,3 2,3,4,Y 4 2 52,3,4,Y 2,3,5 2,3,4 5 4 3由转换矩阵构造DFA M25 001 0 0 1 1 1 034 1 1 0 1 将DFA M最小化 将DFA M的状态划分为非终态集0,1,2,3,4和终态集5p=0，1，2，3，4，5对每一个子集及每一个aÎS进行考察；0，1，2，3，41=1，3，3，3，5Ë

10、;0，1，2，3，4对于输入1是可区别的，将0，1，2，3，4分为 0,1,2，3 和 4。pnew = 0,1,2，3，4，5对pnew 进行考察；0，1，2，30=-，2，2，4Ë0，1，2，3由于0结点不能接受输入的数字“0”，并不属于任何状态集，所以先将0结点区别出来,又由于3结点输入的数字“0”到达4结点，所以将3结点也区别出来3。将0，1,2，3 分为 0 ，1，2和 3pnew = 0，1,2，3，4，5对pnew 进行考察；1,20=2Ì1，2，1,21=3Í3则1，2不可划分合为一个状态，最终的结果是；pnew = 0，1,2，3，4，5。根据最

11、小化的结果构造矩阵表 旧名 0 1，2 3 4 5 新名 0 1 2 3 4 S 0 1 0 1 1 1 2 2 3 2 3 1 4 4 3 2 构造最小化的DFA M 0 1 143210 1 1 0 1 0 012将下图的有限自动机确定化和最小化 a a,b 01 a 该有限自动机输入同一字符a时到达两个不同的结点,所以是NFA。构造转换矩阵表（用子集法） I Ia Ib S a b 0 0，1 1 0 1 2 0，1 0，1 1 1 1 2 1 0 2 0 由转换矩阵构造DFA M1 a a0 b a2 b将DFA M最小化将DFA M的状态划分为非终态集2和终态集0，1p=2，0，1对

12、每一个子集及每一个aÎS进行考察；0，1A=1Ì0，10，1b=2，2Í2对于输入a和b均是不可区别的，所以pnew = 0,1，2根据最小化的结果构造矩阵表 旧名 0，1 2 S a b 新名 0 1 0 0 1 1 0 构造最小化的DFA M a 01 b a 二、P6514、构造一个DFA M，它接受å=0，1上所有满足如下条件的字符串：每个1都有0直接跟在右边。 写出正规集的正规式的表示形式 （0½10）* 构造相应的NFA MYX （0½10）* 1YX e e 0½10 0Y1X e e 1 0 2 构造转换矩阵

13、表（用子集法） I I0 I1 S 0 1 X，1，Y ！，Y 2 0 1 2 1，Y 1，Y 2 1 1 2 2 1，Y 2 1 由转换矩阵构造DFA M 1 021 0 1 0 0 将DFA M最小化 将DFA M的状态划分为非终态集2和终态集0，1p=2，0，1对每一个子集及每一个0，1ÎS进行考察；0，10=1Ì0，10，11=2，2Í2对于输入a和b均是不可区别的，所以pnew = 0,1，2根据最小化的结果构造矩阵表 旧名 0，1 2 S 0 1 新名 0 1 0 0 1 1 0 构造最小化的DFA M 0 10 1 0 第四章 语法分析-自上而下一、

14、用P76的文法写出表达式 (i+i)*i 的预测分析过程。 步骤 符号栈 输入串 所用的产生式 0 #E （i+i）*i# 1 #ET （i+i）*i# E®TE 2 #ETF （i+i）*i# T®FT 3 #ET）E（ （i+i）*i# F®（E） 4 #ET）E i+i）*i# 5 #ET）ET i+i）*i# E®TE 6 #ET）ETF i+i）*i# T®FT 7 #ET）ETi i+i）*i# F®i 8 #ET）ET +i）*i# 9 #ET）E +i）*i# T®e 10 #ET）ET+ +i）*i# E&

15、#174;+TE 11 #ET）ET i）*i# 12 #ET）ETF i）*i# T®FT 13 #ET）ETi i）*i# F®i 14 #ET）ET ）*i# 15 #ET）E ）*i# T®e 16 #ET） ）*i# E®e 18 #ET *i# 19 #ETF* *i# T®*FT 20 #ETF i# 21 #ETi i# F®i 22 #ET # 23 #E # T®e 24 # # E®e二、P811、 考虑下面文法GS® a½½（T） T®T，S½

16、;S消除文法的左递归。经改写后的文法是否是LL（1）的？给出它的预测分析表。解：经考察该文法S® a½½（T）的各侯选式的首字符都是终结符号，所以只有T®T，S½S是直接左递归。根据改写算法，改写后的文法是：S® a½½（T） T®STT®，ST½e 证明改写后的文法是否是LL（1）的.证明S® a½½（T）各侯选式的FIRST是否两两相交。 FIRST（a）ÇFIRST（）=fFIRST（a）ÇFIRST（）=fFIRST（）

17、9;FIRST（）=f证明T®，ST½e的FIRST（T）和FOLLOW（T）是否相交。 求FIRST（T）=，e FOLLOW（T）= ) FIRST（T）Ç FOLLOW（T）=，eÇ ) =f该文法是LL（1）的。构造预测分析表 a ， （ ） # S S® a S® S®（T） T T®ST T®ST T®ST T T®，ST T®e 2、下面的文法GE® TE E®+E½e T®FTT®T½eF®

18、PF F®*F½eP®（E）½½a½b计算这个文法的每个非终结符的FIRST和FOLLOW。证明这个文法是LL（1）的构造它的预测分析表。解：求非终结符的FIRST和FOLLOW。求非终结符的FIRST：因为E®+E½e，所以FIRST（E）=+， e因为F®*F½e，所以FIRST（F）=*， e因为P®（E）½½a½b，所以FIRST（P）=（， ， a， b 因为F®PF，所以FIRST（F）= FIRST（P）因为T®FT，所以

19、FIRST（T）=FIRST（F）因为E® TE，所以FIRST（E）= FIRST（T）因为T®T½e，所以FIRST（T）= FIRST（T）È e =（， ， a， b ，e求非终结符的FOLLOW：因为E® TE的E是文法的开始符号，FOLLOW（E）=#，又因为P®（E），所以FOLLOW（E）=#ÈFIRST（）e=#，)因为E® TE，所以FOLLOW（E）=FOLLOW（E）因为E® TE，并且Ee，所以FOLLOW（T）=FIRST（E）e,又因为E®e,所以FOLLOW（T）

20、=+È FOLLOW（E）=+È #,=+，#,) .因为T®FT，所以FOLLOW（T）=FOLLOW（T）=+，#,) .因为T® FT，并且Te，所以FOLLOW（F）=FIRST（T）e,又因为T®e,所以FOLLOW（F）=（，a，b È FOLLOW（T）=（，a，b È+，#,) =（，a，b ,+，#,) 因为F®PF，所以FOLLOW（F）=FOLLOW（F）=（，a，b ,+，#,) .因为F®PF，并且Fe，所以FOLLOW（P）=FIRST（F）e,又因为F®e,所以FO

21、LLOW（P）=*È FOLLOW（F）=*È（，a，b,+,）,# =*,（，a，b ,+，),# .证明这个文法是LL（1）的证明P®(E)½½a½b各侯选式的FIRST是否两两相交。 FIRST（(E)）ÇFIRST（）=fFIRST（(E)）ÇFIRST（a）=fFIRST（(E)）ÇFIRST（b）=f FIRST（）ÇFIRST（a）=fFIRST（）ÇFIRST（b）=fFIRST（a）ÇFIRST（b）=f证明E®+E½e,T®T

22、½e,F®*F½e非终结符号的FIRST和FOLLOW是否相交。FIRST（E）Ç FOLLOW（E）=+，eÇ#, ) =fFIRST（T）Ç FOLLOW（T）=（， ， a， b ，eÇ+，#,) =f FIRST（F）Ç FOLLOW（F）=*，eÇ（，a，b ,+，#,) =f该文法是LL（1）的。构造预测分析表 + * ( ) a b # E TE TE TE TE E +E e e T FT FT FT FT T e T e T T T e F PF PF PF PF F e *F e e

23、e e e e P (E) a b 第五章 语法分析-自上而下分析一、写出表达式（i+i）*i的LR分析过程（P101 LR分析表）。步骤 状态 符号 输入串 下一状态 1 0 # (i+i)*i# 4 2 04 #( i+i)*i# 5 3 045 #(i +i)*i# goto(4,F)=3 4 043 #(F +i)*i# goto(4,T)=2 5 042 #(T +i)*i# goto(4,E)=8 6 048 #(E +i)*i# 6 7 0486 #(E+ i)*i# 5 8 04865 #(E+i )*i# goto(6,F)=3 9 04863 #(E+F )*i# goto

24、(6,T)=9 10 04 #(E+T )*i# goto(4,E)=8 11 048 #(E )*i# 11 12 04811 #(E) *i# goto(0,F)=3 13 03 #F *i# goto(0,T)=2 14 02 #T *i# 7 15 027 #T* i# 5 16 0275 #T*i # goto(7,F)=10 17 02710 #T*F # goto(0,T)=2 18 02 #T # goto(0,E)=1 19 01 #E # 二、P133 1、 令文法为EE+T½T TT*F½F F（E）½i证明E+T*F是它的一个句型，指出这个

25、句型的所有短语，直接短语和句柄。证明输入串E+T*F是文法的一个句型，建立一个最右推导:EÞE+TÞE+T*F，E+T*F是该文法的句型。EE 且 EE+T*F所以，E+T*F是句型E+T*F+i对于E的一个短语。因为 EE+T 且 TÞT*F所以，T*F是句型E+T*F对于T®T*F的一个直接短语。句型E+T*F的短语为E+T*F，直接短语为T*F，由于直接短语是唯一的，因此T*F为句柄。三、P1345考虑文法SAS½b ASA½a 列出这个文法的所有LR（0）项目。构造这个文法的LR（0）项目规范族及识别活前缀的DFA。这个文法是

26、SLR（1）的吗？若是，构造出它的SLR分析表。解：构造拓广文法，并列出文法的所有项目SS S·S SS· SAS S·AS SA·S SAS·Sb S·b Sb· ASA A·SA AS·A ASA·Aa A·a Aa·构造这个文法的LR（0）项目规范族及识别活前缀的DFA。 A 0 2 5 4 A S A S b A S a a b b a a b b a a S S ASA·SS·ASS·bA·SAA·aS·S

27、S·ASS·bA·SAA·aSAS·AS·AA·SAA·aS·ASS·bASA·SA·SS·ASS·bA·SAA·aSS·AS·AA·SAA·aS·ASS·bAS·AA·SAA·aS·ASS·bS·bA·aS·ASS·bAa· 证明文法是SLR（1）的吗？为了验证这个文法是否是S

28、LR(1)文法，必须对LR(0)项目规范族的各个项目集I，验证其是否存在“移进归约”、“归约归约”冲突。该项目规范族中的I1,I4,I5存在“移进归约”，只需证明存在集合的ía,bý，FOLLOW(S)，FOLLOW(S)，FOLLOW(A)两两不相交。对此求出FOLLOW(S)íý，FOLLOW(S)í#,a,bý，FOLLOW(A)ía,bý。验证如下：对状态I1有FOLLOW(S)íý；A·a；S·b。因此FOLLOW(S)Çía,bý&#

29、237;ýÇía,býf，所以不存在“移进归约”冲突。对状态I4有FOLLOW(S)ía,bý；A·a；S·b。因此FOLLOW(A)Çía,bý=ía,býÇía,bý¹f，所以存在“移进归约”冲突。对状态I5也同样存在这种冲突，即FOLLOW(S)Çía,bý=í,a,býÇía,bý¹f，因此，该文法不是SLR(1)文法。四、P13

30、5 7、证明下面文法是SLR（1）担不是LR（0）的SA AAb½bBa BaAc½a½aAb证明：因为项目AAb·和BaAb·出现在一个项目集中，造成“归约-归”约冲突，所以不是LR（0）文法。又因为FOLLOW（A）=b，c，#，FOLLOW（B）=a使得FOLLOW（A）FOLLOW（B）=，构造SLR（1）分析表时不会出现冲突，所以该文法是SLR（1）的。五、对给定文法G，构造分析表，并利用此分析表判定符号串accd是否文法的句子？ (0)SE E aA E bB A cA Ad B cB B d解：该文法在P110，分析表在P109，

31、构造LR（0）的项目在P105（略）。构造LR（0）识别活前缀的DFA在P106（略）构造LR（0）分析表在P109（略）。利用LR（0）分析表判定符号串accd的分析过程： 状态栈 符号栈 输入串 动作 0 # accd# 开始 02 #a ccd# 移进 024 #ac cd# 移进0244 #acc d# 移进024410 #accd # 移进02448 #accA # 用Ad归约0248 #acA # 用AcA归约026 #aA # 用AcA归约01 #E # 用EaA归约第六章 属性文法和语法制导翻译思考题P164 1 第七章 语义分析和中间代码产生一、 P2185、把下列赋值语句翻

32、译为三地址代码序列,语义规则在P181： Ai，j:=Bi，j+CAK，i+Di+j解：求Ai，jLid (i) L.place:=id.place; L.offset:=null EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place := L.placeL.offset) end ElistidE (i) Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.placeLid (j) L.place:=id.place; L.o

33、ffset:=null EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place:=L.placeL.offset) end ElistElist,E (j) t:=newtemp; m:=Elist.ndim+1; emit(t := Elist.place * limit(Elist1.array,m) emit(t := t + E.place) Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;LElist L.p

34、lace:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emit(L.offset := w *Elist.place)求Bi,j的处理同Ai,j(省略中间过成) ElistidE (i) Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place ElistElist,E (j) t:=newtemp; m:=Elist.ndim+1; emit(t := Elist.place * limit(Elist1.array,m) emit(t := t + E.pl

35、ace) Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;LElist L.place:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emit(L.offset := w *Elist.place) EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place:=L.placeL.offset) end求AK，iElistidE (k) Elist.pl

36、ace:=E.place; Elist.ndim:=1; Elist.array:=id.place ElistElist,E (i) t:=newtemp; m:=Elist.ndim+1; emit(t := Elist.place * limit(Elist1.array,m) emit(t := t + E.place) Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;LElist L.place:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emi

37、t(L.offset := w *Elist.place)EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place:=L.placeL.offset) end求Di+jEE+E E.place:=newtemp; emit(E.place := E1.place + E2.place)ElistidE (i+j) Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place LElist L.place:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emit(L.offset := w *Elist.place)EL if L.offset=null then E.place:=L.