1、*一.名词解释：1)前缀答：前缀是指符号串任意首部。2)可归前缀答：可归前缀是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。3)活前缀答：活前缀规范句型的一个前缀，这种前缀不含句柄之后的任何符号。或给定文法规范句型的可归前缀的任意首部。4)简单短语答：简单短语设 GZ是给定文法,w=xuyV +，为该文法的句型,如果满足下面两个条件: Z xUy； Uu ；则称句型 xuy 中的子串 u 是句型 xuy 的简单短语。5)扫描遍答：扫描遍指编译程序对源程序或中间代码程序从头到尾扫描一次。6)句柄答：句柄给定句型中的最左简单短语就是句柄。7)句型答：句型设 G 是一个给定的文法，
2、S 是文法的开始符号，如果S x(其中 xV *),则称 x 是文法的一个句型。8)句子答：句子设 G 是一个给定的文法，S 是文法的开始符号，如果 S x（其中 xV T*） ，则称 x 是文法的一个句子。9)非终结符答：非终结符出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。10)终结符答：终结符出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。11）属性文法答：一个属性文法形式的定义为一个三元组 AG，AG=（G，V，E） 。其中 G 为一个上下文无关文法；V 为属性的有穷集；E 为一组语义规则。12）语法制导翻译答：语法制导翻译语法制导翻译就是
3、在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。或：为文法中每个产生式配上一组语义规则，并且在语法分析过程中，随着分析的步步进展，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而进行翻译的办法称作语法制导翻译。13）后缀式*答：后缀式一种把运算量（操作数）写在前面，把算符写在后面（后缀）的表示法。14）短语答：短语设 GZ是给定文法,w=xuyV +，为该文法的句型,如果满足下面两个条件: Z xUy； U u；则称句型 xuy 中的子串 u 是句型 xuy 的短语。或：句型语法树的全部子树的叶从左到右排列起
4、来构成的符号串均是句型的短语。15）基本块答：基本块源程序或者中间代码程序中只有一个入口和一个出口的顺序执行的代码段。16）语义规则答：对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。17）语法分析答：语法分析按文法的产生式识别输入的符号串是否为一个句子的分析过程。18）四元式答：四元式是一个带有四个域的记录结构，这四个域分别称为操作符域、左运算对象域、右运算对象域及运算结果域。二简答题：1) 什么是句子？ 什么是语言?解答：句子设 G 是一个给定的文法，S 是文法的开始符号，如果 S x（其中 xV T*） ，则称 x 是文法的一个句子。语言语言是句子的集合。或设 GS是给定文
5、法，则由文法 G 所定义的语言 L(G)可描述为：L(G)xS x,xV T* 。2) DFA 与 NFA 有何区别 ? 解答:DFA 与 NFA 的区别表现为两个方面:一是 NFA 可以有若干个开始状态，而 DFA 仅只有一个开始状态。另一方面，DFA 的映象 M 是从 K到 K，而 NFA 的映象 M 是从 K到 K 的子集，即映象 M 将产生一个状态集合（可能为空集） ，而不是单个状态。3) 自顶向下的语法分析方法的基本思想是什么?解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。4) 自底向上的语法分
6、析方法的基本思想是什么?解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。5) 一个上下文无关文法 G 包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。6) 在自底向上的语法分析方法中，分析的关键是什么？解答:关键是寻找句柄。7) 在自顶向下的语法分析方法中，分析的关键是什么？解答:关键是选择候选式。8) 编译程序中语法分析器接收以什么为单位的输入？解答: 接收以单词为单位的输入。9) 若一个文法是递归的，则它所产生的语言的句子是可枚举的吗？解答: 它所产生的语言的句子不是可枚举的，而是无穷多个。10
7、) 编译程序生成的目标程序是不是一定是机器语言的程序？解答:不一定是机器语言的程序。11) 词法分析器是用于做什么的？解答:词法分析器是用于识别单词的。12) “用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法正确吗？解答: 不正确。13) 把汇编语言程序翻译成机器可执行的目标程序的工作是由什么完成的？解答: 由汇编器（汇编程序）完成的。14)图示运行时存储空间的划分（分为哪几个区） 。 解答: 一般分为静态区和动态区：程序代码区、静态数据区、栈区和堆区15)词法分析的主要任务是什么？ 解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依
8、次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属性字并输出。16)常用的中间语言种类有哪几种？解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。17）文法 G 所描述的语言是什么的集合？解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。18）乔姆斯基把文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 2型文法叫什么？解答: 2 型文法叫上下文无关文法。19）编译程序是一种解释程序吗？还是什么程序？解答:编译程序是一种翻译程序。20）按逻辑上划分，编译程序第二步工作是什么？解答: 编译程序第二步工作是语法分析。21）源程序是
9、用高级语言编写的，目标程序是机器语言程序或汇编语言程程序代码区静态数据区栈区堆区序 ，则其翻译程序称为什么？解答: 其翻译程序称为编译程序。22）编译方式与解释方式的根本区别为什么？解答:编译方式与解释方式的根本区别在于是否生成目标代码。23）常见的动态存贮分配策略有哪两种？解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。24）常用的参数传递方式有哪三种？解答:常见的参数传递方式有传地址、传值和传名三种方式。25）语法分析的任务是什么？解答:语法分析的任务是识别给定的终结符串是否为给定文法的句子。26）局部优化是局限于一个什么范围内的一种优化？解答: 是局限于一个基本块范
10、围内的一种优化。27）文法等价的定义是什么？解答: 设 G1 和 G2 是给定的文法，如果有 L（G1）= L（G2） ，则称 G1 与G2 等价。28）在语法分析处理中，FIRST 集合、FOLLOW 集合、SELECT 集合均是什么集合？解答: 均是终结符集。29）通常一个编译程序中应包括哪七个部分？解答: 通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化，目标代码生成以及表格处理和出错处理等七个部分。32）如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为哪三个阶段？解答: 源程序的执行分为三个阶段: 编译阶段，汇编阶段和运行阶段。33）翻译程序是这
11、样一种程序，它能够将用什么转换成与其等价的用乙语言书写的程序？解答:能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序。34）说明下面文法 GS是二义性文法：SSaS|SbS|cSd|eS|f解答:fafbf 是文法 GS的一个句子，并且有两个不同的最右推导。（1）S = SaS = SaSbS = SaSbf= Safbf= fafbf（2）S = SbS = Sbf= SaSbf = Safbf= fafbf因此说明此文法有二义性。35）在属性文法中，综合属性与继承属性是如何传递信息的？解答: 综合属性用于自下而上传递信息，继承属性用于自上而下传递信息。36）代码优化的主要目标是什
12、么？解答: 代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。37）写一个文法，使其语言是无符号二进制实数（不含指数） 。解答:文法 G(N)：NL.L|L其中：开始状态：0终止状态：2aaa0bbb12LLB|BB0|1三应用题1）消除下列文法 GA的左递归。EE-TTTT/FFF( E )i解答：消除文法 GE的左递归后得到：ETEE-T ETFTT/FTF( E )i2） 消除下列文法 GA的左递归。AAaBBBBbCCCeDDD(A)d解答：消除文法 GA的左递归后得到：A BAAaBAB CBBbcBCeDDD(A)d3）给定下列自动机：把此自动机转换
13、为确定自动机 DFA。解答： 有状态矩阵如图：从而可得 DFA 如图：a b0 01 201 01 22 1 21 2a b 0 0,1 2 1 2 2 1 2- 02aaba101bbb 02babb1极小化后： a1SS print:“a”2Sr D print:“b”3DD，i print:“c”4Di print:“d”4）正规式（a|b） *a(a|b) 构造一个等价的有限自动机。解答：四设计题（1）给定文法 GS 及相应翻译方案为：a. 按 chomsky 分类法，文法 G 属于哪一型文法？ b. 符号串 ri,i,i 是不是该文法的一个句型，请证实。 c. 若是句型，写出该句型的
14、所有短语、简单短语，以及句柄。d. 构造识别该文法的活前缀的 DFA。 e. 判断该文法是 LR（0）还是 SLR（1） ，并构造其相应的语法分析表。 f. 对于 ri,i,i 这个输入符号串，经该翻译方案翻译后的输出是什么？解答：a文法 G 属于 2 型(上下文无关)文法。b符号串 r i,i,i 是该文法的一个句型。证：SSrDrD，i rD ，i，i r i，i，i，得证。或证：构造语法树见图 4，可知符号串 r i,i,i 是该文法的一个句型。c句型 r i,i,i 的短语有：r i,i,i； i,i,i；i,i； 第一个 i简单短语有：第一个 i句柄有：第一个 id求得文法 G 的识
15、别全部活前缀的 DFA 见图 3：a,b aab 0 1 2I1:S S.I0:S.S S.rDI2:Sr.DD.D，iD.irI4:SrD.DD.，iD，SI5:DD，.iI3:Di.iiI6:DD，i.图 3 识别全部活前缀的 DFAe在项目集 I4 中存在冲突项目，文法 G 不是 LR（0）文法。FOLLOW(S)=#FOLLOW(S)=#FOLLOW(D)= ，,#而由于 ，FOLLOW(S)= ，#=，所以文法 G 是 SLR（1）文法。求得文法 G 的 SLR（1）分析表见表 1：f可以先求得该句子的语法树（见图 4） ，然后通过剪枝的方式进行归约，最后归约到文法的开始符号，在归约
16、的过程中同步产生输出符号串dccba。即对于 r i,i,i 这个输入符号串，该翻译方案的输出是：dccba（2）给定文法:（1）SbTc （2）Sa（3）TR（4）RR/S（5）RSa)符号串 ba/ac 是不是该文法的一个句子，请证实。b)若是句子，写出该句子的所有短语、简单短语和句柄。c)为该文法设计翻译方案，使句型 bR/bTc/bSc/ac 经该翻译方案翻译后,输出下列串：0342031320 解答：a) 符号串 ba/ac 是该文法的一个句子。SbTcbRcbR/ScbS/Scba/Scba/ac ，Sb cRR S/aSTaSrSDD i，iD i，图 4 句子的语法树ACTIO
17、N GOTOr ， i # S D0 S2 11 acc2 S3 43 R4 R44 S5 R25 S66 R3 R3表 1 SLR（1）分析表得证。或：给出符号串 ba/ac 的语法树如右图，则判定符号串 ba/ac 是该文法的一个句子。b)给出句型 ba/ac 的语法树如右图：则可求得句型 adbb 的短语有：ba/ac,a/a,第 1 个 a, 第 2 个 a简单短语有：第 1 个 a, 第 2 个 a句柄有：第 1 个 ac)给出句型 bR/bTc/bSc/ac 的语法树如右图：按照归约过程，则给定文法的相应翻译方案为： （1）SbTc print(“0”)（2）Sa print(“1
18、”)（3）TR print(“2”)（4）RR/S print(“3”)（5）RS print(“4”)（3）设有基本块： t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5t5:=2*Ct6:=3*At7:=t6+t5E:=t7-1F:=t4-Ea)画出 DAG 图；b)假设基本块出口时只有 E，F 还被引用，请写出优化后的三地址代码序列。解答：a)构造 DAG：见右图。b)优化后的三地址代码序列为：t1:=3*At2:=2*C5+*+*t4t1,t62A3n11n2n3n5n6n8En7F1n4t2,t5t3,t7n9Cn10n11n12Sb cRR S/SaRR SR Sb
19、cT/Tb cTt3:=t1+t2t4:=t3+5E:=t3-1F:=t4-E五转换题： 给定下列中缀式 (运算符优先级按常规理解) ，分别写出等价的逆波兰式和四元式。1）aba0b0解答：逆波兰式为：aba0b0写出等价的四元式表示1. (,a ,b ,T1)2. (,a ,0 ,T2)3. (,T1,T2,T3)4. (,b ,0 ,T4)5. (,T3,T4,T5)2）ab0a0(ab)2 解答：逆波兰式为：ab0a0ab2；四元式为：1.( ,a, ,T1)2.( ,T1,b ,T2)3.( ,T2,0 ,T3)4.( ,a ,0 ,T4)5.( ,a ,b ,T5)6.( ,T5,2 ,T6)7.( ,T4,T6,T7)8.( ,T3,T7,T8)5、关于坚持的名言，你既然期望辉煌伟大的一生，那么就应该从今天起，以毫不动摇的决心和坚定不移的信念，凭自己的智慧和毅力，去创造你和人类的快乐。 佚名
