编译原理简答

1、给出算符优先文法的定义，算符优先表是否都存在对应的优先函数？给出优先函数的定义。设有一不含ε产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有、和h三种关系的一种成立，则称G一个算符优先文法。算符优先关系表不一定存在对应的优先函数优先函数为文法字汇表中2、考虑文法G[T]：T→T*F|FF→F↑P|PP→（T）|i证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。首先构造T*P↑（T*F）的语法树如图所示。句型T*P↑（T*F）的语法树由图可知，T*P↑（T*F）是文法G[T]的一个句型。直接短语有两个，即P和T*F；句柄为P。3、文法G[S]为：S→SdT|TT→TG|GG→(S)|a试给出句型(SdG)a的短语、简单(直接)短语、句柄和最左素短语。句型(SdG)a的短语：(SdG)a、（SdG）、SdG、G、a简单(直接)短语：G、a句柄：G最左素短语：SdG4、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？三种形式：可立刻执行的机器语言代码；汇编语言程序；待装配的机器语言代码模块考虑的问题包括：每一个语法成分的语义；目标代码中需要哪些信息，怎样截取这些信息。5、符号表的作用是什么？符号表的查找的整理技术有哪几种?作用：登记源程序中出现的各种名字及其信息，以及编译各阶段的进展状况。主要技术：线性表，对折查找与二叉树，杂凑技术。1、实现高级语言程序的途径有哪几种？它们之间的区别？计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序并不对高级语言进行彻底的翻译，而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再执行。在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码，然后再对目标代码进行优化，即对源程序的处理是先翻译后执行。从速度上看，编译方式下，源程序的执行比解释方式下快，但在解释方式下，有利于程序的调试。2、文法G[S]为：S-Ac|aBA-abB-bc该文法是否为二义的？为什么？对于串abc(1)S=Ac=abc(2)S=aB=abc即存在两不同的最右推导所以，该文法是二义的。3、将文法G[S]改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。G[S]：S→SAe|AeA→dAbA|dA|d文法G[S]改写为等价的不含左递归和左公共因子的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:A→α1α2…αnPj:A→α11α21…αm1(A∈VN,α1α2…αn,α11α21…αm1∈VN∪VT)因为Predict(Pi)∩Predict(Pj)为空，因此Pi，Pj中的A经一步推导，最左的终极符肯定不同，因此，对于一个字符串，不可能有两种方法推导。5、文法G[S]为：S-Ac|aBA-abB-bc写出L(G[S])的全部元素S=Ac=abc或S=aB=abc所以L(G[S])={abc}1、解释什么是推导？我们称αAβ直接推出αγβ，即αAβTαγβ，仅当A→γ是一个产生式，且α、β∈(VN∪VT)*。如果α1α2…αn，则我们称这个序列是从α1至α2的一个推导。若存在一个从α1αn的推导，则称α1可推导出αn。推导是归约的逆过程。2、将文法G[S]改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe|bAA→Ab|d文法G[S]改写为等价的不含左递归和左公共因子的G'[S]为：S→bBB→SAe|AA→dA'A'→bA'|ε3、写出Pascal或C语言的字母表。pascal语言的字母表是：{0，1，……，9}∪{a，……，z}∪{A，……，Z}∪{+，-，*，/，\，↑，?，?，_，(，)，[，]，;，:，=，，，'，，Enter，Space，Tab}C语言的字母表是：_,0……9,a……z,A……Z,+,-,*,/,\,%,(,),[,],.,&,|,！,=,#,{,},’,”,?,:，，，Enter，Space，Tab4、有文法G[Z]：Z→aZbZ|aZ|a该文法是否是二义的，试证明之。对于句子aaaba，画出二棵不同的语法树，因而是二义的。5、LL（1）分析法对文法有哪些要求？LL(1)分析法对文法的要求是：对于G的每个非终结符A的任何两个不同产生式A-α|β，有下述条件成立：First(α)∩First(β)=Ф若β=*ε，则First(α)Follow(A)=Ф1、解释编译程序中“遍”的概念，何谓“单遍扫描”？遍指编译程序对源程序或中间代码程序从头到尾扫描一次对于源程序或中间代码程序，从头到尾扫描一次并完成所规定的工作称为一遍。单遍扫描是编译程序的一种极端情形。在这种情形下，整个编译程序同时驻留在内存中，编译程序的各部门之间采用“调用转接”方式连接在一起。2、设有文法G[S]为：S→a|b|(A)A→SdA|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型文法为：1．G的任何产生式α-β均满足|α|=|β|；仅仅S-ε例外，但S不得出现在任何产生式的右部。2．G的任何产生式为A-β，A∈Vn，β∈（VnUVt）*3．G的任何产生式为A-aB或A-a，其中A，B∈Vn1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，—般不允许替换成空串。2型文法对非终结符进行替换时无须考虑上下文，3型文法也称线性文法。1、什么是规范推导？每个句型都有规范推导吗？规范推导就是最右推导每一个句子都有一个规范推导，而每一个句型则不一定都有规范推导，比如说采用非规范推导得到的句型。2、已知文法G[E]:E→ET+|TT→TF*|FF→F^|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、文法G[E]为：E→E+T|TT→T*F|FF→(E)|i试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。短语有:(E+F)*i，(E+F)，E+F，F，i简单(直接)短语有:F，i句柄是:F最左素短语是:E+F4、有人认为：“1型文法对规则的限制比2型文法对规则的限制要多一些”，这种说法对吗？文法是严格按照规则的形式来分类的1型文法的规则是：xUy-xuyu∈Vnu∈V+x,y∈V*要求将U替换为u时，U的前后一定要有x和y。而2型文法的规则形式为U-uu∈Vnu∈V*没有什么要求，似乎1型的规则限制要多一些。但仔细看看1型规则中的条件x和y时，就不难发现当x和y为空时，正好是2型文法。从0型文法到3型文法，是依次增加对文法的限制，所以描述的语言集合越来越小。5、简述自底向上分析法。基本思想是：从待输入的符号串开始，利用文法的规则步步向上归约，试图归约到文法的识别符号。从语法树的角度看，自底向上分析的过程是以输入符号串作为末端结点符号串，向着根结点方向往上构造语法树，使识别符号正好是该语法树的根结点。如果最终根结点是识别符号，则输入符号串被识别是相应语言的一个句子；否则不是。自底向上分析过程实际上是一个不断进行直接归约的过程。1.对如下文法：G[S]：SabS|aaB|adBbbB|b分别给出句子abaabbb和ad的句柄（6分）句子abaabbb的句柄是b；句子ad的句柄是ad2.什么是可规约活前缀？举一例说明。（6分）若活前缀是含句柄的活前缀，即有α=α′π,且π是句柄，则活前缀α为可归约活前缀。例Sa|bCdCe则be为一个可归约活前缀3.写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列或P代码。（6分）(1)（*,b,c）(2)(+,a,(1))(3)(+,a,b)(4)(/,(2),(3))(5)(-,(4),d)4.词法分析和语法分析都是对字符串进行识别，二者有何区别？（4分）在词法分析和语法分析中，都是对输入符号串进行识别。但词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子或者说是一个程序。为了讨论方便，我们都是用小写字母来表示终结符号，但一定要明白在词法分析中小写字母表示组成单词的字符，而在语法分析中小写字母表示组成程序的的一个单词，识别方式来说，词法分析和语法分析都是对输入符号串结构的识别，但由于单词和程序的结构有所区别，所以具体的识别方式不一样。5.已知文法G[S]为：S→a|^|(T)T→T,S|S判断该文法是否是算符优先文法？如是，请给出算符优先关系表。（8分）(1)FIRSTVT和LASTVTFIRSTVTLASTVTSa、^、（a、^、）T，、a、^、（，、a、^、)(2)算符优先关系a(),^#a≯≯≯(≮≮≡≮)≯≯≯,≮≮≯≯≮^≯≯