编译原理超强复习纲领

PAGE编译原理课程英文词汇alphabet字母表symbol符号string串length长度catenation连接power方幂gather集合product乘积emptyset空集closure闭包program程序logicstructure逻辑结构generating产生executing执行machinelanguage机器语言instruction指令function函数assembler汇编程序interpreter解释程序translator翻译程序sourcelanguage源语言finite有穷的sourceprogram源程序targetlanguage目标语言attribute属性possess占有preprocess预处理compiler编译程序break中断Intermediatelanguage中间语言definition定义reconstructed重构normal正规charactersequences符号序列programminglanguage程序设计语言operand操作数instead替换memory内存element元素high-levellanguage高级语言objectprogram目标程序address地址input输入output输出terminal终结符compilation编辑equivalence等价nonterminal非终结符recursion递归deterministic确定的nondeterministic非确定的Backus-NormalForm巴科斯范式syntax语法tree树expression表达式grammar文法automata自动机prefix前缀suffix后缀infix中缀identify识别identifier标识符analyses分析predigest化简symbolset符号集performed执行forecast预测state状态formula产生式conversion变换precedence优先simple简单handle句柄operator算符terminalstate终态firststate初态optimizer优化程序concatenation连接word单词alphabet字母表lexical词法scanner扫描器analyzer分析器syntaxtree语法树symboltable符号表pass趟，遍regularexpression正规表达式codegenerator代码生成器backdate回溯derivation推导educe推导derivationtree推导树path路径ambiguous二义性simplephrase简单短语context-sensitive上下文有关context-free上下文无关right-linear右线形phrase-structured短语结构regulargrammar文法directderivation直接推导sentence句子sententialform句型rootnode根结点subtree子树semantic语义的terminalnode端末结点attributegrammar属性文法canonicalderivation规范推导top-down自上而下bottom-up自下而上viableprefix活前缀nondeterminatefiniteautomata非确定的有穷自动机编译复习：一．专业术语英汉对译：复习老师给出的编译原理课程英文词汇二、概念题(单项选择题、填空题、判断正误题、名词解释题、简答题)1.翻译程序的种类有哪些？把汇编语言程序翻译成机器可执行的目标程序的工作是由什么来完成的？2.编译程序生成的结果是什么？目标程序；不一定是机器语言的程序。3．高级语言的翻译处理只有编译一种方式？4.在LR分析法中，分析栈中存放的状态是识别规范句型的什么状态？5.词法分析器用于识别什么？语法分析器接收以什么为单位的输入？6．在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？7．若一个文法是递归的，则它所产生的语言的句子有多少？8．按逻辑上划分，一个编译程序的组成部分有哪些？它的工作过程由哪几部分来完成的？各部分的任务是什么？9．属性有哪些分类？它们如何传递信息？10．乔姆斯基（Chomsky）把文法分为几种类型？各是什么名称？11．无符号常数的识别和拼数工作通常是在什么阶段完成？12．在语法分析方法中，自底向上的分析的关键是什么？自顶向下的分析的关键是什么？13．一个上下文无关文法G的定义是什么？语义规则的定义是什么？语法分析的定义是什么？四元式的定义是什么？语言的定义是什么？可归前缀的定义是什么？句型的定义是什么？句子的定义是什么？后缀式的定义是什么？扫描遍的定义是什么？活前缀的定义是什么？句柄定义14．源程序经翻译后能直接运行的目标程序是什么程序？15.正则文法产生的语言是否都可以用上下文无关文法来描述？16.编译程序在优化阶段是否要用到源程序中的注释？17.用高级语言书写的源程序是否都必须通过编译产生目标代码后才能投入运行？18.解释与编译方式的区别是否是解释方式对源程序没有真正进行翻译？19.对任何NFAM，是否都存在一个正则表达式e或正则文法与之等价?对任何正则表达式e，是否都存在一个NFAM,满足L（M）=L(e)？对任何正则文法G，都存在一个NFAM,满足L（M）=L(G)？20.任何句型是否都存在一个规范推导，任何句子是否也都存在一个规范推导？21.定义一个语言的文法是否是唯一的？22.对任一编译程序来说，产生中间代码是不是必要的？23.具有优化功能的编译程序的效率是否较高？24.符号表由词法分析程序建立，是否只能由语法分析程序使用？25.一个句型的句柄与文法某产生式的右部是什么关系？26.数组元素的地址计算与数组的存储方式是否有关？27.每个文法是否都能改写为LL(1)文法？28.在中间代码优化中循环的优化包含哪些优化工作？29.语义分析过程中的主要问题是否是候选式的选择？30.在程序中出现的标识符仅为使用性出现的？31.在编译中进行语法检查的目的仅是为了发现程序中各种错误？32.递归下降法是否允许任一非终极符是直接左递归的？33.自顶向下语法分析的思想是什么？自底向上语法分析的思想是什么？34.代码生成是否与具体的机器硬件无关？35.基本块的定义是什么？36.何谓语法制导翻译?目标代码有哪几种形式？37.什么是文法的二义性？证明给定文法G[N]的二义性。38.DFA与NFA有何区别?39．在规范归约中，用什么来刻画可归约串？40．四元式之间的联系是通过什么实现的？41．过程的DISPLAY表中记录了过程的什么？三．自动机转换题给定一个NFAM：（此处自动机略）1.把此自动机转换为等价的确定自动机DFA。2.给出与此DFA等价的正则表达式。四．给定中缀式，写出它们等价的后缀式和四元式。五．给出一个三地址代码序列，请用DAG进行局部优化：（此处三地址代码序列略）1.画出DAG图；2.假设基本块出口时只有某些变量还被引用，写出优化后的三地址代码序列。六．给定文法G[S]：（此处文法略）1.文法G属于chomsky哪一型文法？2.给定符号串，判定该符号串是不是该文法的一个句子，请证实。3.若是句子，写出该句型的所有短语、简单短语，以及句柄。4.构造识别该文法的活前缀的DFA。5.判断该文法是LR（0）还是SLR（1），并构造其分析表？6.对于给定的属性文法和输入符号串α，该翻译方案的输出是什么？（需要给出解题过程）一.名词解释： 1)前缀答：前缀——是指符号串任意首部。2)可归前缀答：可归前缀——是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。3)活前缀答：活前缀——规范句型的一个前缀，这种前缀不含句柄之后的任何符号。或给定文法规范句型的可归前缀的任意首部。4)简单短语答：简单短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:①ZxUy；②Uu；则称句型xuy中的子串u是句型xuy的简单短语。5)扫描遍答：扫描遍——指编译程序对源程序或中间代码程序从头到尾扫描一次。6)句柄答：句柄——给定句型中的最左简单短语就是句柄。7)句型答：句型——设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈V*),则称x是文法的一个句型。*8)*答：句子——设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*），则称x是文法的一个句子。9)非终结符答：非终结符—出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。10)终结符答：终结符——出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。11）属性文法答：一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。12）语法制导翻译答：语法制导翻译——语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。13）后缀式答：后缀式——一种把运算量（操作数）写在前面，把算符写在后面（后缀）的表示法。14）短语答：短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:①ZxUy；②Uu；则称句型xuy中的子串u是句型xuy的短语。或：句型语法树的全部子树的叶从左到右排列起来构成的符号串均是句型的短语。15）基本块答：基本块——源程序或者中间代码程序中只有一个入口和一个出口的顺序执行的代码段。16）语义规则答：对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。17）语法分析答：语法分析——按文法的产生式识别输入的符号串是否为一个句子的分析过程。18）四元式答：四元式——是一个带有四个域的记录结构，这四个域分别称为操作符域、左运算对象域、右运算对象域及运算结果域。二．简答题：什么是句子？什么是语言?*解答：句子——设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*），则称x*语言——语言是句子的集合。或——设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*}。DFA与NFA有何区别?解答:DFA与NFA的区别表现为两个方面:一是NFA可以有若干个开始状态，而DFA仅只有一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。自顶向下的语法分析方法的基本思想是什么?解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。自底向上的语法分析方法的基本思想是什么?解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。一个上下文无关文法G包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。在自底向上的语法分析方法中，分析的关键是什么？解答:关键是寻找句柄。在自顶向下的语法分析方法中，分析的关键是什么？解答:关键是选择候选式。编译程序中语法分析器接收以什么为单位的输入？解答:接收以单词为单位的输入。若一个文法是递归的，则它所产生的语言的句子是可枚举的吗？解答:它所产生的语言的句子不是可枚举的，而是无穷多个。编译程序生成的目标程序是不是一定是机器语言的程序？解答:不一定是机器语言的程序。词法分析器是用于做什么的？解答:词法分析器是用于识别单词的。程序代码区静态数据区栈区堆区“用高级语言书写的源程序都必须通过编译,程序代码区静态数据区栈区堆区解答:不正确。把汇编语言程序翻译成机器可执行的目标程序的工作是由什么完成的？解答:由汇编器（汇编程序）完成的。14)图示运行时存储空间的划分（分为哪几个区）。解答:一般分为静态区和动态区：程序代码区、静态数据区、栈区和堆区15)词法分析的主要任务是什么？解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属性字并输出。16)常用的中间语言种类有哪几种？解答:常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。17）文法G所描述的语言是什么的集合？解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。18）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？解答:2型文法叫上下文无关文法。19）编译程序是一种解释程序吗？还是什么程序？解答:编译程序是一种翻译程序。20）按逻辑上划分，编译程序第二步工作是什么？解答:编译程序第二步工作是语法分析。21）源程序是用高级语言编写的，目标程序是机器语言程序或汇编语言程序，则其翻译程序称为什么？解答:其翻译程序称为编译程序。22）编译方式与解释方式的根本区别为什么？解答:编译方式与解释方式的根本区别在于是否生成目标代码。23）常见的动态存贮分配策略有哪两种？解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。24）常用的参数传递方式有哪三种？解答:常见的参数传递方式有传地址、传值和传名三种方式。25）语法分析的任务是什么？解答:语法分析的任务是识别给定的终结符串是否为给定文法的句子。26）局部优化是局限于一个什么范围内的一种优化？解答:是局限于一个基本块范围内的一种优化。27）文法等价的定义是什么？解答:设G1和G2是给定的文法，如果有L（G1）=L（G2），则称G1与G2等价。28）在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？解答:均是终结符集。29）通常一个编译程序中应包括哪七个部分？解答:通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化，目标代码生成以及表格处理和出错处理等七个部分。32）如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为哪三个阶段？解答:源程序的执行分为三个阶段:编译阶段，汇编阶段和运行阶段。33）翻译程序是这样一种程序，它能够将用什么转换成与其等价的用乙语言书写的程序？解答:能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序。34）说明下面文法G[S]是二义性文法：S→SaS|SbS|cSd|eS|f解答:fafbf是文法G[S]的一个句子，并且有两个不同的最右推导。（1）S=>SaS=>SaSbS=>SaSbf=>Safbf=>fafbf（2）S=>SbS=>Sbf=>SaSbf=>Safbf=>fafbf因此说明此文法有二义性。35）在属性文法中，综合属性与继承属性是如何传递信息的？解答:综合属性用于自下而上传递信息，继承属性用于自上而下传递信息。36）代码优化的主要目标是什么？解答:代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。37）写一个文法，使其语言是无符号二进制实数（不含指数）。解答:文法G(N)：N→L.L|LL→LB|BB→0|1三．应用题1）消除下列文法G[A]的左递归。E→E-T∣TT→T/F∣FF→(E)∣i解答：消除文法G[E]的左递归后得到：E→TE′E’→-TE′∣εT→FT′T’→/FT′∣εF→(E)∣i消除下列文法G[A]的左递归。A→AaB∣BB→BbC∣CC→eD∣DD→(A)∣d解答：消除文法G[A]的左递归后得到：A→BAˊAˊ→aBAˊ∣εB→CBˊBˊ→bcBˊ∣εC→eD∣DD→(A)∣d3）给定下列自动机：其中：开始状态：其中：开始状态：0终止状态：2aaa0bbb12把此自动机转换为确定自动机DFA。ab001201012ab001201012－21212ab00,1212－212-02-02aaba101bbb02babb1极小化后：a4）正规式（a|b）*a(a|b)构造一个等价的有限自动机。解答：a,ba,baab012四．设计题（1）给定文法G[S′]及相应翻译方案为：11．S→S{print:“a”}2．S→rD{print:“b”}3．D→D，i{print:“c”}4．D→i{print:“d”}a.按chomsky分类法，文法G属于哪一型文法？b.符号串ri,i,i是不是该文法的一个句型，请证实。c.若是句型，写出该句型的所有短语、简单短语，以及句柄。d.构造识别该文法的活前缀的DFA。e.判断该文法是LR（0）还是SLR（1），并构造其相应的语法分析表。f.对于ri,i,i这个输入符号串，经该翻译方案翻译后的输出是什么？解答：a．文法G属于2型(上下文无关)文法。b．符号串ri,i,i是该文法的一个句型。证：SSrDrD，irD，i，iri，i，i，得证。或证：构造语法树见图4，可知符号串ri,i,i是该文法的一个句型。c．句型ri,i,i的短语有：①ri,i,i；②i,i,i；③i,i；④第一个i简单短语有：第一个i句柄有：第一个id．求得文法G的识别全部活前缀的DFA见图3：II1:S→S.I0:S′→.SS→.rDI2:S→r.DD→.D，iD→.irI4:S→rD.D→D.，iD，SI5:D→D，.iI3:D→i.iiI6:D→D，i.图3识别全部活前缀的DFAe．∵在项目集I4中存在冲突项目，∴文法G不是LR（0）文法。FOLLOW(S)={#}FOLLOW(S)={#}FOLLOW(D)={，,#}而由于{，}∩FOLLOW(S)={，}∩{#}=Φ，所以文法G是SLR（1）文法。SrSDDi，iDSrSDDi，iDi，图4句子的语法树ACTIONACTIONGOTOr，i#SD0S211acc2S343R4R44S5R25S66R3R3表1SLR（1）分析表f．可以先求得该句子的语法树（见图4），然后通过剪枝的方式进行归约，最后归约到文法的开始符号，在归约的过程中同步产生输出符号串dccba。即对于ri,i,i这个输入符号串，该翻译方案的输出是：dccba（2）给定文法:（1）S→bTc（2）S→a（3）T→R（4）R→R/S（5）R→Sa)符号串ba/ac是不是该文法的一个句子，请证实。b)若是句子，写出该句子的所有短语、简单短语和句柄。c)为该文法设计翻译方案，使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出下列串：SbSbcRRS/aSTa解答：a)符号串ba/ac是该文法的一个句子。∵SbTcbRcbR/ScbS/Scba/Scba/ac，∴得证。或：给出符号串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的语法树如右图：SbcSbcRRS/SaRRSRSbcT//TbcT（1）S→bTc{print(“0”)}（2）S→a{print(“1”)}（3）T→R{print(“2”)}（4）R→R/S{print(“3”)}（5）R→S{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还被引用，请写出优化后的三地址代码序列。5－5－+*+*－t4t1,t62A3n11n2n3n5n6n8En7F1n4t2,t5t3,t7n9Cn10n11n12a)构造DAG：见右图。b)优化后的三地址代码序列为：t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5E:=t3-1F:=t4-E五．转换题：给定下列中缀式(运算符优先级按常规理解)，分别写出等价的逆波兰式和四元式。1）a≤b∧a＞0∨b＜0解答：逆波兰式为：ab≤a0＞∧b0＜∨写出等价的四元式表示1.(≤,a,b,T1)2.(＞,a,0,T2)3.(∧,T1,T2,T3)4.(＜,b,0,T4)5.(∨,T3,T4,T5)―2）―a＋b≤0∨a＜0∧(a―b)>2―解答：逆波兰式为：a―b＋0≤a0＜ab―2＞∧∨；―四元式为：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)一、填空题:1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理.1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于是否生成目标代码.1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序.1-05.对编译程序而言,输入数据是源程序,输出结果是目标程序.1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段:编译阶段和运行阶段.如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段:编译阶段,汇编阶段和运行阶段.1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。1-09.编译方式与解释方式的根本区别为是否生成目标代码。2-01.所谓最右推导是指：任何一步αβ都是对α中最右非终结符进行替换的。2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。2-03.产生式是用于定义语法成分的一种书写规则。2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*}。2-05.设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈V*），则称x是文法的一个句型。2-06.设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈VT*),则称x是文法的一个句子。3-01.扫描器的任务是从源程序中识别出一个个单词符号。4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。4-03.递归下降法不允许任一非终极符是直接左递归的。4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。4-05.递归下降分析法是自顶向上分析方法。4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。5-03.简单优先方法每次归约当前句型的句柄，算符优先方法每次归约当前句型的最左素短语，二者都是不断移进输入符号，直到符号栈顶出现可归约串的尾，再向前找到可归约串的头，然后归约。5-04.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最左归约，0的含义是向貌似句柄的符号串后查看0个输入符号。5-05.在SLR（1）分析法的名称中，S的含义是简单的。6-01.所谓属性文法是一个属性文法是一个三元组：A＝（G，V，F），一个上下文无关文法G；一个属性的有穷集V和关于属性的断言或谓词的有穷集F。每个断言与文法的某产生式相联。6-02.综合属性是用于“自下而上”传递信息。6-03.继承属性是用于“自上而下”传递信息。6-04.终结符只有综合属性，它们由词法分析器提供。7-01.在使用高级语言编程时,首先可通过编译程序发现源程序的全部A错误和B部分错误.a.语法

b.语义

c.语用

d.运行8-01.符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。8-02.一个过程相应的DISPLAY表的内容为现行活动记录地址和所有外层最新活动记录的地址。9-01.一个过程相应的DISPLAY表的内容为现行活动记录地址和所有外层最新活动记录的地址。9-02.常用的两种动态存贮分配办法是栈式动态分配和堆式动态分配。9-03.常用的参数传递方式有传地址，传值和传名。10-01.局部优化是局限于一个基本块范围内的一种优化。10-02.代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。二、单选题:1-10.一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括(1)c.其中,(2)b和代码优化部分不是每个编译程序都必需的.词法分析器用于识别(3)c,语法分析器则可以发现源程序中的(4)d.(1)

a.模拟执行器

b.解释器

c.表格处理和出错处理

d.符号执行器(2)

a.语法分析

b.中间代码生成

c.词法分析

d.目标代码生成(3)

a.字符串

b.语句

c.单词

d.标识符(4)

a.语义错误

b.语法和语义错误

c.错误并校正

d.语法错误1-11.程序语言的语言处理程序是一种(1)a.(2)b是两类程序语言处理程序,他们的主要区别在于(3)d.(1)

a.系统软件

b.应用软件

c.实时系统

d.分布式系统(2)

a.高级语言程序和低级语言程序

b.解释程序和编译程序c.编译程序和操作系统

d.系统程序和应用程序(3)

a.单用户与多用户的差别

b.对用户程序的查错能力c.机器执行效率

d.是否生成目标代码1-12.汇编程序是将a翻译成b,编译程序是将c翻译成d.a.汇编语言程序b.机器语言程序c.高级语言程序d.a或者be.a或者cf.b或者c1-13.下面关于解释程序的描述正确的是b.(1)解释程序的特点是处理程序时不产生目标代码(2)解释程序适用于COBOL和FORTRAN语言(3)解释程序是为打开编译程序技术的僵局而开发的

a.(1)(2)

b.(1)

c.(1)(2)(3)

d.(2)(3)1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少(1)e和(1)b.其中，(1)e的目的是使最后阶段产生的目标代码更为高效.与编译系统相比，解释系统(2)d.解释程序处理语言时,大多数采用的是(3)b方法.(1):a.中间代码生成

b.目标代码生成

c.词法分析

d.语法分析

e.代码优化(2):a.比较简单,可移植性好,执行速度快b.比较复杂,可移植性好,执行速度快c.比较简单,可移植性差,执行速度慢d.比较简单,可移植性好,执行速度慢(3):a.源程序命令被逐个直接解释执行b.先将源程序转化为之间代码,再解释执行c.先将源程序解释转化为目标程序,在执行d.以上方法都可以1-15.用高级语言编写的程序经编译后产生的程序叫b.用不同语言编写的程序产生b后,可用g连接在一起生成机器可执行的程序.在机器中真正执行的是e.a.源程序

b.目标程序

c.函数

d.过程

e.机器指令代码

f.模块

g.连接程序

h.程序库1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容:c,d,f.a.汇编语言

b.高级语言

c.源语言

d.目标语言e.程序设计方法

f.编译方法

g.测试方法

h.机器语言1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成(1)d,诸阶段的工作往往是(2)d进行的.(1)a.过程

b.程序

c.批量

d.遍(2)a.顺序

b.并行

c.成批

d.穿插1-18.编译程序与具体的机器a,与具体的语言a.a.

有关

b.无关1-19.使用解释程序时,在程序未执行完的情况下，a重新执行已执行过的部分.a.也能

b.不可能1-20.编译过程中,语法分析器的任务就是b.(1)分析单词是怎样构成的

(2)

分析单词串是如何构成语句和说明的(3)分析语句和说明是如何构成程序的

(4)分析程序的结构a.(2)(3)

b.(2)(3)(4)

c.(1)(2)(3)

d.(1)(2)(3)(4)1-21.编译程序是一种常用的b软件.a.

应用

b.系统1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过b这几步.(1)编辑

(2)编译

(3)连接

(4)运行a.(1)(2)(3)(4)

b.(1)(2)(3)

c.(1)(3)

d.(1)(4)1-23.编译程序必须完成的工作有a.(1)词法分析

(2)语法分析

(3)语义分析(4)代码生成

(5)之间代码生成

(6)代码优化a.(1)(2)(3)(4)

b.(1)(2)(3)(4)(5)

c.(1)(2)(3)(4)(5)(6)

d.(1)(2)(3)(4)(6)

e.(1)(2)(3)(5)(6)1-24.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法a.a.不正确

b.正确1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由b完成的.a.编译器

b.汇编器

c.解释器

d.预处理器1-26.编译程序生成的目标程序b是机器语言的程序.a.

一定

b.不一定1-27.编译程序生成的目标程序b是可执行的程序.a.

一定

b.不一定1-28．编译程序是一种B。A.汇编程序B.翻译程序C.解释程序D.目标程序1-29．按逻辑上划分，编译程序第二步工作是C。A.语义分析B.词法分析C.语法分析D.代码优化1-30．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括C。A.模拟执行器

B.解释器

C.表格处理和出错处理

D.符号执行器2-06．已知语言L={xnyyn|n>=1}，则下述文法中，D可以产生语言L。A1.Z→xZy|xAy|yB1.A→xAy2.A→xAy|x2.A→xC1.Z→AyBD1.Z→xAy2.A→xA|x2.A→xAy|y3.B→yB|y2-07．文法G所描述的语言是C的集合。A.文法G的字母表V中所有符号组成的符号串B.文法G的字母表V的闭包V*中的所有符号串C.由文法的开始符号推出的所有终极符串D.由文法的开始符号推出的所有符号串2-08．乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是B。A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法2-09.文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是C。A.L(G[N])={bi│i≥0}B.L(G[N])={b2i│i≥0}C.L(G[N])={b2i+1│i≥0}D.L(G[N])={b2i+1│i≥1}2-10．一个句型中的最左B称为该句型的句柄。可选项有：A.短语B.简单短语C.素短语D.终结符号2-11．设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈V*),则称x是文法G的一个B。A.候选式B.句型C.单词D.产生式2-12．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组D。A.句子B.句型C.单词D.产生式2-13.文法G[E]：E→T∣E＋TT→F∣T﹡FF→a∣（E）该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的B。①（E＋T）②E＋T③F④F﹡(E＋T)可选项有：A)①和③B)②和③C)③和④D)③2-14．若一个文法是递归的，则它所产生的语言的句子A。A.是无穷多个B.是有穷多个C.是可枚举的D.个数是常量2-15．文法的二义性和语言的二义性是两个A的概念。A不同B相同C无法判断D不存在3-02．词法分析器用于识别C。A.句子B.句型C.单词D.产生式4-07.在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是B。A.非终极符集B.终极符集C.字母表D.状态集4-08.编译程序中语法分析器接收以A为单位的输入。A.单词B.表达式C.产生式D.句子5-06．在自底向上的语法分析方法中，分析的关键是D。A.寻找句柄B.寻找句型C.消除递归D.选择候选式5-07.在LR分析法中，分析栈中存放的状态是识别规范句型C的DFA状态。A.句柄B.前缀C.活前缀D.LR(0)项目三、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。)1-31.计算机高级语言翻译成低级语言只有解释一种方式。（×）1-32.在编译中进行语法检查的目的是为了发现程序中所有错误。（×）1-34.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。（×）2-15.正则文法其产生式为Aa，ABb,A,B∈VN，a、b∈VT。（√）4-09.每个文法都能改写为LL(1)文法。（×）4-10.递归下降法允许任一非终极符是直接左递归的。（√）5-08.算符优先关系表不一定存在对应的优先函数。（√）5-09.自底而上语法分析方法的主要问题是候选式的选择。（×）5-10.LR法是自顶向下语法分析方法。（×）5-11.简单优先文法允许任意两个产生式具有相同右部。（×）5-12.若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。（×）5-13.一个句型的句柄一定是文法某产生式的右部。（√）7-02.数组元素的地址计算与数组的存储方式有关。（√）8-03.在程序中标识符的出现仅为使用性的。（×）9-04.对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。（×）9-05.在程序中标识符的出现仅为使用性的。（×）10-03.仅考虑一个基本块，不能确定一个赋值是否真是无用的。（√）10-04.削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。（×）10-05.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。（√）四、名词解释1-35.扫描遍____指编译程序对源程序或中间代码程序从头到尾扫描一次。2-16.短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:①ZxUy；②Uu；则称句型xuy中的子串u是句型xuy的短语。2-17.简单短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:①ZxUy；②Uu；则称句型xuy中的子串u是句型xuy的简单短语（或直接短语）。2-18.句柄——一个句型中的最左简单短语称为该句型的句柄。2-19.答：规范推导——如果在任一步推导vw中，都是对符号串v的最右非终结符进行替换，则称其为规范推导。*2-21.答：语言——L（G[Z]）={x|Zx，x∈VT*}。*4-11.语法分析－－按文法的产生式识别输入的符号串是否为一个句子的分析过程。4-12.选择符集合SELECT－－给定上下文无关文法的产生式A→α,A∈VN,α∈V*,若αε,则SELECT(A→α)=FIRST(α),其中如果αε，则SELECT(A→α)=FIRST(α\ε)∪FOLLOW(A),FIRST(α\ε)表示FIRST(α)的非{ε}元素。RR5-14.活前缀——若S′αAωαβω是文法G′中的一个规范推导，G′是G的拓广文法，符号串γ是αβ的前缀，则称γ是G的，也是G′的一个活前缀。其中S'为文法开始符号。或：可归前缀的任意首部。RR5-15.可归前缀——是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。5-16.LR(0)项目——把产生式右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。5-17.算符优先文法——设有一不含ε产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有、和三种关系中的一种成立，则称G是一个算符优先文法。5-18.最左素短语——设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。6-05.语义规则——对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。6-06.翻译方案——将属性文法中的语义规则用花括号{}括起来，插在产生式右部的合适地方，指明语义规则的计算次序，陈述一些细节，得到一种语义动作与语法分析交错的表示方法，以表述语义动作在语法分析过程中的执行时刻，称之为翻译方案。6-07.语法制导翻译——为文法中每个产生式配上一组语义规则，并且在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。7-03.后缀式——一种把运算量（操作数）写在前面把算符写在后面（后缀）的表示法。即一个表达式E的后缀形式可以如下定义：如果E是一个变量或常量，则E的后缀式是E自身。如果E是E1opE2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’op，这里E1’和E2’分别为E1和E2的后缀式。如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。7-04.四元式——一个四元式是一个带有四个域的记录结构，这四个域分别称为op、arg1、arg2及result。域op包含一个代表运算符的内部码。9-06.活动答：一个过程的活动指的是该过程的一次执行。就是说，每次执行一个过程体，产生该过程体的一个活动。9-07.活动记录答：为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样一个连续的存储块称为活动记录。9-08.活动的生存期答：指的是从执行某过程体第一步操作到最后一步操作之间的操作序，包括执行过程时调用其它过程花费的时间。10-02.答：基本块——源程序中只有一个入口和一个出口的顺序执行的代码段。10-06.基本块的DAG。答：一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG。

