编译原理简答(12页).doc

-编译原理简答-第 12 页1、给出算符优先文法的定义，算符优先表是否都存在对应的优先函数？给出优先函数的定义。设有一不含产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有、和h三种关系的一种成立，则称G一个算符优先文法。算符优先关系表不一定存在对应的优先函数优先函数为文法字汇表中2、考虑文法GT：TT*F|FFFP|PP（T）|i证明T*P（T*F）是该文法的一个句型，并指出直接短语和句柄。首先构造T*P（T*F）的语法树如图所示。句型T*P（T*F）的语法树 由图可知，T*P（T*F）是文法GT的一个句型。直接短语有两个，即P和T*F；句柄为P。3、文法GS为：SSdT | TTT<G | GG(S) | a试给出句型(SdG)<a的短语、简单(直接)短语、句柄和最左素短语。句型(SdG)<a的短语：(SdG)<a 、（SdG） 、SdG 、G 、a简单(直接)短语：G 、a句柄：G最左素短语：SdG4、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？三种形式：可立刻执行的机器语言代码；汇编语言程序；待装配的机器语言代码模块考虑的问题包括：每一个语法成分的语义；目标代码中需要哪些信息，怎样截取这些信息。5、符号表的作用是什么？符号表的查找的整理技术有哪几种?作用：登记源程序中出现的各种名字及其信息，以及编译各阶段的进展状况。主要技术：线性表，对折查找与二叉树，杂凑技术。1、实现高级语言程序的途径有哪几种？它们之间的区别？计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序并不对高级语言进行彻底的翻译，而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再执行。在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码，然后再对目标代码进行优化，即对源程序的处理是先翻译后执行。从速度上看，编译方式下，源程序的执行比解释方式下快，但在解释方式下，有利于程序的调试。2、文法GS为： S->Ac|aB A->ab B->bc 该文法是否为二义的？为什么？对于串abc (1)S=>Ac=>abc (2)S=>aB=>abc 即存在两不同的最右推导 所以，该文法是二义的。3、将文法GS 改写为等价的G'S，使G'S不含左递归和左公共因子。GS： SSAe|Ae AdAbA|dA|d文法GS 改写为等价的不含左递归和左公共因子的G'S为： S AeS'S' AeS'|A dA' A' AB|B bA |4、证明LL(1)文法是无二义性文法证明：LL（1）文法中任意两个产生式Pi，Pj，（Pi，Pj具有相同的左部非终极符）         Predict(Pi) Predict(Pj) 为空        设 Pi: A12n         Pj: A1121m1        (AVN, 12n, 1121m1 VNVT)         因为Predict(Pi) Predict(Pj) 为空，因此 Pi，Pj中的A经一步推导，        最左的终极符肯定不同，因此，对于一个字符串，不可能有两种方法推导。5、文法GS为： S->Ac|aB A->ab B->bc 写出L(GS)的全部元素S=>Ac=>abc 或S=>aB=>abc 所以L(GS)=abc 1、解释什么是推导？我们称A直接推出，即AT，仅当A 是一个产生式，且、(VNVT)*。如果12n，则我们称这个序列是从1至2的一个推导。若存在一个从1n的推导，则称1可推导出n。推导是归约的逆过程。2、将文法GS 改写为等价的GS，使GS不含左递归和左公共因子。GS： SbSAe | bA AAb | d文法GS 改写为等价的不含左递归和左公共因子的G'S为：SbB BSAe | AAd A' A' bA' | 3、写出Pascal 或C语言的字母表。pascal语言的字母表是：0，1，9a，zA，Z+，-，*，/，?，?，_， (，)，;，:，=，<，>，'，"，Enter，Space，TabC语言的字母表是：_, 09, az, AZ, +, -, *, /, , %, (, ), , , ., &, |, ！, =, #, , , , ”, ?, :，<，>， Enter，Space，Tab4、有文法GZ：ZaZbZ|aZ|a 该文法是否是二义的，试证明之。对于句子aaaba，画出二棵不同的语法树，因而是二义的。5、LL （ 1 ）分析法对文法有哪些要求？LL(1)分析法对文法的要求是：对于G的每个非终结符A的任何两个不同产生式A->|，有下述条件成立： First() First()= 若=*>，则First()Follow(A)=1、解释编译程序中“遍”的概念，何谓“单遍扫描”？遍指编译程序对源程序或中间代码程序从头到尾扫描一次对于源程序或中间代码程序，从头到尾扫描一次并完成所规定的工作称为一遍。单遍扫描是编译程序的一种极端情形。在这种情形下，整个编译程序同时驻留在内存中，编译程序的各部门之间采用“调用转接”方式连接在一起。2、设有文法GS为：Sa|b|(A)ASdA|S给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。短语：S，SdS，SdSdS，（SdSdS）简单短语（即直接短语）：S句柄（即最左直接短语）：S素短语：SdS，它同时也是该句型的最左素短语。图5-7-3句型（SdSdS）的语法树3、写出表达式A+B*（C-D）+E/（C-D）*N的逆波兰表示及三元式序列。(1)（_, C,D）(2) (*,B,(1)(3) (+,A,(2)(4) (_,C,D)(5) (/,E,(4)(6) (*,N,(5)(7)(+,(3),(6)4、画出编译程序的总体结构图。编译程序的总框图见下图。5、给出0，1，2，3型文法的定义。乔姆斯基(chomsky)把文法分成类型，即0型，1型，2型和3型，0型强于1型，1型强于2型，2型强于3型。 如果它的每个产生式->的结构是（VnUVt）*且至少含有一个非终结符,而（VnUVt）*，我们说G=（Vt，VN，S，）是一个0型文法。 0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵(Tunring)机。或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。 如果把0型文法分别加上以下的第i条限制，则我们就得i型文法为： 1G的任何产生式-> 均满足|<=|；仅仅S->例外，但S不得出现在任何产生式的右部。 2G的任何产生式为A->，AVn，（VnUVt）* 3G的任何产生式为A->aB或A->a，其中A，BVn 1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，般不允许替换成空串。 2型文法对非终结符进行替换时无须考虑上下文， 3型文法也称线性文法。 1、什么是规范推导？每个句型都有规范推导吗？规范推导就是最右推导每一个句子都有一个规范推导，而每一个句型则不一定都有规范推导，比如说采用非规范推导得到的句型。2、已知文法GE: EET+|T TTF* | F FF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄。该句型对应的语法树如下：该句型相对于E的短语有FF*；相对于T的短语有FF*,F;相对于F的短语有F;F;简单短语有F;F;句柄为F. 3、写出表达式w+(a+b)*(c+d/(e-10)+8)的逆波兰表示及三元式序列。(1)（+,a,b）(2) (-,e,10)(3) (/,d,(2)(4) (+,c,(3)(5) (+,(4),8)(6) (*,(1),(5)(7) (+,w,(6)4、何谓优化？按所涉及的程序范围可分为哪几级优化？所谓优化，一般是指为提高目标程序的质量而进行的各项工作，即对程序或中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 在源程序级 在语义动作的设计上 在中间代码级 在目标代码级5、简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。1、计算机执行用高级语言编写的程序有那些途径？它们之间的主要区别是什么？计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序并不对高级语言进行彻底的翻译，而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再执行。在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码，然后再对目标代码进行优化，即对源程序的处理是先翻译后执行。从速度上看，编译方式下，源程序的执行比解释方式下快，但在解释方式下，有利于程序的调试。2、编译程序的实现途径有那些？编译程序的实现途径可有：- 手工构造：用机器语言、汇编语言或高级程序设计语言书写。- 自动构造工具：Lex,Yacc。 Lex ,Yacc分别是词法和语法分析器的生成器。 - 移植方式：目标程序用中间语言 - 自展方式：用T型图表示 3、文法GE为： EE+T|T TT*F|F F(E)|i 试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。短语有: (E+F)*i ，(E+F) ，E+F ，F ，i 简单(直接)短语有: F ，i 句柄是: F 最左素短语是: E+F4、有人认为：“1型文法对规则的限制比2型文法对规则的限制要多一些”，这种说法对吗？文法是严格按照规则的形式来分类的1型文法的规则是：xUy->xuy uVn uV+ x,yV*要求将U替换为u时，U的前后一定要有x和y。而2型文法的规则形式为U->u uVn uV*没有什么要求，似乎1型的规则限制要多一些。但仔细看看1型规则中的条件x和y时，就不难发现当x和y为空时，正好是2型文法。从0型文法到3型文法，是依次增加对文法的限制，所以描述的语言集合越来越小。5、简述自底向上分析法。基本思想是：从待输入的符号串开始，利用文法的规则步步向上归约，试图归约到文法的识别符号。从语法树的角度看，自底向上分析的过程是以输入符号串作为末端结点符号串，向着根结点方向往上构造语法树，使识别符号正好是该语法树的根结点。如果最终根结点是识别符号，则输入符号串被识别是相应语言的一个句子；否则不是。 自底向上分析过程实际上是一个不断进行直接归约的过程。1. 对如下文法：GS：SàabS|aaB|adBàbbB|b分别给出句子abaabbb和ad的句柄（6分）句子abaabbb的句柄是b；句子ad的句柄是ad2. 什么是可规约活前缀？举一例说明。（6分）若活前缀是含句柄的活前缀，即有 = ,且是句柄，则活前缀为可归约活前缀。例 S à a | b C dCà e则be为一个可归约活前缀3.写出表达式(ab*c)/(ab)d的逆波兰表示及三元式序列或P代码。（6分）(1)（*,b,c）(2) (+,a,(1)(3) (+,a,b)(4) (/,(2),(3)(5) (-,(4),d)4.词法分析和语法分析都是对字符串进行识别，二者有何区别？（4分）在词法分析和语法分析中，都是对输入符号串进行识别。但词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子或者说是一个程序。为了讨论方便，我们都是用小写字母来表示终结符号，但一定要明白在词法分析中小写字母表示组成单词的字符，而在语法分析中小写字母表示组成程序的的一个单词，识别方式来说，词法分析和语法分析都是对输入符号串结构的识别，但由于单词和程序的结构有所区别，所以具体的识别方式不一样。5.已知文法GS为： Sa|(T) TT,S|S判断该文法是否是算符优先文法？如是，请给出算符优先关系表。（8分）(1) FIRSTVT和LASTVT   FIRSTVT LASTVT S a、（ a、） T ，、a、（ ，、a、) (2) 算符优先关系   a ( ) , # a       (     )       ,         #       1、语法分析的主要（功能）任务是什么？有哪二种分析分方法？语法分析的主要任务是对词法分析的输出结果-单词序列进行分析，识别合法的 语法单位。若给定的输入符号是该文法所产生的语言中的句子，就给出它的语法树，否则就报告出错信息。自上而下语法分析和自下而上语法分析。2、令文法G为Sa|(T)TT,S|S（1）给出(a,(a,a)的最右推导和最左推导。（2）画出语法分析树最左推导：S=>(T) =>(T,S) =>(a,S)=>(a,(T,S) =>(a,(S,S)=>(a,(a,S)=>(a,(a,a)最右推导：S=>(T)=>(T,S)=>(T,(T)=>(T,(T,S) =>(T,(T,a)=>(T,(S,a)=>(T,(a,a) =>(S,(a,a)=>(a,(a,a)3、写出表达式A=（a+b）+（c+d）*（x+y+c）的三元式序列或P代码表示。(1)（+,a,b）(2) (+,c,d)(3) (+,x,y)(4) (+,(3),c)(5) (*,(2),(4)(6) (+,(1),(5)4、什么是二义性文法？请举例说明。一个文法如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性，如果一个文法含有二义性的句子，则称此文法具有二义性。例： Eài | (E) | EAE Aà + | - | * | /i+i+iEEE A EE A EEA E t I i t E A Ei t i i t i5、在一个基本块内通常可实现哪些优化？合并已知量 删除公共子表达式 删除无用代码 复写传播1、DFA和NFA有何区别？DFA和NFA的区别表现在三个方面。一是NFA可有若干个开始状态，而DFA仅有一个。二是DFA的映像M是从K到K，而的映象M是从K到K的子集，即映像M将产生一个状态集合（可能为空集），而不单个状态。三是NFA在没有扫描输入符号的情况下，也可以进行空移。2、已知文法G为：S aAcB|BdA AaB|cB bScA|b写出句子acabcbbdcc得最左推导及语法树s->aAcB->aAaBcB->aCaBcB->acabcB->acabcbScA->acabcbBCCA->acabcbbdcc Sa A c B A a B b S c A C b B d b3、写出表达式A=（x+y）*（c+d）+（x+y+c）的四元式序列或P代码表示。(1)（+,x,y）(2) (+,c,d)(3) (*,(1),(2)(4) (+,x,y)(5) (+,(4),c)(6) (+,(3),(5)4、什么是语法树?满足下面4个条件的树称之为文法GS的一棵语法树。每一终结均有一标记，此标记为VNVT中的一个符号；树的根结点以文法GS的开始符S标记；若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,Xk，则AX1,X2,Xk， 必然是G的一个产生式。5、在编译过程中为什么要建立符号表，简述符号表的组织，即它一般分成几部分，含有那些域？在编译过程中，始终涉及到对一些语法符号的处理，需要用到这些语法符号的相关属性。为了在需要的时候能找到这些语法成分及其相关属性，必须使用一些表格保存这些语法成分及其属性，这些表格就是符号表。符号表应包括语法符号的名字和相关属性，不同语法符号在符号表中存放的信息不同。符号表的条目一般由两部分组成，即名字栏和信息栏。符号表域包括标识符名、其他信息、地址等。对名字栏，为节省空间，可另外设立一个存放标识符的字符数组。对信息栏中的类型等信息可以用数值或向量来表示，以节省空间1、简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树的角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。2、设有文法GA的产生式集为: ABaC|CbB BAc|c CBb|b 试消除GA的左递归。    提示：不妨以A、B、C排序.先将A代入B中，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。 最后结果为:GA: ABaC|CbB BCbBcB'|cB' B'aCcB'| CcB'bC'|bC' C'bBcB'bC'|3、写出表达式a+b*(c-d)+e/(c-d)*n的三元式序列或P代码表示。(1)（_,c,d）(2) (*,b,(1)(3) (+,a,(2)(4) (_,c,d)(5) (/,e,(4)(6) (*,n,(5)(7)(+,(3),(6)4、什么样的文法是算符优先文法，请举个算符优先文法的例子。设文法G，如果它的产生式右部不包含相邻非终结符号，则称文法G为算符文法，如果算符文法的终结符号集中任意两个符号之间至多存在一种优先关系，则称该算符文法为算符优先文法。例如：E->E+T|TT->T*F|FF->(E)|i+*()i+><<><*>><><(<<<=<)>>>i>>>5、解释什么是归约？我们称直接归约出A，仅当A 是一个产生式， 且、(VNVT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。1.什么是算符优先文法？给出一个非教材上提供的算符优先文法的例子，并给出算符优先表？（6分）设文法G，如果它的产生式右部不包含相邻非终结符号，则称文法G为算符文法，如果算符文法的终结符号集中任意两个符号之间至多存在一种优先关系，则称该算符文法为算符优先文法。例如：E->E+T|TT->T*F|FF->(E)|i+*()i+><<><*>><><(<<<=<)>>>i>>>2.设有文法GS：Sàa|(T)TàT,S|S请给出句子(a,(a,a)的最左和最右推导，给出该句子的短语和句柄。（7分）最左推导：S=>(T) =>(T,S) =>(a,S)=>(a,(T,S) =>(a,(S,S)=>(a,(a,S)=>(a,(a,a)最右推导：S=>(T)=>(T,S)=>(T,(T)=>(T,(T,S) =>(T,(T,a)=>(T,(S,a)=>(T,(a,a) =>(S,(a,a)=>(a,(a,a)3. 编译程序的实现应考虑的问题有那些？（4分）编译程序的实现 应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护性、可扩充性等。4.什么是二义性文法？请用例说明文法GE：Eài | (E) | EAE Aà + | - | * | /是二义性文法。（6分）一个文法如果它的一个句子有两棵或两棵以上的语法树，则称该句子具有二义性，如果一个文法含有二义性的句子，则该文法是二义性文法。如句子：i+i+i5.在编译过程中为什么要建立符号表？简述符号表的组织，即它一般分成几部分，含有那些域？（6分）在编译过程中，始终涉及到对一些语法符号的处理，需要用到这些语法符号的相关属性。为了在需要的时候能找到这些语法成分及其相关属性，必须使用一些表格保存这些语法成分及其属性，这些表格就是符号表。符号表应包括语法符号的名字和相关属性，不同语法符号在符号表中存放的信息不同。符号表的条目一般由两部分组成，即名字栏和信息栏。符号表域包括标识符名、其他信息、地址等。对名字栏，为节省空间，可另外设立一个存放标识符的字符数组。对信息栏中的类型等信息可以用数值或向量来表示，以节省空间