复习题(软件2012)

一．令文法为ETETETTFTFTFFEi|||*|/()|（1）给出i+i*i、i*(i+i)的最左推导和最右推导；（2）给出i+i+i、i+i*i、i-i-i的语法树。最左推导:EETTTFTiTiTFiFFiiFiiiETTFFFiFiEiETiTTiFTiiTiiFiii********()*()*()*()*()*()*()最右推导:EETETFETiEFiEiiTiiFiiiiiETFTFFFEFETFEFFEiFTiFFiFiiiii**********()*()*()*()*()*()*()*()语法树：EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*ii+i+ii+i*ii-i-i考虑文法G(E):E→E+T|TT→T*F|FF→(E)|i（1）给出句型E+F*F的语法树；（2）给出以上句型的的短语、直接短语、句柄。E=E+T=E+T*F=E+F*FEE+TT*FF由上图知：短语：F,F*F,E+F*F直接短语：F句柄：F二．构造下列正规式相应的NFA。1求1(0|1)*00的状态最少的DFA。解：1)得到NFAX12Y001012）NFA转换成DFA状态转换矩阵为：II0I1{X}---{1}{1}{1,2}{1}{1,2}{1,2,Y}{1}{1,2,Y}{1,2,Y}{1}重新命名后为：表格1S010--11212313313)DFA的化简例如：将下图最小化。bbaabaabbaaa最小化：bbaab五．令文法G1为：E-E+T|TT-T*F|FF-(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：EETETF*短语:E+T*F,T*F,直接短语:T*F句柄:T*FE-E+T|TT-T*F|FF-(E)|i句型（E+T）*i+F指出这个句型的所有短语、直接短语和句柄、素短语、最左素短语短语：E+T(E+T)i(E+T)*i(E+T)*i+FF直接短语:E+TiF素短语:iE+T最左素短语:E+T1、名词解释：句柄：一个句型的最左直接短语称为这个句型的句柄。最左素短语：包括至少一个终结符号，且除自身之外不包含其它素短语的短语称作素短023145012语。某句型最左边的那个素短语，称为最左素短语。六．给出下面表达式的逆波兰表示（后缀式）七．将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。三元式序列:(1)+,a,b(2)@,(1),-(3)+,c,d(4)*,(2),(3)(5)+,a,b(6)+,(5),c(7)-,(4),(6)间接三元式序列:三元式表：(1)+,a,b(2)@,(1),-(3)+,c,d(4)*,(2),(3)(5)+,(1),c(6)-,(4),(5)间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1)+,a,b,1T(2)@,1T,-,2T(3)+,c,d,3T(4)*,2T,3T,4T(5)+,a,b,5T(6)+,5T,c,6T(7)-,4T,6T,7T八．按照表7.3产生三地址代码的属性文法，自下而上把赋值句A:=B*(-C+D)翻译成四元式。步骤输入串栈PLACE四元式(1)A:=B*(-C+D)(2):=B*(-C+D)iA(3)B*(-C+D)i:=A-(4)*(-C+D)i:=iA-B(5)*(-C+D)i:=EA-B(6)*(-C+D)i:=EA-B(7)(-C+D)i:=E*A-B-(8)-C+D)i:=E*(A-B--(9)C+D)i:=E*(-A-B---(10)+D)i:=E*(-iA-B---C(11)+D)i:=E*(-EA-B---C(@,C,-,T1)(12)+D)i:=E*(EA-B--T1(13)D)i:=E*(E+A-B--T1-(14))i:=E*(E+iA-B--T1-D(15))i:=E*(E+EA-B--T1-D(+,T1,D,T2)(16))i:=E(EA-B--T2(17)i:=E*(E)A-B--T2-(18)i:=E+EA-B-T2(*,B,T2,T3)(19)i:=EA-T3(:=,T3,-,A)(20)A产生的四元式：(@,C,-,T1)(+,T1,D,T2)(*,B,T2,T3)(:=,T3,-,A)备注:本类题目不需要写出详细过程，只要会用抽象语法树写出四元式即可。九．试把以下程序划分为基本块并作出其程序流图。1、划分基本块的算法：（1）先求出四元式程序中各个基本块的入口：①程序的第一条语句；⑵能由条件转移语句或无条件转移语句转移到的语句；③紧跟在条件转移语句后面的语句。（2）对以上求出的每一入口语句，构造其所属的基本块。它是由该入口语句到另一入口语句，或到一转移语句，或到一停语句之间的语句序列组成的。（3）凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，可把它们从程序中删除。ReadCA:=0B:=1L1:A:=A+BIfB≥CgotoL2B:=B+1GotoL1L2:writeAhalt十.调用R0和R1是两个可使用的寄存器，T4是基本块出口之后的活跃变量。将下面基本块的中间代码序列生成目标代码。T1:=A+BT2:=C+DT3:=E-T2T4:=T1-T31.首先画出DAG图，对DAG图节点执行顺序进行排序，调整语句执行顺序T2：=C+DT3：=E-T2T1：=A+BT4：=T1-T32.然后进行翻译，目标代码序列为：LDR0,CADDR0,DLDR1,ESUBR1,R0LDR0,AADDR0,BSUBR0,R1STR0,T4注意寄存器的选择要求利用变量的待用信息来决定。选择题：1.将编译程序分成若干个“遍”是为了。a．提高程序的执行效率b．使程序的结构更加清晰c．利用有限的机器内存并提高机器的执行效率d．利用有限的机器内存但降低了机器的执行效率2.构造编译程序应掌握。a．源程序b．目标语言c．编译方法d．以上三项都是3、变量应当。a．持有左值b．持有右值c．既持有左值又持有右值d．既不持有左值也不持有右值4、编译程序绝大多数时间花在上。a．出错处理b．词法分析c．目标代码生成d．管理表格5、不可能是目标代码。a．汇编指令代码b．可重定位指令代码c．绝对指令代码d．中间代码6、使用可以定义一个程序的意义。a．语义规则b．词法规则c．产生规则d．词法规则7、词法分析器的输入是。a．单词符号串b．源程序c．语法单位d．目标程序8、中间代码生成时所遵循的是-。a．语法规则b．词法规则c．语义规则d．等价变换规则9、编译程序是对。a．汇编程序的翻译b．高级语言程序的解释执行c．机器语言的执行d．高级语言的翻译10、编译程序各阶段的工作都涉及到。a．语法分析b．表格管理c．出错处理d．语义分析e．词法分析11、编译程序工作时，通常有阶段。a．词法分析b．语法分析c．中间代码生成d．语义检查e．目标代码生成12、文法G：S→xSx|y所识别的语言是。a.xyxb.(xyx)*c.xnyxn(n≥0)d.x*yx*13、文法G描述的语言L(G)是指。a.L(G)={α|S+⇒α,α∈VT*}b.L(G)={α|S*⇒α,α∈VT*}c.L(G)={α|S*⇒α,α∈(VT∪VN*)}d.L(G)={α|S+⇒α,α∈(VT∪VN*)}14、有限状态自动机能识别。a.上下文无关文法b.上下文有关文法c.正规文法d.短语文法15、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。a.若f(a)g(b)，则abb.若f(a)g(b)，则abc.a~b都不一定成立d.a~b一定成立16、如果文法G是无二义的，则它的任何句子α。a.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导和最右推导必定相同d.可能存在两个不同的最左推导，但它们对应的语法树相同17、由文法的开始符经0步或多步推导产生的文法符号序列是。a.短语b.句柄c.句型d.句子18、文法G：E→E+T|TT→T*P|PP→(E)|i则句型P+T+i的句柄和最左素短语为。a.P+T和ib.P和P+Tc.i和P+T+id.P和T19、文法G：S→b|∧(T)T→T,S|S则FIRSTVT(T)。a.{b,∧,(}b.{b,∧,)}c.{b,∧,(,，}d.{b,∧,),，}20、产生正规语言的文法为。a.0型b.1型c.2型d.3型21、采用自上而下分析，必须。a.消除左递归b.消除右递归c.消除回溯d.提取公共左因子22、在规范归约中，用来刻画可归约串。a.直接短语b.句柄c.最左素短语d.素短语23、有文法G：E→E*T|TT→T+i|iEE*TTT+iT+ii6i281句子1+2*8+6按该文法G归约，其值为。a.23B.42c.30d.1724、规范归约指。a.最左推导的逆过程b.最右推导的逆过程c.规范推导d.最左归约的逆过程25.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位是_______。A字符B单词C句子D句型26．编译程序前三个阶段完成的工作是________。A词法分析、语法分析和代码优化B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成D词法分析、语法分析和代码优化27．对应Chomsky四种文法的四种语言之间的关系是AL0L1L2L3BL3L2L1L0CL3=L2L1L0DL0L1L2=L328.给定文法G:A→Ab|cc，试问在下面的符号中,为该文法句子的是______.AccbbBbcbccCbccbccDcbbcc29．属于自上而下分析法的是（）ALL（1）BLR（0）CSLRD算符优先30．在自下而上的语法分析中，应从开始分析。A最左素短语B句子C文法的开始符号D句柄二、填空题1、解释程序和编译程序的区别在于是否生成目标程序。2、编译过程通常可分为5个阶段，分别是词法分析、语法分析、中间代码生成、代码优化和目标代码生成。3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为目标代码程序。4、编译程序是指将高级语言源程序翻译成等价的低级语言程序的程序。5、编译程序是一种常用的＿翻译软件。6、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为三个阶段＿＿＿＿＿、＿＿＿＿＿、＿＿＿＿＿。7、文法G产生的一切句子的全体是该文法描述的语言。8、最右推导亦称为＿＿＿＿。9、语法分析方法大致上可分为两大类＿＿＿＿和＿＿＿＿。递归子程序方法属于＿＿＿＿。10、表达式—a+b*（—c+d）的逆波兰式为＿＿＿＿。11、自顶向下语法分析方法会遇到的主要问题有＿＿＿＿＿和＿＿＿＿＿。12、LL（1）分析法中，第一个L的含义是＿＿＿＿＿，第二个L的含义是＿＿＿＿＿，“1”的含义是＿＿＿＿＿。13．确定的有穷自动机是一个五元组、，通常表示为DFA=(K,∑,M,S,Z)。14．所谓最右推导是任何一步都是对最右非终结符进行替。15．语法分析器的任务是分析一个文法的句子结构。16．如果一个文法的任何产生式的右部都不含有相邻的非终结符，则这种文法称为算符文法。17．进行确定的自上而下语法分析要求语言的文法是无左递归、公共左因子18．根据优化对象所涉及的程序范围，代码优化分局部优化、循环优化、全局优化1.给出下述文法对应的正规式（7分）S→0A|1BA→1S|1B→0S|02.已知文法G(E)：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是该文法的一个句型，并指出该句型的所有短语、直接短语和句柄。（8分）3.设有文法G[S]：SaBc|bABAaAb|bBb|ε构造其LL(1)分析表，First(S)={a,b}Fir