(1)图的叶结点（没有后继的结点）以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。

(2)图的内部结点（有后继的结点）以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。

(3)图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。五、简答题：2-19什么是句子？什么是语言?答：设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈VT*),则称x是文法的一个句子。设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*}。2-20.已知文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→（E）|i①该文法的开始符号（识别符号）是什么？②请给出该文法的终结符号集合VT和非终结符号集合VN。③找出句型T+T*F+i的所有短语、简单短语和句柄。解：①该文法的开始符号（识别符号）是E。②该文法的终结符号集合VT={+、-、*、/、（、）、i}。非终结符号集合VN={E、T、F}。③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;简单短语为i、T*F、第一个T;句柄为第一个T。2-21.已知文法G[S]为：S→dABA→aA|aB→Bb|ε①G[S]产生的语言是什么？②G[S]能否改写为等价的正规文法？解：①G[S]产生的语言是L(G[S])={danbm│n≥1,m≥0}。②G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[Sˊ]为：Sˊ→dAA→aA|aB|aB→bB|b2-22.设有语言L(G)={adaR|a∈(a,b)*,aR为a之逆}，试构造产生此语言的上下文无关文法G。解：根据题义，可知aR为a之逆的含义就是句子中的符号a、b以d为中心呈左右对称出现；由于a∈(a,b)*，所以a、b的个数可以为零。所以可构造产生此语言的上下文无关文法G[S]为：S→aSa|bSb|d2-23.证明下面文法G[N]是二义性文法。G[N]：N→SE∣ES→SD∣DE→0∣2∣10D→0∣1∣2答：10是文法G[N]的一个句子，并且有两个不同的最右推导。（1）1S=>E=>10（2）S=>SE=>S0=>D0=>10因此说明此文法有二义性。3-03．简述DFA与NFA有何区别?答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。3-04.试给出非确定自动机的定义。答：一个非确定的有穷自动机（NFA）M是一个五元组：M=（K，Σ，f，S，Z）。其中:1.K是一个有穷集，它的每个元素称为一个状态；2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；3.f是状态转换函数，是在K×Σ*→K的子集的映射，即，f:K×Σ*→2K；表明在某状态下对于某输入符号可能有多个后继状态；4.S﹙K是一个非空初态集；5.Z﹙K是一个终态集（可空）。3-05.为正规式（a|b）*a(a|b)构造一个等价的确定的有限自动机。a,baa,baab0123-06.给定下列自动机，将其转换为确定的自动机。dddεd··dddd＋startd―εSADBCEGH注：带＋号的结点为初始状态；带―号的结点为终止状态―――＋解答：(1)消除ε边，得到NFA：――＋――ddddd··dddd＋―ddd·＋SADBCEGH注：带＋号的结点为初始状态；带―号的结点为终止状态(2)确定化，得到DFA：＋―d·＋―d·SABCDEGHAABCEBCEBCDEHHGDG+[SA][A][BCE][G][DG][H][DH][A][A][BCE][BCE][BCE][H][DH][H][DH][G][G][DG]――――ddd·ddd＋―d··＋SAAAHBCEADGADHA注：带＋号的结点为初始状态；带―号的结点为终止状态G3-07.给定下列自动机：其中：开始状态：其中：开始状态：0终止状态：2aaa0bbb12(1)把此自动机转换为确定自动机DFA。(2)给出此DFA的正则表达式。解答：（1）：有状态矩阵如图：abab001201012－21212ab00,1212－212从而可得DFA如图：--02aaba101bbb极小化后：02babb1a（2）此DFA的正则表达式为：(aa*bb)(bab)*或a*b（bab）*。4-13.消除下列文法G[E]的左递归。E→E-T∣TT→T/F∣FF→(E)∣i解答：消除文法G[E]的左递归后得到：E→TE’E’→-TE’∣εT→FT’T’→/FT’∣εF→(E)∣i4-14.在LL(1)分析法中,LL分别代表什么含义?答:第一个L代表从左到右的扫描，第二个L代表每次进行最左推导。4-15.自顶向下分析思想是什么？答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。4-16.自顶向下的缺点是什么？答：在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。4-17.LL（1）文法的定义是什么？答：一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A的两个不同产生式，A→α,A→β；满足SELECT(A→α)∩SELECT(A→β)=Ф。其中，α、β不能同时ε。4-18.什么是文法的左递归？答：一个文法含有下列形式的产生式之一时：1)A→Aβ，A∈VN，β∈V*2)A→Bβ，B→Aα，A、B∈VN，α、β∈V*则称该文法是左递归的。4-19.递归下降法的主要思想是什么？答：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。5-19.自底向上分析法的原理是什么？答：在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。5-20.简单优先方法基本思想是什么？答：简单优先方法基本思想是首先规定文法符号之间的优先关系和结合性质，然后在利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定句型的“句柄”并进行归约。5-21.三种优先关系的定义是什么？答：三种优先关系的定义是：1.sisj当且仅当存在形如下面的产生式U→…SiSj…2.sisj当且仅当存在形如下面的产生式U→…SiW…的生产式，且有WSj3.sisj当且仅当存在形如下面的产生式U→…VW…的生产式,且有VSi和WSj5-22.如何确定简单优先文法的句柄？答：设S1S2…Sn是简单优先文法的规范句型，其子串SiSi+1…Sj是满足下列条件的最左子串：Si-1Si

