华师网络2014年9月课程考试《编译原理》练习测试题库及参考答案

华中师范大学网络教育学院《编译原理》练习测试题库及参考答案一、填空若源程序是用高级语言编写的目标程序是 则其翻译程序称为编译序。词法分析和语法分析本质上都是对源程序的 进行分析。如果源语言(编写源程序的语言)是高级语言而目标语言是某计算机的汇编言或机器语言，则这种翻译程序称为 。对编译程序而言，输入数据是 ,输出结果是 。 ，是构成语言文法的单词，是语法成分的最小单位。由PL／0的EBNF可知语言可看成是PASCAL语言的子集，它的编译序是一个 。由于PL／0编译程序采，所以语法分析过程BLOCK是整个编译程的核心。用语法图描述语法规则的优点是 、 。每个非终结符是一个语法成分在书写语言程序时并不出现它是由 和 、或终结符串定义的。PL／0的目标程序为假想栈式计算机的汇编语言，与具体计算机 。PL／0的编译程序和目标程序的解释执行程序都是用 书写的因此PL／0语言可在配备 的任何机器上实现。PL／0编译程序是用PASCAL语言书写的，整个编译程序(包括主程序)是由 个嵌套及并列的过程或函数组成当源程序编译正确时，PL／0编译程序自动调用 ，对目标代码行解释执行，并按用户程序要求输入数据和输出运行结果。由于对某些非终结符可以递归定义，这就使得 可用有穷的文法述。 定的文法规则。PL／0编译程序的语法分析采用了 。语法分析程序除总控外主要有两大部分的功能，即 和 .PL／0的词法分析程序GETSYM，是一个独立的过程，其功能是为 提供单词用的，是 的基础，它把输入的字符串形式的源程序分割成一个个单词符号。每个过程应有过程首部以定义局部于它自己过程的常量变量和过程标识符也称 。词法分析程序GETSYM将完成的任务有: ,识别保留字,拼数拼复合词,输出源程序.如果一个PL／0语言的单词序列在整个语法分析中，都能逐个得到匹配，到 ，这时就说所输入的程序是正确的。若要构造程序设计语言的编译程序，则首先要对程序设计语言本身有较为精确的描述而关于程序设计语言的描述将涉及 语义和 三个方面23.凡是具有某种特殊性质的客体的聚合，都可称为 。如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为 ，记为φ。设有集合A和B，如果A和B有相同的元素，则称这两个集合是 .设AB为任意两个集合由所有属于集合A或属于集合B的元素组成的集合叫做集合A与B的 ．设A、B为任意两个集合，由所有用于集合A且属于集合B的元素组成的合，称为集合A与B的 . E。AAAA的 .由两个按一定次序排列的客体组成的序列，称为 .ABA个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的 .在集合X上的关系如对任意均有则称关系R是 。XR，如果合(x，y)∈R，便必有(y，x)∈R，R是 。在集合X上的关系R，如果合(x，y)∈R且(y，z)∈R，必有(x，z)则称关系R是 。35P={（1，2（3，4（2，2）}Q={4，7（2，9（3，1）}则P·Q= 符号串与符号组成顺序 ，如符号串ab ba，符号申001也 010。假设G是一个文法，S是文法的开始符号，如果S=>*x,则称x是 。文法G产生的 的全体是该文法描述的语言39.一个文法G[Z]若存在推导序列Z=>+··Z··,则称G(z)是 文法，这类文法所产生的句子有 个40.乔姆斯基把文法分成 类型.四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是 .最右推导常被称为 。由规范推导所得的句型称为 。文法的二义性和语言的二义性是两个 的概念。对于上下文无关文法， 是句型推导过程的几何表示。直接短语也称 .每棵语法树的叶子组成一个 .每棵子树的叶子组成一个 .每棵简单子树的叶子组成一个 .最左边简单子树的叶子组成 .一个句型的最左直接短语称为该句型的 。关于句型或句子的直接推导"=>"和推导实际上均可视为符号串之间系，而且推导"=>+"为直接推导"=>"的 。 BNF某条规则U→u中的左部符号U(U不是识别符)，不在所属文法的任何其规则右部出现那么这条规则在推导中不起作用即所有句子的推导始终不会到此规则，显然这种规则是多余的。也称这种非终结符为 .从文法的某个非终结符号U推不出终结符号串，显然，所有含有U的规则多余的。也称这种非终结符为 。LL∪{εLε}分别是上下文有关语言、 和正规语言。设有文法G，对于其中某一非终结符号U可能作出一些不同推导U=>+其中S叫头符号由于推导不同由U产生的头符号S也可能不同这些头符S构成的集合，称为U的推导的 .一个上下文无关文法G包括四个组成部分依次是： , , , .11文法所描述的语言是 的集合。词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲中，这个缓冲区称 。二、选择编译程序是一种常用的 软件A.应用 B.系统 C.工具 D.测试在使用高级语言编程时首先可通过编译程序发现源程序的全部 错误部分 错误。语法B.语义 C.语用 D.运行编译程序生成的目标程序 是机器语言的程序。一定 B.不一定C.某种情况下一定D.某种情况下不一4.编译程序生成的目标程序 是可执行的程序。A.一定 B.不一定 C.某种情况下一定D.某种情况下不一5.一个语言的文法是 .A．惟一的 B．不惟一的 C.个数有限的 D.无限的6.巴科斯-诺尔范式(即BNF)是一种广泛采用的 的工具A．描述规则 B.描述语言 C．描述文法 D．描述句子r=(a|b|c)(x|y|z)L（r）中元素为个（）A．9B．6C．18 D．278、正则集合L={an|n≧0}相应的正则表达式是（）A．a*B．a+C．aa*D．aa+编译过程中扫描器的任务包括 。①组织源程序的输入②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出⑧删除注解④删除空格及无用字符⑤行计数、列计数⑥发现并定位词法错误⑦建立符号表B．②③④⑥⑦C．①②③④⑥⑦ D．①②③④⑤⑥⑦10、编译过程中，语法分析器的任务是 。分析单词是怎样构成的c.分析语句和说明是如何构成程序的d.分析程序的结构A.bc Bd C．bcd D．abcd、语法分析的常用方法是 a.自顶向下b.自底向上 c.自左向右d.自右向B．ab C．cd D．abc12、编译程序中的语法分析器接受以 为单位的输入，并产生有关信供以后各阶段使用。表达式 B．产生式 C．单词 D．语句13、LL(1)文法的条件是 。U->Xl|X2„|XnFIRST(Xi∩FIRST(Xj)=Φ，(≠j)BU->Xl|X2|„|XnXi=>*ε)FOLLOW(U)=ΦC．A和BD．都不是14、一个右线性文法G一定是（）A．LL（1）文法C．SLR（1）文法B．LR（1）文法D．上述三者都不是15、算符文法是指 的文法。26U-„VW„的规则(，，W∈VN)②终结符号集VT中任意两个符号对之间至多有一种优先关系成立⑧没有相同的规则右部④没有形如U->ε的规则B．①② C．①②③ 16、算符优先文法是指 的文法。U-„VW„的规则(，，W∈VN)②终结符号集VT中任意两个符号对之间至多有一种优先关系成立⑧没有相同的规则右部④没有形如U->ε的规则A.①② B．①②③ C.①②③④ D．①②④17、下列文法G[S]的句型aR／aSb／aTb／,b 的最左素短为 S->aTb|，T->RR->R／S|SA.aTb B.aSb C.S D.R／18算符优先分析法每次都是对 进行归约简单优先分析法每次都是对柄进行归约。A．最左短语 B.简单短语 C.最左素短浯 D．素短19、xab+cde-*f/:=是赋值语句( )相应的后缀式A．x:=a+b+c*d-e/f B．x:=a+(b+c)*d-e/fC．x:+a+b+c*(d-e)/f 20、LR(K)方法是 。A．从左到右分析，每次走K步的一种编译方法B．从左到右分析，共经过K步的一种编译方法C．从左到右分析，每次向前预测K步的一种编译方法D．从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法21、下面三个文法中，为SLR(1)文法的是 。G1：P->PaP|bG2：P->bPb|cPc|b|cG3：P->bPb|bPc|d仅Gl B．仅G2 C．仅G3 D．G2和22、有下列文法：11S->Pa|Pb|cP->Pd|Se|f该文法是 。文法 B.SLR(1)文法C.a和b D.都不是23．代码优化的主要目标是( ②如何减少目标程序运行所需的空间③如何协调①和②④如何使生成的目标代码尽可能短A①② B①②③ C①②④ D ①②③④24、设文法G（S为其开始符号）产生式如下：S→aSb|ab|G是一个（）A．LR（1）文法B．SLR（1）文C．三型文法 D．二型文法在编译程序采用的优化方法中， 是在循环语句范围内进行的。12①合并已知常量 ②删除多余运算，③删除归纳变量 ④强度削弱⑤代码外提A①④ B①⑤ C①④⑤ D③④⑤合并表达式中常量运算的目的是 。12①合并常量，使表达式中的常量尽可能少②合并常量，使表达式尽可能简短③将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所有这种常量运算，使得生成的代码指令尽可能少A① B② C③ D①②③下面的程序段可以进行哪些优化 。i：=1j：=l0read L：x：=x*ij*iz：=writeji：=i+1ifi<100 goto halt①合并已知常量 ②删除多余运算③删除归纳变量 ④强度削弱⑤代码外提可选项有：A．①④ B①⑤C，①④⑤D．③④⑤属于低级语言的是（）AFortran B.Pascal C.Lisp DMasmoct是字母表{0，1，…，7}C号整规表达式是（。A.(oct)8 B.(oct)* C.(oct)+ D.(oct)#采用（）实现三地址代码时，不利于对中间代码进行优化。A.四元式B.间接三元式C.三元式D.有向无循环图一个正规语言只能对应( A一个正规文法；B一个最小有限状态自动机；C.一个下推自动机D.一个确定的有限自动机文法G[A]：A→εA→aBB→AbB→a是( A正规文法 B二型文法C.上下无关文法 D.不确定下面说法正确的是( )：ASLR（1）LALR（1）BLR（1）LALR（1）文法一个上下文无关文法消除了左递归，提取了左公共因子后是满足法的( )：A．必要条件BC.充分条件D．无法确定PL/0语言的目标程序解释执行时用到的数据对象有( A目标代码CODEBTABLECDSPL/0语言编译时产生或使用的数据对象不包括( A目标代码CODEBCSDWORD37、编译程序是一种常用的 软件A.应用 B.系统 C支撑 D.自动化38在使用高级语言编程时首先可通过编译程序发现源程序的全部 错和部分语义错误。A.语法 B语义 C.语用 D.运行39.LR（1）LALR（1）A则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突D不存在冲突40、运算符与运算对象类型不符属于 。A.语法错误 B.语义错误 C.语用错误 D.规41．语言是A．句子的集合 B．产生式的集合C．符号串的集合 D．句型的集42．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化43．一个句型中称为句柄的是该句型的最左A．非终结符号 B．短语 C．句子 D．直接短44．下推自动机识别的语言是A．0型语言 B．1型语言C．2型语言 D．3型语言扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含A．字符 B．单词 C．句子 D．句46．对应Chomsky四种文法的四种语言之间的关系是A．L0L1L2L3 B．L3L2L1L0C．L3=L2L1L0 D．L0L1L2=L3词法分析的任务是A．识别单词 B．分析句子的含义C．识别句子 D．生成目标代48．常用的中间代码形式不含A．三元式 B．四元式 C．逆波兰式 D．语法树代码优化的目的是A．节省时间 B．节省空间C．节省时间和空间 D．把编译程序进行等价交50．代码生成阶段的主要任务是A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言CD．把汇编语言翻译成机器语言语言是A．句子的集合 B．产生式的集合C．符号串的集合 D．句型的集52．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化53．一个句型中称为句柄的是该句型的最左A．非终结符号 B．短语 C．句子 D．直接短54．下推自动机识别的语言是A．0型语言 B．1型语言C．2型语言 D．3型语言扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含A．字符 B．单词 C．句子 D．句56．对应Chomsky四种文法的四种语言之间的关系是A．LLLL B．LLLL0 1 2 3 3 2 1 0C．L=LLL D．LLL=L3 2 1 0 0 1 2 3词法分析的任务是A．识别单词 B．分析句子的含义C．识别句子 D．生成目标代58．常用的中间代码形式不含A．三元式 B．四元式 C．逆波兰式 D．语法树代码优化的目的是A．节省时间 B．节省空间C．节省时间和空间 D．把编译程序进行等价交60．代码生成阶段的主要任务是A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言CD．把汇编语言翻译成机器语言三、名词解释题词法分析LL(1)文法语法树LR(0)分析器语言和文法四、判断题1．正规文法产生的语言都可以用上下文无关文法来描述。„„„„„„„„( )„„„„„„„„„（ ）„„„„„„„（ ）„„„„„„„„„„„„„„„„（ ）（ ）． 一 个 LL( l) 文 法 一 定 是 无 二 的。„„„„„„„„„„„„„„„„„„( )．在规范规约中用最左素短语来刻划可归约串。„„„„„„„„„„„„( )．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。„„„„„( )9．编译程序是对汇编程序的翻译。 „„„„„„„„„„„„„„（ ）10 ．逆波兰法表示的表达式亦称前式。„„„„„„„„„„„„„„„„„( )五、简答题有人认为编译程序的五个组成部分却一不可，这种看法正确吗？解释程序定义哪些寄存器?PL／0LIT?LOD?STO?CAL?INT?JMP?JPC?OPR?5S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。何谓优化？按所涉及的程序范围可分为哪几级优化？目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。0?关系有哪些基本性质？解释字母表,符号,符号串,符号串的长度,符号串联结？自下而上分析算法的基本思想是什么？s::=Qc|cQ::=Rb|bR::=Sa|a试求HARD(S),HARD(Q),HARD(R).BNF范式表示下述文法以消去ε规则：S::=aABb|abA::=Aab|εB::=Aa|a考虑下面程序…………Vara：integer；ProcedureS(X)；VarX：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．a么？G[I]:8I->I1/I0/Ia/Ic/a/b/c判断下面符号串中哪些是该文法的句子.ab0(2)a0c01(3)aaa(4)bc10(5)aabc(6)bbca为了正确地对源程序进行编译，不允许文法有二义性，那么怎样才能排除文法的二义性呢?9什么是简单子树？什么是子树？什么是句型的分析？自下而上分析算法的基本思想是什么？s::=Qc|cQ::=Rb|bR::=Sa|a试求HARD(S),HARD(Q),HARD(R).编译程序和高级语言有什么区别?编译程序的工作分为那几个阶段?简述自下而上的分析方法。简述代码优化的目的和意义。六、综合题Whilea＞0∨b＜0 BeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；翻译成四元式序列。设布尔表达式的文法为E→E(1)∨E(2)E→E(1)∧E(2)E→i假定它们将用于条件控制语句中，请改写文法，使之适合进行语法制导翻译和实现回填；写出改写后的短个产生式的语义动作。G(S)：S→(L)|aL→L，S|S消除左递归和回溯；FIRSTFOLLOW；G:S'->#S#S->D(R)R->R;P|pP->S|iD->i计算文法中每个非终结符的FIRSTVT集和LASTVT集 。A[i,j]:=B[i,j]C[A[k,l]]D[i+j]6、设布尔表达式的文法为E→E(1)∨E(2)E→E(1)∧E(2)E→i假定它们将用于条件控制语句中，请改写文法，使之适合进行语法制导翻译和实现回填；7（8）PASCALwhilea>bdoifa>0thena:=a-1elsea:=a+1;将该语句翻译成逆波兰式；thenFIRST集？G：SaSbS|aS|d是二义性文法。对于文法baSb短语和句柄？句型baSb的语法树如图五(2)所示。SA Bb B S ba图五(2)句型baSb的的语法树11．设有非确定的有自限动机NFA 中：(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}转换距阵和状态转换图。华中师范大学网络教育学院《编译原理》练习测试题库参考答案一、填空机器语言程序或汇编程序结构编译程序源程序，目标程序。终结符编译解释执行系统一趟扫描方法直观、易读终结符和非终结符串无关PASCAL语言12.18解释执行程序无穷的句子集语法分析自顶向下的递归子程序法说明部分的处理,程序体部分的处理语法分析,语法分析局部量滤空格,识别标识符,输出源程序程序结束符语法,语用集合空集相等的并集交集全集幂集序偶笛卡尔乘积自反的对称的传递的35.（1，9（3，7（2，5）}有关,不同于,不同于句型句子39.(1)递归 (2)无数四种上下文无关的规范推导规范句型不同语法树简单短语句型短语简单短语句柄句柄传递闭包语法图不可达到的不可终止的上下文无关语言头符号集合终结符号，非终结符号，开始符号，产生式由文法的识别符推出的所有终结符号串输入缓冲区二、选择1.B 2.A 3.B 4.B 5.B 6.B 7.B 8.A 9.D 10.C11.B 12.C 13.C 14.A 15.A 16.D 17.B 18.D 19.A 20.D21.C 22.B 23.B 24.D 25.D 26.D 27.C 28.D 29.D 30.C31.B 32.B 33.A 34.A 35.A 36.C 37.B 38.A 39.B 40.A41.A 42.C 43.D 44.C 45.B 46.B 47.A 48.D 49.C 50.C51A 52C 53D 54C 55B 56B 57A 58D 59C 60C三．名词解释题从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。A|都满足下面两个条件：FIRST()FIRST()=*FIRST()FOLLOW(A)=。LL(1)文法LL表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。句子的树结构表示法称为语法树(语法分析树或语法推导树)。G=(VN，VT，P，S)G语法树。这棵树具有下列特征：S。V中的一个符号。AA1A2…AR，那么AA1A2…AR一定是P中的一条产生式。AAVN。wwG的句型；若w中仅含终结符号，则w为文法G所产生的句子。LR(0)每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。G定义为四元组的形式：N G=(V，V，P，N 其中：VN是非空有穷集合，称为非终结符号集合；VT是非空有穷集合，称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)这里，V∩V=，SV。V=V∪VG的字母表，它是出现N T N N T文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即L(G)={x|S*x，其中S为文法开始符号，且xV }T简单的说，文法描述的语言是该文法一切句子的集合。四判断题1× √ √ × √ √ 、× √ × 10、×五、简答题以，上述说法不对。答：不正确。编译程序的五个组成部分中，词法分析，语法分析，语义分析和没有优化部分的编译程序也能生成目标代码。指令寄存器,程序地址寄存器,栈顶寄存器,基址寄存器(1以校正。校正的方式就是补上逗号或分号。为止。LITLOD：STO：CAL：INT：6. 句型 归约规则句柄((a，a)，a)S→aa((S，a)，a)T→SS((T，a)，a)S→aa((T，S)，a)T→T，ST，S((S)，a)T→SS((T)，a)S→S(T)(T)(S，a)T→SS(T，a)S→aa(T，S)T→T，ST，S(T)S→(T)(T)S发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化。机器语言模块。应着重考虑的问题：如何使生成的目标代码较短；(3)如何充分利用指仅系统的的特点。逆波兰表示：abc*＋ab＋/d－三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。自反的 在集合X上的关系R，如对任意x∈X，均∈R，则称系R是自反的。非自反的在集合X上的关系R，如对任意x∈X，均有(x，x) R，则称系R是非自反。对称的 在集合X上的关系R，如果(x，y)∈R，便必∈R，则关系R是对称的。非对称的在集合X上的关系R，如果有(x，y)∈R丛x≠y，便必有(y，x)R，则称关系R是非对称的。传递的 在集合X上的关系R，如果合(x，y)∈R且(y，z)∈R，必有(x，z)∈R，则称关系R是传递的。13.元素的非空有穷集合。字母表中的元素。由字母表中的符号组成的任何有穷序列，惯用小写字母tuvxxyx的符号之后所得的符号串，叫xyxy。答：从所给符号串x并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图x归约到文法的识别符号x是文法的句子。HARD(S)={S,Q,R,a,b,c}HARD(Q)={S,Q,R,a,b,c}HARD(R)={S,Q,R,a,b,c}S::=aABb|abA::={ab}B::=Aa|a17传名：a＝12 传值：a＝618.(1)错误正确正确正确错误错误错误19.(1)在语义上加些限制，或者说加一些语法的非形式规定。这样做不必改变文法中原有的语法规则。(2)把排除二义性的规则合并到原有文法中，即构造一个等价的无二义性的文法G'。这样做，需要改造原有文法。只有单层分支的子树称为简单子树。由某一结点及其所有分支组成的部分，成为原语法树的一棵子树。程。x用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试xx句子。HARD(S)={S,Q,R,a,b,c}HARD(Q)={S,Q,R,a,b,c}HARD(R)={S,Q,R,a,b,c}用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。"对话"，随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。词法分析、语法分析和语义分析是对源程序进行的分析(端)，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序所谓自下而上分析法就是从输入串开始，逐步进行“归约”的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。28代码优化是尽量生成“好”一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。五、综合题每题10分，3题共30分1.解：(1)(j＞，a，0，5)(2)(j，－，－，3)(3)(j＜，b，0，5＝(4)(j，－，－，15)(5)(＋，×，1，T1)(6)(：＝，T1，－，×)(7)(j≥，a，0，9)(8)(j，－，－，12)(9)(－，a，1，T2)(10)(：＝，T2，－，a)(11)(j，－，－，1)(12)(＋，b，1，T3)(13)(：＝，T3，－，b)(14)(j，－，－，1)2.解：(1)E0→E(1)E→E0E(2)EA→E(1)E→EAE(2)E→i(2)E→E(1){BACKPATCH(E(1)·FC，NXQ)；E0·TC：＝E(1)·TC}E→E0E(2){E·FC：＝E(2)·FC；E·TC：＝MERG(E0·TC，E(2)·TC)}EA→E(1){BACKPATCH(E(1)·TC，NXQ)；E0·FC：＝E(1)·FC}E→EAE(2){E·TC：＝E(2)·TC；E·FC：＝MERG(EA·FC，E(2)·FC)E→i{E·TC：＝NXQ；E·FC：＝NXQ＋1；GEN(jn2，entry(i)，－0)；GEN(j，－，－，0)3(1)

S→(L)|aS’S’→S|εL→SL’L’→SL’|ε(2)FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,εFIRST(L)＝{(，a}}FOLLOW(S’)＝{#，，，)}FOLLOW(L)＝{)}FIRST(L’)＝{，，ε(3)}FOLLOW(L’〕＝{)}a，()＃SS→aS’S→(L)S’S’→SS’→εS’→SS’→ε S’→εLL→SL’L→SL’L’L’→εL’→ε4.(1)文法G中每个非终结符的FIRSTVT集和LASTVT集为FIRSTVT(s')={#} FIRSTVT(P)={i,()FIRSTVT(s)={(,i) FIRSTVT(D)={i}FIRSTVT(R)={;,(,i)(2)文法G中每个非终结符