《编译原理简答》由会员分享，可在线阅读，更多相关《编译原理简答（24页珍藏版）》请在金锄头文库上搜索。
1、如果您需要使用本文档，请点击下载按钮下载!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。1 / 22如果您需
2、要使用本文档，请点击下载按钮下载!3、文法GS为：SSdT | TTTG | GG(S) | a试给出句型(SdG)a的短语、简单(直接)短语、句柄和最左素短语。句型(SdG)a的短语：(SdG)Ac|aB A-ab B-bc 该文法是否为二义的？为什么？对于串abc (1)S=Ac=abc (2)S=aB=abc 即存在两不同的最右推导 所以，该文法是二义的。3 / 22如果您需要使用本文档，请点击下载按钮下载!3、将文法GS 改写为等价的GS，使GS不含左递归和左公共因子。GS： SSAe|Ae AdAbA|dA|d文法GS 改写为等价的不含左递归和左公共因子的GS为： S AeSS Ae
3、S|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经一步推导，最左的终极符肯定不同，因此，对于一个字符串，不可能有两种方法推导。4 / 22如果您需要使用本文档，请点击下载按钮下载!5、文法GS为： S-Ac|aB A-ab B-bc 写出L(GS)的全部元素S=Ac
4、=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 改写为等价的不含左递归和左公共因子的GS为：SbB BSAe | AAd A A bA | 3、写出Pascal 或C语言的字母表。pascal语言的字母表是：0，1，9a，zA，Z+，-，*，/，?，?，_， (，)，;，:，
5、=，Enter，Space，Tab5 / 22如果您需要使用本文档，请点击下载按钮下载!C语言的字母表是：_, 09, az, AZ, +, -, *, /, , %, (, ), , , ., &, |, ！, =, #, , , , ”, ?, :， Enter，Space，Tab4、有文法GZ：ZaZbZ|aZ|a 该文法是否是二义的，试证明之。对于句子aaaba，画出二棵不同的语法树，因而是二义的。5、LL （ 1 ）分析法对文法有哪些要求？LL(1)分析法对文法的要求是：对于G的每个非终结符A的任何两个不同产生式A-|，有下述条件成立： First() First()= 若=*，则F
6、irst()Follow(A)=6 / 22如果您需要使用本文档，请点击下载按钮下载!1、解释编译程序中“遍”的概念，何谓“单遍扫描”？遍指编译程序对源程序或中间代码程序从头到尾扫描一次对于源程序或中间代码程序，从头到尾扫描一次并完成所规定的工作称为一遍。单遍扫描是编译程序的一种极端情形。在这种情形下，整个编译程序同时驻留在内存中，编译程序的各部门之间采用“调用转接”方式连接在一起。2、设有文法GS为：Sa|b|(A)ASdA|S给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。短语：S，SdS，SdSdS，（SdSdS）简单短语（即直接短语）：S句柄（即最左直接短语）：S素短
7、语：SdS，它同时也是该句型的最左素短语。7 / 22如果您需要使用本文档，请点击下载按钮下载!图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、画出编译程序的总体结构图。编译程序的总框图见下图。8 / 22如果您需要使用本文档，请点击下载按钮下载!5、给出0，1，2，3型文法的定义。乔姆斯基(chomsky)把文法分成类型，即0型，1型，2型和3型，0型强于1
8、型，1型强于2型，2型强于3型。 如果它的每个产生式-的结构是（VnUVt）*且至少含有一个非终结符,而（VnUVt）*，我们说G=（Vt，VN，S，）是一个0型文法。 0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵(Tunring)机。或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。 如果把0型文法分别加上以下的第i条限制，则我们就得i型文法为： 1G的任何产生式- 均满足|例外，但S不得出现在任何产生式的右部。 2G的任何产生式为A-，AVn，（VnUVt）* 3G的任何产生式为A-aB或A-a，其中A，BVn 1型文法也称上下文有关文
9、法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，般不允许替换成空串。 2型文法对非终结符进行替换时无须考虑上下文， 3型文法也称线性文法。 9 / 22如果您需要使用本文档，请点击下载按钮下载!1、什么是规范推导？每个句型都有规范推导吗？规范推导就是最右推导每一个句子都有一个规范推导，而每一个句型则不一定都有规范推导，比如说采用非规范推导得到的句型。2、已知文法GE: EET+|T TTF* | F FF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄。该句型对应的语法树如下： 该句型相对于E的短语有FF*；相对于T的短语有FF*,F;相对于F的短语有F;F;
10、简单短语有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)10 / 22如果您需要使用本文档，请点击下载按钮下载!4、何谓优化？按所涉及的程序范围可分为哪几级优化？所谓优化，一般是指为提高目标程序的质量而进行的各项工作，即对程序或中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 在源程序级 在语义动作的设计上 在中间代码级 在目标代码级5、简述自
11、顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。1、计算机执行用高级语言编写的程序有那些途径？它们之间的主要区别是什么？计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序并不对高级语言进行彻底的翻译，而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再执行。在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码，然后再对目标代码进行优化，即对源程序的处理是先翻译后执行。从速度上看，编