SiSi+1……Sj-1Sj

SjSj+1则SiSi+1…Sj定是S1S2…Sn的句柄。Z→CSC→ifEthenZ→CSC→ifEthenS→A＝EE→E∨AE→AA→i其中：Z、C、S、A、E∈VN；if、then、＝、∨、i∈VT构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。构造其SLR（1）分析表。解答：1.首先拓广文法：在G中加入产生式0．Z′→Z，然后得到新的文法G′，再求G′的识别全部活前缀的DFA：II0：Z′→.ZZ→.CSC→.ifEthenI1：Z′→Z.I2：Z→C.SS→.A＝EA→.iI3：C→if.EthenE→.E∨AE→.AA→.iI4：Z→CS.I5：S→A.＝EI6：A→i.I7：C→ifE.thenE→E.∨AI9：S→A＝.EE→.E∨AE→.AA→.iI10：C→ifEthen.I11：E→E∨.AA→.iI12：S→A＝E.E→E.∨AI13：E→E∨A.CCSiAi＝iEAZI0I1I6I5I2I3I7I9I12I13I11I10I8I4A∨then∨iifEA2．Follow(Z)＝{#}Follow(C)＝{i}Follow(S)＝{#}Follow(E)＝{#,∨,then}Follow(A)＝{＝,#,∨,then}则可构造SLR（1）分析表为：ACTIONGOTO0ifthen＝∨i#ZCSEA0S3121OK2S6453S6784r15S96r6r6r6r67S10S118r5r5r59S612810r211S61312S11r313r4r4r45-24.设有文法G[S]：SS→aAA→AbA→bI1:S′→S.I1:S′→S.I0:S′→.SS→.aAI2:S→a.AA→.AbA→.baI3:S→aA.A→A.bAI4:A→Ab.A→b.bbS解答：(1).首先拓广文法：在G中加入产生式0.S′→S，然后得到新的文法G′:0.S0.S′→S1.S→aA2.A→Ab3.A→b(2).再求G′的识别全部活前缀的DFA：6-07.语法制导翻译方法的基本思想是什么?答：在语法分析过程中，每当使用一条产生式进行推导或归约时，就执行该产生式所对应的语义动作进行属性计算，完成对输入符号串的翻译。6-08.何谓“语法制导翻译”?答：在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。6-09.在一个属性文法中，对应于每个产生式A→a都有一套与之相关联的语义规则，每条规则的形式为b：＝f（c1,c2…，ck），其中对于b的要求是什么？答：语义规则中的左部属性变量b被规定为只能是下述两种变量：对应产生式左部符号的综合属性变量；对应产生式右部符号的继承属性变量。6-10.给定文法及相应的翻译方案：SS→bTc{print(“0”)}S→a{print(“1”)}T→R{print(“2”)}R→R/S{print(“3”)}R→S{print(“4”)}为该文法设计翻译方案，使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出串：SbSbcRRS/SaRSRSRbcT//TbcT解：给出句型bR/bTc/bSc/ac的语法树如右图：则对于句型bR/bTc/bSc/ac,处理完该句型后输出是：4245130341246-10.给定文法及相应的翻译方案：)EEEETF()ETiTTFFTFT()+**EET+E→E+T{print(“5”)}E→T{print(“4”)}T→T*F{print(“3”)}T→F{print(“2”)}F→(E){print(“1”)}F→i{print(“0”)} 对于句型T+(T*(F+T)*i),处理完该句型后输出是什么？解：给出句型T+(T*(F+T)*i)的语法树如右图：则对于句型T+(T*(F+T)*i),处理完该句型后输出是：4245130341247-05.常用的中间语言种类有哪几种？答：有逆波兰式、三地址代码、抽象语法树和DAG。7-06.给定下列中缀式，分别写出等价的逆波兰表示(运算符优先级按常规理解)。(1)―a≤b∧a＞0∨b＜0解答：逆波兰表示为：a―b≤a0＞∧b0＜∨。(2)a―(a*b―d)*(a―b*d)/d解答：逆波兰表示为：aab*d―abd*―*d/―。(3)―a＋b≤0∨a＜0∧(a―b)>2解答：逆波兰表示为：a―b＋0≤a0＜ab―2＞∧∨。(4)a*(b*c―a)≤b＋c∧d解答：逆波兰表示为：abc*a―*bc＋≤d∧。7-07给定下列中缀式，分别写出等价的后缀式和