《编译原理》考试试题及答案

编译原理考试试题及答案（附录）一、判断题：1. 一个上下文无关文法的开始符，可以是终结符或非终结符。（X ）2. 一个句型的直接短语是唯一的。（X ）3. 已经证明文法的二义性是可判定的。（X）4. 每个基本块可用一个DAG表示。（V ）5每个过程的活动记录的体积在编译时可静态确定。（V ）6.2型文法一定是3型文法。（ x ）7. 一个句型一定句子。（ X ）8. 算符优先分析法每次都是对句柄进行归约。（应是最左素短语）（ X ）9. 采用三元式实现三地址代码时，不利于对中间代码进行优化。（ V ）10. 编译过程中，语法分析器的任务是分析单词是怎样构成的。（x）11. 一个优先表一定存在相应的优先函数。（x）12. 目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。（）13. 递归下降分析法是一种自下而上分析法。（）14. 并不是每个文法都能改写成LL（1）文法。（）15. 每个基本块只有一个入口和一个出口。（）16. 一个LL（1 ）文法一定是无二义的。（）17. 逆波兰法表示的表达试亦称前缀式。（）18. 目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。（）19. 正规文法产生的语言都可以用上下文无关文法来描述。（）20. 一个优先表一定存在相应的优先函数。（）21.3型文法一定是2型文法。（）22. 如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。（）二、填空题：1. （ 最右推导 ）称为规范推导。2. 编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目 标代码生成）五个阶段。3. 如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（4. 从功能上说，程序语言的语句大体可分为（5. 语法分析器的输入是（），其输出是（6. 扫描器的任务是从（）中识别出一个个（）语句和（）。语句两大类。）。）。7. 符号表中的信息栏中登记了每个名字的有关的性质，如（&一个过程相应的DISPLAY表的内容为（9.一个句型的最左直接短语称为句型的（10. 常用的两种动态存贮分配办法是（）动态分配和11. 一个名字的属性包括（）和（）。12. 常用的参数传递方式有（），（13. 根据优化所涉及的程序范围，可将优化分成为（14. 语法分析的方法大致可分为两类，一类是（15. 预测分析程序是使用一张（）和一个16. 常用的参数传递方式有（竺竺等等。）。）。）动态分配。（）。），（）和（分析法，另一类是（）进行联合控制的。）三个级别。）分析法。），（）。）态;而且实际上至少要有一个（ ）态。17. 一张转换图只包含有限个状态,其中有一个被认为是（18. 根据优化所涉及的程序范围，可将优化分成为（ ），（ ）和（ ）三个级别。19. 语法分析是依据语言的（ ）规则进行。中间代码产生是依据语言的（ ）规则进行的。20. 一个句型的最左直接短语称为句型的（ ）。21. 一个文法G,若它的预测分析表M不含多重定义，则该文法是（）文法。22对于数据空间的存贮分配，FORTRAN采用（）策略，PASCAL采用（）策略。23. 如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。24. 最右推导亦称为（），由此得到的句型称为（）句型。25. 语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。26. 对于文法G,仅含终结符号的句型称为（）。27.所谓自上而下分析法是指（）28.语法分析器的输入是（），其输出是（）。29.局限于基本块范围的优化称（）。30.预测分析程序是使用一张（）和一个（）进行联合控制的。31.2型文法又称为（）文法；3型文法又称为（）文法。32.每条指令的执行代价定义为（）。33.算符优先分析法每次都是对（）进行归约。三、名词解释题：1. 局部优化2. 二义性文法3. DISPLAY 表4. 词法分析器5. 最左推导6. 语法7. 文法8. 基本块9. 语法制导翻译10. 短语11. 待用信息12. 规范句型13. 扫描器14. 超前搜索15. 句柄16. 语法制导翻译17. 规范句型18. 素短语19. 语法20. 待用信息21. 语义四、简答题：1写一个文法G,使其语言为不以0开头的偶数集。2. 已知文法G（S）及相应翻译方案SaAb print “1”Saprint “2”AAS print “3”Acprint “4”输入acab,输出是什么？3. 已知文法G（S）SbAaA(B | aBAa) 写出句子b(aa)b的规范归约过程。4. 考虑下面的程序： procedure p(x, y, z)； beginy:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A, A, B);Print A, Bend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出A, B的值是什么?5. 文法G(S)SdABAaA| aBBb| e 描述的语言是什么？6证明文法G(S)SSaS| e 是二义性的。7.已知文法G(S)SBAABS| dBaA| bS | c 的预测分析表如下abcd#SSBASBASBAAABSABSABSAdBBaABbSBc给出句子adccd的分析过程。&写一个文法 G,使其语言为 L(G) = albmclanbn|l=0, m=1, n=29. 已知文法G(S):Sa| (T) TT,S|S 的优先关系表如下：关系a()a.(.=.).请计算出该优先关系表所对应的优先函数表。10. 何谓优化？按所涉及的程序范围可分为哪几级优化？11. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？12. 一字母表= a, b，试写出工上所有以a为首的字组成的正规集相对应的正规式。13. 基本的优化方法有哪几种？14. 写一个文法G,使其语言为L(G) = abns| n015. 考虑下面的程序： procedure p(x, y, z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b, b, a);print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么?16. 写出表达式a+b*(c-d)/e的逆波兰式和三元序列。17. 证明文法G(A)AAA | (A)| &是二义性的。18. 令S = a,b，则正规式a*b|b*a表示的正规集是什么？19. 何谓DISPLAY表？其作用是什么？20. 考虑下面的程序： procedure p(x, y, z)；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b, a-b, a);print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么？21. 写一个文法G,使其语言为L(G) = anbncm| n0为奇数，m0为偶数22. 写出表达式a: = (b+c)*e+(b+c)/f的逆波兰式和三元序列。23. 一个文法G别是LL(1)文法的充要条件是什么？24. 已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左递归和提公共左因子。25. 符号表的作用是什么？符号表查找和整理技术有哪几种？五、计算题：1设文法G(S):S | a | (T)TT,S | S 消除左递归； 构造相应的FIRST和FOLLOW集合； 构造预测分析表2. 语句 if E then S(1) 改写文法，使之适合语法制导翻译；(2) 写出改写后产生式的语义动作。3. 设文法G (S)：S-(T) | aT-T+S | S(1) 计算 FIRSTVT 和 LASTVT；(2) 构造优先关系表。4. 设某语言的for语句的形式为for i:=E(i)to E do S其语义解释为i:=E(1)LIMIT:=E(2)again: if iV=LIMIT t henBeginS;i:=i1goto againEnd;(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作。5. 把语句while a0 then a:=a+1 else a:=a*3-1;翻译成四元式序列。6. 设有基本块D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有M还被引用，请写出优化后的四元序列。7. 已知文法G(S)S-a(T)T-T,S | S(1) 给出句子(a,(a,a)的最左推导；(2) 给出句型(T,S),a)的短语，直接短语，句柄。&对于C语言do S while E语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。9. 已知文法G(S)SaAcBeAAb| bBd(1) 给出句子abbcde的最左推导及画出语法树；(2) 给出句型aAbcde的短语、素短语。10. 设文法G(S):S(T) | aS | a TT,S | S 消除左递归和提公共左因子； 构造相应的FIRST和FOLLOW集合； 构造预测分析表。11. 把语句f X0 v 丫0then while X0 do X:=A*3 else Y:=B+3;翻译成四元式序列。12. 已知文法G(S)EE+T | TTT*F| FF(E)| i(1) 给出句型(i+i)*i+i的最左推导及画出语法树；(2) 给出句型(E+T)*i+F的短语，素短语和最左素短语。13. 设文法G (S)：ST | SvTTU |TaUUi |-U(1) 计算 FIRSTVT 和 LASTVT；(2) 构造优先关系表。参考答案一、是非题：1. X2.X3.X4.V5.V6.X7.X&X 9. V10.X11. X12. V13. X14. V15. V16. V17. X18. V19.V20. X21.V22.V二、填空题：1. （最右推导）2. （词法分析），（语法分析），（中间代码生成），（代码优化），（目标代码生成）3. （二义性的）4. （执行性），（说明性）5. （单词符号），（语法单位）。6. （源程序），（单词符号）7. （类型、种属、所占单元大小、地址）8. （现行活动记录地址和所有外层最新活动记录的地址）9. （句柄）10. （栈式），（堆式）11. （类型），（作用域）12. （传地址），（传值），（传名）13. （局部优化），（循环优化），（全局优化）14. （自上而下），（自下而上）15. （分析表），（符号栈）16. （传地址），（传值），（传名）17. （初），（终）18. （局部优化），（循环优化），（全局优化）19. （语法），（语义）20. （句柄）21. （LL（1）文法）22. （静态），（动态）23. （二义性文法）24. （规范推导），（规范）25. （自上而下），（自下而上）26. （句子）27. （从开始符号出发，向下推导，推出句子）28. （单词符号），（语法单位）29. （局部优化）30. （分析表），（符号栈）31. （上下文无关文法），（正规）32. （指令访问主存次数加1）33. （最左素短语）三、名词解释题：1. 局部优化局限于基本块范围的优化称。2. 二义性文法如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3. DISPLAY表-过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。4. 词法分析器执行词法分析的程序。5最左推导任何一步a=B都是对a中的最右非终结符替换。6. 语法一组规则，用它可形成和产生一组合式的程序。7. 文法描述语言的语法结构的形式规则。8. 基本块指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9. 语法制导翻译在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。十10. 短语令G是一个文法，S划文法的开始符号，假定aB是文法G的一个句型，如果有S=aA6且，则称B是句型aB相对非终结符A的短语。11待用信息如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。12. 规范句型由规范推导所得到的句型。13. 扫描器执行词法分析的程序。14. 超前搜索在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15. 句柄一个句型的最左直接短语。16. 语法制导翻译在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法叫做语法制导翻译。17. 规范句型由规范推导所得到的句型。18素短语素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19语法是组规则，用它可形成和产生一个合式的程序。20. 待用信息如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。21. 语义定义程序的意义的一组规则。四、简答题：1所求文法是GS:SAB |B A0AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2输出是42313. 句子 b(aa)b 的规范归约过程:步骤符号栈输入串动作0#b(aa)b#预备1#b(aa)b#移进2#b(aa)b#移进3#b(aa)b#移进4#b(Aa)b#归约5#b(Ma)b#移进6#b(Ma)b#移进7#b(Bb#归约8#bAb#归约9#bAb#移进10#S#接受4. 传地址 A=6,B=16传值 A=2,B=45. L(G)二danbm |n0, m三06. 证明：因为文法GS存在句子aa有两个不同的最左推导，所以文法GS是是二义性的。S=SaS=SaSaS=aSaS=aaS=aaS=SaS=aS=aSaS=aaS=aa7.句子 adccd 的分析过程：步骤符号栈输入串产生式0#Sadccd#1#ABadccd#S-BA2#AAaadccd#BaA3#AAdccd#4#Addccd#Ad5#Accd#6#SBccd#A-BS7#Scccd#Bc8#Scd#9#ABcd#Bc10#Acd#11#Ad#12#dd#Ad13#&所求文法是GS:S-ABAaAc | DD-bD | bB-aBb | aabb 9.11. 目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。 应着重考虑的问题：(1) 如何使生成的目标代码较短；(2) 如何充分利用寄存器，以减少访问内存次数；(3) 如何充分利用指令系统的特点。12. 正规式 a ( a | b )*。13. 删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值14. 文法 GS:S-aB | aB-bc |bBc15. 传值a=2传地址 a=1516. 逆波兰式: abcd-*e/+三元序列:op arg1 arg2(1)-cd(2)*b(1)(3)/(2)e(4)+a(3)17. 证明：因为文法GS存在句子()有两个不同的最左推导，所以文法GS是是二义性的。 A=AA=(A)A=()A=()A=AA=A=(A)=()18. (a*b|b*a)二a,b,ab,ba,aab,bba19. Display表：嵌套层次显示表 由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外 层过程的最新活动记录起始地址，display表就是用于登记每个外层过程的最新活动记录起始地址。20. 传地址 a=12 传值 a=521所求文法是GS:S-ACAaaAbb | abCccC | cc22. 逆波兰式 abc+e*bc+f/+:=三元序列oparg1arg2(1)+bc(2)*(1)e(3)+bc(4)/(3)f(5)+(2)(4)(6):=a(5)23. 一个文法G别是LL(1)文法的充要条件是：(1) FIRST(a) nFIRST(B) = (2) 如果 B=*&, FIRST(a) nFOLLOW(A)=24. 消除左递归SaFS | *aFSSf*aFS | &F+aF | +a提公共左因子，文法G(S)SaFS | *aFSS*aFS | &F+aFFF | e25. 作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况 主要技术：线性表，对折查找，杂奏技术。五、计算题： 1.(1)消除左递，文法变为GS：S | aTST | (T)S|e此文法无左公共左因子。(2)构造相应的FIRST和FOLLOW集合： FIRST(S) = a, , (, FOLLOW(S) = #, )FIRST(T) = a, , ( , FOLLOW(T) = FIRST(T) = , e , FOLLOW(F) = ) 构造预测分析表：aA()#SSaSAS(T)TTST，TST，TST，T，T，T，,ST，2. (1)Cif E t henS-CS(i)(2)Cif E then BACK(E.TC, NXQ); C.chain:=E.FCSCS(1) S.chain:=MERG(C.Chain, S(1). Chain)3. (1) FIRSTVT(S)=a, ( FIRSTVT(T)=+, a, (aLASTVT(S)=a, ) LASTVT(T)=+, a, )(2)a+()a.+.(.二.).4. (1) Ffor i:=E(1) to E(2) doSFS(1)(2) Ffor i:=E(1) to E(2) doGEN(:=, E(1).place, _, entry(i);F.place:=entry(i);LIMIT:=Newtemp;GEN(:=, E(2).place, _, LIMIT);Q:=NXQ;F.QUAD:=q;GEN(jW, ent ry(i), LIMIT, q+2)F.chain:=NXQ;GEN(j, _, _, 0)SFS(1)BACKPATCH(S(1).chain, NXQ);GEN(+, F.place, 1, F.place);GEN(j, _, _, F.QUAD);S.chain:=F.chain5. (1)(j, c, 0,(5)(4) (j,_,_,(8)(5) (+, a, 1, T1)(6) (:=, T1, _,a)(7) (j, _,_,(1)(8) (*, a, 13, T2)(9) (-, T2, 1, T3)(10) (:=, T3, _, a)(11) (j, _, _, (1)6. 优化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+207. 最左推导S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a) 短语(T,S),a)(T,S),a(T,S)T,Sa直接短语T,S句柄T,SSdo M S while M E1 1 2Mg(2)MgSdo M S while M E1 1 28. (1)M.quad=nestquad;backpatch(s.nextlist, M .quad); backpatch(E.truelist, M .quad);S.nextlist=E.falelist;9. (1) S=aAcBe=AAbcBe=abbcBe=abbcde(2) 短语: aAbcde, Ab, d 素短语: Ab, d10. (1) S(L) | aSSS |gFIRST(S)=a, (, g FIRST(L)=, g FOLLOW(S)=, ), # FOLLOW(L)= )LSL L,SL |g(2) FIRST(S)=a, ( FIRST(L)=a, ( FOLLOW(S)=, ), # FOLLOW(L)= )(3)()a#SS (L)S aSSSSSESSSESELLSLLSLL,SLLLE11. (1) (j, X, 0, (5)(2) (j, _, _, (3)(3) (j0, X, 0, (7)(6) (j, _, _, (7)(7) (*, A, 3, T1)(8) (:=, T1, _, N)(9) (j, _, _,(5)(10) (j, _, _,(13)(11) (+, B, 3, T2)(12) (:=, T2, _, Y)12. (1) E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+T =(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T =(i+i)*i+F=(i+i)*i+i(2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F素短语 i, E+T最左素短语 E+T13. (1) FIRSTVT(S) = V, A, i, - FIRSTVT(T) = A, i, -FIRSTVT(U)=i, -LASTVT(S) = V, A, i, - LASTVT(T)=A, i,-LASTVT(U)=i, -(2)iVAS.V.A.一、单项选择题 1将编译程序分成若干个“遍”是为了( B )A. 提高程序的执行效率B. 使程序的结构更加清晰C. 利用有限的机器内存并提高机器的执行效率D. 利用有限的机器内存但降低了机器的执行效率 2不可能是目标代码的是( D )A. 汇编指令代码B.可重定位指令代码C.绝对指令代码D.中间代码3. 词法分析器的输入是( B )456789101112131415A. 单词符号串B.源程序C.语法单位D.目标程序中间代码生成时所遵循的是( C )A.语法规则B.词法规则C.语义规则D.等价变换规则编译程序是对( D )A.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译词法分析应遵循( C )A.语义规则B.语法规则C.构词规则D.等价变换规则词法分析器的输出结果是( C )A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和属性值D.单词属性值 正规式Ml和M2等价是指(C )A. M1和M2的状态数相等B. M1和M2的有向弧条数相等C. Ml和M2所识别的语言集相等D. Ml和M2状态数和有向弧条数相等词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，( B )A. 词法分析器应作为独立的一遍B. 词法分析器作为子程序较好C. 词法分析器分解为多个过程，由语法分析器选择使用.D. 词法分析器并不作为一个独立的阶段如果 L(M1)=L(M2)，则 Ml 与 M2( A )A.等价B.都是二义的C.都是无二义的D.它们的状态数相等文法G： SxSx| y所识别的语言是(C )A. xyx B. (xyx)* c. xnyxn(n三0)d. x*yx*文法G描述的语言L(G)是指(A )A.L(G)二| S兰w V Jb.L(G)二| S =a,a g(Vu V )*T JTNC.L(G)二| S厶a,a g V Jd.L(G)二| S厶a,a g(Vu V )*T JT N有限状态自动机能识别( C )A. 上下文无关文法B. 上下文有关文法C.正规文法D.短语文法如果文法G是无二义的，则它的任何句子(A )A. 最左推导和最右推导对应的语法树必定相同B. 最左推导和最右推导对应的语法树可能不同C. 最左推导和最右推导必定相同D. 可能存在两个不同的最左推导，但它们对应的语法树相同由文法的开始符经0步或多步推导产生的文法符号序列是( C )A.短语 B.句柄 C.句型 D.句子16. 文法 G： EE+T|TTT*P|PP- (E)|i则句型P+T+i的句柄为(B )A.P+T B.P C.P+T+i D.i17. 文法 G： S-b|A|(T)T-TVS|S则 FIRSTVT(T) = ( C )A. b，A，( B. b，A，) C. b，A，(，V D. b，A，)，V 18. 产生正规语言的文法为( D )A.O型 B.1型 C. 2型 D. 3型19. 任何算符优先文法( D )优先函数。A.有一个 B.没有 C.有若干个D.可能有若干个20. 采用自上而下分析，必须( C )A.消除左递归B.消除右递归C.消除回溯D.提取公共左因子21. 在规范归约中，用( B )来刻画可归约串。A.直接短语B.句柄 C.最左素短语 D.素短语22. 有文法 G： E-E*T|TT-T+i|i句子1+2*8+6按该文法G归约，其值为(B )A.23B.42C.30D.1723. 如果文法是无二义的，那么规范归约是指( B )A.最左推导的逆过程B.最右推导的逆过程C.规范推导D.最左归约的逆过程24. 文法 G:S-S+T|TT-T*P|PP-(S)|i 句型P+T+i的短语有(B )A.i,P+T B.P,P+T,i,P+T+i C.P+T+i D.P，P+T25. 四元式之间的联系是通过( B )实现的。A.指示器 B.临时变量C.符号表 D.程序变量26. 后缀式ab+cd+ /可用表达式(B )来表示。a+b+c/dA.a+bc+d B.(a+b)(c+d)C.a+b(c+d) D.27. 使用间接三元式表示法的主要目的( A )A.便于优化处理B.便于表的修改C.节省存储空间D.生成中间代码更容易28. 表达式G AVB) A(CVD)的逆波兰表示为(B )A.n ABVACDV B. An BVCDVAC. ABVn CDVA D. An BVACDV二、判断题1. 一个确定有限状态自动机中，有且仅有一个唯一的终态。（X）2. 设R和S分别是字母表工上的正规式，则有L（R|S）=L（R）UL（S）。（V）3. 自动机Ml和M2的状态数不同，则二者必不等价。（X）4确定有限自动机以及非确定有限自动机都能正确地识别正规集。（V）5. 对任意一个右线性正规文法G,都存在一个NFA M,满足L（G）=L（M）。（V）6. 对任意一个右线性正规文法G,都存在一个DFA M,满足L（G）= L（M）。（V）7. 对任何正规式e,都存在一个NFA M,满足L（M）=L（e）。（V）8. 对任何正规式e,都存在一个DFA M,满足L（M）=L（e）。（V）9. 从一个句型到另一个句型的推导过程是唯一的。（X）10. 词法分析作为单独的一遍来处理较好。（X）11. 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（X）12. 二义文法不是上下文无关文法。（X）13. 自上而下分析法是一种“移进一归约”法。（X）14. 文法是描述语言的语法结构的形式规则。（V）15. 产生式是定义语法范畴的一种书写规则。（V）16. 要构造行之有效的自上而下的分析器，则必须消除左递归。（X）17. 如果文法G是无二义的，那么规范归约和规范推导是互逆的两个过程。（V）18. 自下而上的分析法是一种“移进一归约”法。（V）19. 如果文法G是二义的，那么规范归约和规范推导是互逆的两个过程。（X）三、填空题1. 解释程序和编译程序的区别在于（是否生成目标代码）。2. 编译过程通常可分为5个阶段，分别是（词法分析）、（语法分析）、语义分析与中间代码产生、代 码优化和目标代码生成。3. 编译程序工作过程中，第一阶段输入是（源程序），最后阶段的输出为（目标代码）程序。4. 把语法范畴翻译成中间代码所依据的是（语义规则）。5. 目标代码可以是（汇编）指令代码或（可重定位）指令代码或绝对机器指令代码。6. 词法分析的任务是：输入源程序，对构成源程序的（字符串）进行扫描和分解。7. 源程序中的错误通常分为（语法错误）和（语义错误）两大类。8. （编译程序）是将源程序翻译成目标程序的程序。9. 一个上下文无关文法G包括四个部分：（终结符号）、（非终结符号）、（开始符号）和一组（产生式）。10. 若a na n na，则称这个序列是从a 到的一个（推导）。1 2 n 1 n*11. 设文法G的开始符号为S,如果S na则称a是l（G）的一个（句型）。12. 文法G所产生的句子的全体是文法G所定义的（语言）。13. 若一个文法存在某个句子对应的两棵不同的语法树，则称这个文法是（二义文法）。14. 程序语言的单词符号一般可分为五种：（关键字）、（标识符）、常数、（运算符）和界符。15. （确定有限自动机DFA）是非确定有限自动机NFA的一个特例。16. 对于正规文法G和有限自动机M,若L（G）=L（M），则称G和M是（等价）的。17. 若两个正规式所表示的正规集相等，则认为二者是（等价）的。18按照语法分析树的建立方法，语法分析可分为两类：(自上而下分析)和(自下而上分析)。 18规范归约中的可归约串是指(句柄)。19算符优先分析中的可归约串是指(最左素短语)。20(自下而上)语法分析的关键问题是精确定义可归约串的概念。四、简答1给出上下文无关文法的定义。一个上下文无关文法G是一个四元式(V, V, S, P),其中：TNvt是一个非空有限集，它的每个元素称为终结符号；V：是一个非空有限集，它的每个元素称为非终结符号，vtuvn=；s是一个非终结符号，称为开始符号；T P是一个产生式集合(有限)，每个产生式的形式是P-a，其中，PGVN，aG(VTUVN)*o开始符号s至少必须在某个产生式的左部出现一次。NT N2.给出正规式与正规集的递归定义。(1) &和都是工上的正规式，它们所表示的正规集分别为&和；(2) 任何aE，a是工上的一个正规式，它所表示的正规集为a；(3) 假定U和V都是工上的正规式，它们所表示的正规集分别记为L(U)和L(V),那么，(U|V)、(UV) 和(U)*也都是正规式，它们所表示的正规集分别为L(U) UL(V)、L(U)L(V)(连接积)和(L(U)*(闭包)。仅由有限次使用上述三步骤而得到的表达式才是工上的正规式。仅由这些正规式所表示的字集才是工 上的正规集。3设文法G为：s-aAcB|BdsA-BaB|aBc|aB-ascA|cAB|b对于输入串aacabccb，给出最左推导。s=aAcB=aaBccB=aacABccB=aacaBccB=aacabccB=aacabccb4设文法G为：s-BAA-Bs|dB-aA|bs|c对于输入串adccd,给出最左推导。s=BA=aAA=adA=adBs=adcs=adcBA=adccA=adccd5.证明：文法G：P-PaP|PbP|cP|Pe|f为二义文法。对于文法G定义的句子fbfbf,有两棵不同的语法树：所以该文法是二义文法。6. 证明：文法G：P-S+S|S*S|i|(S)为二义文法。对于文法G定义的句子i+i*i,有两棵不同的语法树:/S所以该文法是二义文法。7给定正规文法G:S-aS|bA|bA-aS请构造与之等价的有限自动机。8给定正规文法G:S-aAA-bA|aB|bB-aA请构造与之等价的有限自动机。9对下面给出的 NFA 确定化。假定整个表达式的真假出口分别为Ltrue和Lfalse，请翻译成三地址语句。 if ab goto L1goto LfalseL1:if cd goto Ltrue goto L2L2:if ef goto Ltrue goto Lfalse14有如下语句：if ab then if cd then p:=a+1 else p:=b+1 else p:=c+1 请翻译成三地址语句。if ab goto L1goto L2L1:if cb(vvv=v)dvvvv#vvv=由于该文法的任何产生的右部都不含两个相继的非终结符，故属于算符文法。从上表可以看出，任何两个终结符之间至少满足=、三种关系之一，故G为算符优先文法。 给出句型(SdSdS)对应的语法树，指出该句型的短语、句柄短语：(SdSdS) SdSdS SdS S 句柄: S2.设有文法G:S-S*F|FFF fP|PP- (S)|i 完成下列算符优先关系表，并判断是否为算符优先文法(请说明理由)。*f()i#*vvvfvv(vvv=v)i#vvvv=由于该文法的任何产生的右部都不含两个相继的非终结符，故属于算符文法。从上表可以看出，任何两个终结符之间至少满足=、三种关系之一，故G为算符优先文法。 给出句型S*P f (S)对应的语法树，指出该句型的短语、句柄短语：S*P f (S) Pf (S) P (S)F句柄: P一、单项选择题（共10 小题，每小题 2分） （题分 20分）1语言是A. 句子的集合B.产生式的集合C.符号串的集合D.句型的集合2. 编译程序前三个阶段完成的工作是A. 词法分析、语法分析和代码优化B. 代码生成、代码优化和词法分析C. 词法分析、语法分析、语义分析和中间代码生成D. 词法分析、语法分析和代码优化3. 一个句型中称为句柄的是该句型的最左A. 非终结符号B.短语 C.句子 D.直接短语4. 下推自动机识别的语言是A. 0 型语言B. 1 型语言C. 2 型语言D. 3 型语言5. 扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A. 字符B.单词C.句子D.句型6. 对应 Chomsky 四种文法的四种语言之间的关系是A. LuLUL2uL3B.C. LsuLgULiULo.7词法分析的任务是A.识别单词C.识别句子8常用的中间代码形式不含A.三元式B.四元式9 代码优化的目的是A.节省时间C.节省时间和空间10代码生成阶段的主要任务是A.把高级语言翻译成汇编语言L3UL2UL1UL0L0UL1UL2=L3B. 分析句子的含义D.生成目标代码C. 逆波兰式 D.语法树B. 节省空间D. 把编译程序进行等价交换B. 把高级语言翻译成机器语言C. 把中间代码变换成依赖具体机器的目标代码D. 把汇编语言翻译成机器语言二、填空题（本大题共 5 小题，每小题 2 分）（题分 10分）1编译程序首先要识别出源程序中每个（），然后再分析每个（）并翻译其意义。2编译器常用的语法分析方法有（）和（）两种。），中间代码生成、代3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的 （码优化与目标代码的生成则是对源程序的（）。）方案和4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即： （ （ ） 方案。5对编译程序而言，输入数据是（），输出结果是（）。三、名词解释题（共 5 小题，每小题 4 分） （题分 20分）1词法分析2. LL（1）文法3语法树4. LR（O）分析器5. 语言和文法四、 简答题（共4小题，每小题5分）（题分 20分）1 .编译程序和高级语言有什么区别 ?2. 编译程序的工作分为那几个阶段?3. 简述自下而上的分析方法。4. 简述代码优化的目的和意义。五、综合应用题（共3小题，每小题10分）（题分 30分）1. 证明下述文法 G：STaSbSlaSId是二义性文法。2对于文法GS： StAB, ATAalbB, BalSb求句型baSb的全部短语、直接短语和句柄? 句型 baSb 的语法树如图五（2）所示。图五（2） 句型 baSb 的的语法树3设有非确定的有自限动机NFA M=(A, B, C, 0, 1, 5, A, C),其中：5 (A, 0)=C5 (A, 1)=A, B 5 (B, 1)=C5 (C, 1)=C。请画出状态转换距阵和状态转换图。参考答案 一、单项选择题（共10 小题，每小题 2分，共 20分）1语言是A.句子的集合B.产生式的集合C. 符号串的集合D.句型的集合2. 编译程序前三个阶段完成的工作是A. 词法分析、语法分析和代码优化B. 代码生成、代码优化和词法分析C 词法分析、语法分析、语义分析和中间代码生成D. 词法分析、语法分析和代码优化3. 一个句型中称为句柄的是该句型的最左A.非终结符号B.短语 C.句子 D.直接短语4下推自动机识别的语言是A0 型语言B1 型语言C 2型语言D. 3型语言5扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A. 字符B一单词C.句子D.句型6对应 Chomsky 四种文法的四种语言之间的关系是A. L0UL1UL2UL3 L 丿3=1 gUL 丿UL 丿 7词法分析的任务是BL3UL2ULiULoDL0UL1 UL2=L3A.识别单词B分析句子的含义C.识别句子D.生成冃标代码8常用的中间代码形式不含A.三元式B.四元式C.逆波兰式D.语法树9 代码优化的冃的是A.节省时间B节省空间C节省时间和空间D.把编译程序进行等价交换10代码生成阶段的主要任务是A. 把高级语言翻译成汇编语言B. 把高级语言翻译成机器语言C把中间代码变换成依赖具体机器的冃标代码D.把汇编语言翻译成机器语言二、填空题（本大题共5小题，每小题2分，共10分）1编译程序首先要识别出源程序中每个（单词），然后再分析每个（句子）并翻译其意义。2编译器常用的语法分析方法有（自底向上）和（自顶向下）两种。3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的（分析）,中间代码生成、代码 优化与冃标代码的生成则是对源程序的（综合）。4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配）方案和（动态存储分配） 方案。5对编译程序而言，输入数据是（源稈序），输出结果是（冃标稈序）。三、名词解释题（共5小题，每小题4分，共20分）1词法分析词法分析的主要仟务是从左向右扫描每行源稈序的符号，按照词法规则从构成源稈序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析稈序。2. LL(1)文法若文法的任何两个产生式 A t a丨卩 都满足下面两个条件：(1) FIRST(a) c FIRST(卩)=咖(2) 若卩=* ，那么 FIRST(a) c FOLLOW( A )=机我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产牛最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是一义的，也不含左递归。3. 语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(Vn，V, P, S),对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征：(1) 根节点的标记是开始符号S。(2)