作业与学习05.doc

编译原理 学习与作业第一章 引论一、填空问题 由于计算机只能认识机器语言，所以需要翻译程序将高级语言翻译成计算机可以识别的机器语言。编译程序的工作过程一般主要划分为词法分析，语法分析，中间代码生成，代码优化，目标代码生成等几个基本阶段，同时还会伴有表格处理和出错处理。如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两个阶段：编译阶段和运行阶段。如果编译程序生成的目标程序是汇编语言的程序，则源程序的执行分为三个阶段：编译阶段，汇编阶段和运行阶段。二、判断问题高级语言程序必须经过编译程序的翻译才被计算机识别和执行。（ 错 ）答：对高级语言的翻译，还有解释程序。编译程序的输入是高级语言，输出是机器语言程序。（错）答：输出还有汇编语言程序。具有优化功能的编译程序的工作效率高。（错）答：优化是编译程序的的一部分，优化的目的，是提高目标程序的质量和运行效率。有的编译程序可以没有目标代码生成部分。（错）答：编译程序必须生成目标代码，所以目标代码生成部分是不可缺少的。 第二章 高级语言及其语法描述一、判断题 1、正规文法一定不是二义性的。（错）答：文法的二义性问题是不可避免和不可判定的，正规文法也可能存在二义性的问题。 2、文法的二义性和语言的二义性是两个不同的概念。（对） 答：可能有两个不同的文法G和G，其中G是二义性的，但是却有L（G）= L（G）。 3、一个句型对应的一棵语法树，包括了该句型的所有推导。（错）答：一棵语法树，只能对应一个推导，所以不能包括该句型的所有推导。二、选择题 1、文法G所描述的语言是 D 的集合。A、文法G的字汇表V中所有符号组成的符号串 B、文法G的字汇表V的闭包V*中的所有符号串C、由文法的开始符号推出的所有符号串D、由文法的开始符号推出的所有终结符号串三、解答题 1、设文法G ETE+TE-T TFT*FT/F F（E）I试给出关于（i）与（i+i）/i的推导。E T F （E）（T）（F）（i）ETT/FF/F（E）/F（E+T）/F（T+T）/F（F+T）/F（i+T）/F（i+F）/F（i+i）/F（i+i）/i证明E+T*F*i+i是该文法的句型。 EE+TE+T+TE+T*F+TE+T*F*F+TE+T*F*F+FE+T*F*F+iE+T*F*i+i因为存在上述推导序列，所以E+T*F*i+i是该文法的句型。2、试判断下述文法是否具有二义性： Ei（E）EAE A+-*/该文法是二义性文法，因为该文法给定的句子i+i+i，存在两棵不同的语法树。E E E A E E A E E A E + i i + E A E i + i i + i8、把下面的文法改写为无二义性的文法： SSS（S）（） 该文法产生二义性文法的原因就在于产生式SSS中左部符号在右部连续出现两次，使得对S既可以采用左递归得到（）（）（）又可以采用右递归得到（）（）（），为此改写文法为：SAS（S）（）A（S）（） 第三章 词法分析一、填空题1、编译过程中扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位单词。2、高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符以及界限符。3、确定的有限自动机是一个五元组，通常表示为DFA M=（S，S，d，S0，F）。4、词法分析的任务是输入源程序，输出单词符号。5、确定有限自动机DFA是NFA的一种特例。6、若二个正规式所表示的正规集相同，则认为二者是等价的。二、判断题1、一些语言，它们能被确定的有限自动机识别，但不能用正规表达式表示。（ 错 ）答：用正规式表示的语言，都能被确定的有限自动机识别。2、每一个NFA M都对应有唯一的一个最小化的DFA M。（ 对 ）答：每一个NFA M都可以构造一个DFA M，而DFA M又可以构造一个最小化的DFA M。3、一个有限自动机，仅有一个唯一的终态。（错）答：有限自动机的终态可以有多个。4、确定的有限自动机以及不确定的有限自动机都能正确识别正规集。（对）答：一个有限自动机能识别该正规式，所描述的语言（正规集）。5、对任意一个正规文法G，都存在一个DFA M，满足L（G）=L（M）。（对）答：对每一个正规文法G，都存在一个DFA M，使得L（G）=L（M）。三、选择题1、在词法分析中能识别出a，c，e。 a、关键字 b、四元式 c、运算符 d、逆波兰式 e、常数2、令=a，b，则上所有以b开头，后跟若干个ab的字的全体对应的正规式b，d。a、b（ab）* b、b（ab）+ c、（ba）*b d、（ba）+b e、b（ba）*3、词法分析所依据的是b。 a、语义规则 b、词法规则 c、语法规则 d、等价变换规则 4、正规式V1和V2等价是指c。a、V1和V2的状态数相等 b、V1和V2的有向弧条数相等c、V1和V2所识别的语言集相等 d、V1和V2状态数和有向弧条数相等5、令=a，b，正规式abc代表的正规集b。 a、b、， c、 d、，三、简答题 1、什么是扫描器？扫描器的功能是什么？ 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析使用。四、基本题1、设M=（x，y，a，b，d，x，y）为一个非确定有限自动机，其中d定义如下：d（x，a）=x，y d（x，b）=yd（y，a）=f d（y，b）=x，y试构造相应的确定的有限自动机(DFA M).解：根据d函数值，先构造NFA M aYX b b a b用子集法构造DFA M的转换矩阵表 I Ia Ib x 0 x，y 2 y 1 y 1 x，y 2 x，y 2 x，y 2 x，y 2 确定DFA M的初态和终态含有x状态子集为DFA M的初态结点，所以x=0初态结点。含有y状态子集为DFA M的终态结点，所以y=1，x，y=2为终态结点（因为DFA M只含有唯一的初态）。构造DFA M20 a1 b b a,bDFA M的最小化将DFA M划分成终态集1，2和非终态集0，采用后继状态等价性的依赖关系，构造DFA M的最小化。因为结点1和结点2输入的字符不同，结点1，2是可分割的，所以确定的有限自动机（DFA M）不需要化简。2、构造下列正规式相应的DFA M最小化 （10）*（1100）*D构造NFA M 1 1 1CZSAB e e e eE 0 0 0用子集法构造DFA M的转换矩阵表I I0 I1S，A，B，C，Z S A，B，C，E，Z A A，B，C，D，Z BA，B，C，E，Z A A，B，C，E，Z A A，B，C，D，Z BA，B，C，D，Z B A，B，C，E，Z A A，B，C，D，Z B 确定DFA M的初态和终态含有s，z状态子集为DFA M的初态和终态，即为S。含有z状态子集为DFA M的终态结点，即为A，B。构造DFA MA2 0 0S 1 0B1 1 1将DFA M最小化将DFA M划分成终态集和非终态集因为DFA M只有终态集，即S，A，B。采用后继状态等价性的依赖关系，构造DFA M的最小化。又因为输入0均到达A，输入1均到达B，所以S，A，B等价，化简后的DFA M。S 0，1第四章 语法分析自上而下分析一、填空题1、自上而下语法分析方法的基本思想是：从文法的开始符号出发。不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。2、自上而下语法分析方法会遇到的主要问题有回溯和左递归。3、在自上而下语法分析中，应先消除文法的间接左递归，再消除文法的直接左递归。4、在语法分析中，最常见的两种方法是自上而下分析法，另一种是自下而上分析法。二、选择题1、高级语言编译程序常用的语法分析方法中，递归下降分析法属于B分析方法。A、自左至右 B、自上而下 C、自下而上 D、自右至左三、解答题 1、已知文法G： AaAae该文法是LL（1）文法吗？为什么？若采用LL（1）方法进行分析，如何得到该文法的LL（1）分析表。若输入串“aaaa”，请给出语法分析过程。解：因为FOLLOW（A）FIRST（a）=a，# 造成FOLLOW（A）FIRST（A）=a，#a，ef 所以该文法不是LL（1）文法。若采用ll（1）方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为0）个a，所以得到文法G：AaaAe。此时 FOLLOW（A）=#，因此FOLLOW（A）FIRST（A）=#a，e=f所以文法G是LL（1）文法，该文法的ll（1）分析表：VTVN a # A AaaA Ae 对符号串“aaaa”的分析过程： 步骤 分析栈 输入串 产生式/动作 1 #A aaaa# AaaA 2 #Aaa aaaa# 匹配 3 #Aa aaa# 匹配 4 #A aa# AaaA 5 #Aaa aa# 匹配 6 #Aa a# 匹配 7 #A # Ae 8 # # 接受 2、设文法G：SSbAaABScABc将此文法改写为LL（1）文法。求文法的每一个非终结符号的FIRST集合和FOLLOW集合。构造相应的LL（1）分析表。解：改写文法为LL（1）文法 SaASSbASeBScABc构造文法每一个非终结符号FIRST和FOLLOW的集合。a、构造文法每一个非终结符号FIRST的集合 FIRST（S）=a FIRST（S）=b，e FIRST（B）=a FIRST（A）=ab、构造文法每一个非终结符号FOLLOW的集合因为SaAS和BSc，所以 FOLLOW（S）=#FIRST（c）=#，c因为SaAS，所以FOLLOW（S）= FOLLOW（S）=#，c因为SaAS，所以FOLLOW（A）= FOLLOW（A）FIRST(S)e =b又因为Se,并且FOLLOW（S）=FOLLOW（S），最终结果FOLLOW（A）= FOLLOW（A）FOLLOW(S)=#，c,b。因为ABc，所以 FOLLOW(B)=FOLLOW（B）FIRST（c）=c判定该文法是否是LL（1）文法因为文法中只含有一个多后选式的定义式SbASe，只需证明：FIRST（S）Follow（S）=b，e#，c,=f，该文法是LL（1）文法。构造相应的LL（1）分析表 因为 FIRST（S）=a，所以MS，a= SaAS；因为 FIRST（S）=b，e，所以MS，b= SbAS，又因为eFIRST（S），则对b，#FOLLOW（S），使得MS，b= Se，MS，#= Se； 因为FIRST（B）=a，所以MB，a= BSc；因为FIRST（A）=a，所以MA，a= ABc。 a b c # S SaAS S SbAS Se Se A ABc BBSc 第五章 语法分析自下而上分析一、填空题 对于一文法，如果能够构造一张分析表，使得它的每一个入口均是唯一确定的，则称该文法为LR文法。自下而上语法分析法的基本思想是：从待输入的符号串开始，利用文法的产生式步步向上进行直接归约，试图归约到文法的开始符号（识别符号）。字的活前缀是指该字的任意首部。活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何句型。二、选择题若a为终结符，则Aaab为B项目。 A、归约 B、移进 C、接受 D、待约一个LR分析器包括A、D。 A、一个总控程序 B、一个项目集 C、一个活前缀 D、一张分析表 E、一个分析栈对LR分析表的构造，有可能存在C、E动作冲突。 A、归约 B、移进 C、移进-归约 D、移进-移进 E、归约-归约自上而下的语法分析方法A、C、D、E有。A、算符优先分析法 B、LL（1）分析法 C、LR（0）分析法 D、SLR（1）分析法E、LALR（1）分析法每一项ACTIONs，a所规定的动作包括A、C、D、E。A、归约 B、比较 C、移进 D、接受 E、报错四、解答题考虑文法G SBB BaBb列出这个文法的所有LR（0）项目；构造这个文法的LR（0）项目及识别活前缀的DFA；若是LR（0）文法，构造LR（0）分析表。解答：将文法G拓广为文法G及LR（0）的项目集规范族：0、SS SS SS 1、SBB SBB SBB SBB2、BaB BaB BaB BaB3、Bb Bb Bb用e-CLOSURE办法构造文法G的LR（0）项目集规范族：I0：SS I1：SS I3：BaB I5：BaBSBB I2：SBB BaB I6：BbBaB BaB BbBb Bb I4：Bb根据转换函数GO构造出G的DFA。 I0: SSSBB BaBEbI1: SS S I5: SBB I2: SBBBaBBb B B A bI3: BaB BaB Bb a bI4: Bb a B bI6: BaB构造LR（0）的分析表 状 ACTION GOTO 态 a b # S B 0 S3 S4 1 2 1 acc 2 S3 S4 5 3 S3 S4 6 4 r3 r3 r3 5 r1 r1 r1 6 r2 r2 r2 已知文法G SaSbSa构造该文法的项目；构造识别活前缀的DFA；判断该文法是否是SLR（1）文法，并构造其SLR分析表。解：将文法G拓广为G及构造LR（0）项目：0、SS SS SS 1、SaS SaS SaS SaS2、SbS SbS BbS BbS3、Sa Sa Ba 构造识别活前缀的DFAI1: SaS SaS SbS Sa Sa I4: SaS S a a bI0: SSSaS SbSSa I3: SS a S I2: SbSSaSSbs Sa I5: SbS B S b构造其SLR分析表在I1项目集中存在移进-归约冲突，求FOLLOW（S）=#证明：a，bFOLLOW（S）=a，b#=f，所以是SLR（1）文法（或判定分析表中是否有冲突项）。其分析表为： 状 ACTION GOTO 态 a b # S 0 S1 S2 3 1 S1 S2 r3 4 2 S1 S2 5 3 acc 4 r1 5 r2 第七章 语义分析和中间代码生成一、填空题1、所谓语法制导翻译，是指在语法规则的制导下，通过计算语义规则，完成输入符号的翻译，即每当使用语法规则进行推导或归约的同时，就是用与其相关的语义规则来进行翻译。2、编译过程中，常见的中间语言形式有逆波兰式表示、三地址代码（三元式、四元式）和图形表示。3、语法制导翻译即可以用来产生中间代码，也可以产生目标指令，甚至可用来对输入串进行解释执行。二、选择题1、中间代码生成时所依据的是C。A、语法规则 B、词法规则C、语义规则 D、等价变换规则2、终结符具有D属性。A、传递 B、继承 C、抽象 D、综合3、在下面的语法制导翻译B、C、D、E中，采用拉练-回填技术。A、赋值语句 B、布尔表达式的短路计算 C、GOTO语句D、条件语句 E、循环语句4、在编译程序中安排中间代码生成的目的是B、D。A、便于进行存储空间的组织 B、利于目标代码的优化C、利于编译程序的移植 D、利于目标代码的移植三、判断题1、 一个语义子程序描述了一个文法所对应的翻译工作。（错）答：一个语义子程序描述了一个产生式对应的翻译工作。2、 程序中的表达式语句在语义翻译时不许要回填技术。（对）答：表达式语句在语义翻译时程序结构是顺序结构。3、 对任何一个编译程序来说，产生中间代码是不可缺少的。（错）答：有的编译程序对目标程序不许要优化，可以直接生成目标程序。四、解答题1、什么是语法制导翻译？在分析过程中，每当需要使用一个产生式进行归约时，语法分析程序除执行相应的语法分析动作之外，还要执行相应的语义动作或调用相应的语义子程序。2、什么是语义子程序？语义子程序描述了一定的输入和一定的输出之间的对应关系。3、设某语言的WHILE语句的语法形式为：Swhile E do S（1）其语义解释如图所示。E的代码 假 真S（1）的代码 写出适合语法制导翻译的产生式。写出每个产生式对应的语义动作。解：改写后的产生式如下： WwhileAW E doSA S（1）每个产生式对应的语义子程序如下：Wwhile W.QUAD:=NXQ;AW E do BACKPATCH(E.TC，NXQ);B.CHAIN:=E.FC;A.QUAD:=W.QUADSA S（1） BACKPATCH(S（1）.CHAIN，A.QUAD); GEN(j，_，_，A.QUAD); S.CHAIN:=A.CHAIN;4、用7.5.1节的办法，把下列语句翻译成四元式序列：while ab do if cd then x:=y+z While M1 E do M2 S1 if E then M S1 翻译过程：M1 M1.quad:=100 Eid1 relop id2 (ab) E.t:=100, E.f:=101; 100(j,a,b,0 )102 101(j,_,_, 0 )107M2 M2.quad:=102 Eid1 relop id2 (cd) E.t:=102, E.f:=103; 102(j,c,d,0 )104 103(j,_,_, 0 )100M M.quad:=104 EE1 + E2 (x:=y+z)104 (+, Y, Z, T1) 105 (:=,T1, _, x)SA S.nextlist:=null Sif E then M S1 backpatch(102,104) S.nextlist:=merge(103,null)=103 SWhile M1 E do M2 S1 backpatch(103,100); backpatch(100,102); S.nextlist=101 106(j,_,_,100)LS backpatch(101,107)上述四元式如下:100(j,a,b,102)101(j,_,_, 107)102(j,c,d,104)103(j,_,_, 100)104(+, Y, Z, T1)105(:=, T1, _,x)106(j ,_, _, 100)107编译原理作业解析第一章 引 言一、解释下列各词源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序（结果程序）一般可由计算机直接执行。低级语言：机器语言和汇编语言。高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言），然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。汇编程序: 是把汇编语言编写的程序翻译成机器指令序列的过程。宿主机:运行编译程序的计算机。目标机:运行编译程序所产生目标代码的计算机.交叉编译: 如果一个编译程序产生不同于其宿主机的机器代码。二、什么叫“遍”？指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。三、简述编译程序的基本过程的任务。编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。词法分析：输入源程序，进行词法分析，输出单词符号。语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。优化：对中间代码进行优化处理。目标代码生成：把中间代码翻译成目标语言程序。四、编译程序与解释程序的区别？编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。五、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码、六、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。 第二章 高级语言及其语法描述一、P36 6、令文法为N DNDD 0129 文法描述的语言L（G）是什么？ 给出句子34，568的最左推导和最右推导。解： L（G）=aa为可带前导0的正整数或L（G）=（0129）+ 或 L（G）=aa为数字串 最左推导：NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN4D434NNDN8ND8N68D685687、写出一个文法，使其语言是奇数集，且每个奇数是不以0开头。解：N CACABCC 13579A 129B BBBB 0A8、令文法为 E TE+TE-TT FT*FT/FF （E）i 给出i+i*i，i*（i+i）的最左推导和最右推导。给出i+i+i，i+i*i的语法树。解：最左推导EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEE+TT+TF+Ti+Ti+Fi+（E）i+（T*F） i+（F*F）i+（i*F）i+（i*i）最右推导EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iEE+TE+FE+（E）E+（T*F）E+（T*i）E+（F*i）E+（i*i）T+（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（01）*101 Y5431X 1 （01）* 1 0 1 Y3221X45 1 e e 1 0 1 01 0 Y54321X 1 e 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对每一个子集及每一个aS进行考察；0，1，2，3，41=1，3，3，3，50，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，40，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=21，2，1,21=33则1，2不可划分合为一个状态，最终的结果是；pnew = 0，1,2，3，4，5。根据最小化的结果构造矩阵表 旧名 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将下图的有限自