1、第 1 页共 6 页 编译原理期末试题（一） 一、是非题（请在括号内，正确的划，错误的划）（每个 2 分，共 20 分） 1编译程序是对高级语言程序的解释执行。( ) 2一个有限状态自动机中，有且仅有一个唯一的终态。() 3一个算符优先文法可能不存在算符优先函数与之对应。 ( ) 4语法分析时必须先消除文法中的左递归 。 () 5LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 () 6逆波兰表示法表示表达式时无须使用括号。 ( ) 7静态数组的存储空间可以在编译时确定。 () 8进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 () 9两
2、个正规集相等的必要条件是他们对应的正规式等价。 ( ) 10一个语义子程序描述了一个文法所对应的翻译工作。 () 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)( 每个 4 分，共 40 分) 1词法分析器的输出结果是_。 A( ) 单词的种别编码 B( ) 单词在符号表中的位置 C( ) 单词的种别编码和自身值 D ( ) 单词自身值 2 正规式 M 1 和 M 2 等价是指_。 A( ) M1 和 M2 的状态数相等 B( ) M1 和 M2 的有向边条数相等 C( ) M1 和 M2 所识别的语言集相等 D ( ) M1 和 M2 状态数和有向边条数相等 3 文法
3、 G：SxSx|y 所识别的语言是_。 第 2 页共 6 页 A( ) xyx B( ) (xyx)* C( ) xnyxn(n0) D( ) x*yx* 4如果文法 G 是无二义的，则它的任何句子 _。 A( ) 最左推导和最右推导对应的语法树必定相同 B( ) 最左推导和最右推导对应的语法树可能不同 C( ) 最左推导和最右推导必定相同 D( ) 可能存在两个不同的最左推导，但它们对应的语法树相同 5构造编译程序应掌握_。 A( ) 源程序 B( ) 目标语言 C( ) 编译方法 D( ) 以上三项都是 6四元式之间的联系是通过_实现的。 A( ) 指示器 B( ) 临时变量 C( ) 符
4、号表 D( ) 程序变量 7表达式(AB)(CD) 的逆波兰表示为_。 A. ( ) AB CD B ( ) ABCD C( ) ABCD D ( ) ABCD 8. 优化可生成_的目标代码。 A( ) 运行时间较短 B( ) 占用存储空间较小 C( ) 运行时间短但占用内存空间大 D ( ) 运行时间短且占用存储空间小 9下列_优化方法不是针对循环优化进行的。 A. ( ) 强度削弱 B( ) 删除归纳变量 C( ) 删除多余运算 D( ) 代码外提 10编译程序使用_区别标识符的作用域。 第 3 页共 6 页 A. ( ) 说明标识符的过程或函数名 B( ) 说明标识符的过程或函数的静态层
5、次 C( ) 说明标识符的过程或函数的动态层次 D. ( ) 标识符的行号 三、填空题(每空 1 分，共 101.优化可生成运行时间短且占用存储空间小的目标代码 2.LR 分析法解决“移进-规约”冲突时，右结合意味着建立联系实行移进 3.若 B 为非终结符，则 Aa.Bb 为待约项目 4.在目标代码生成阶段，符号表用于数据存储分配的依据 5.四元式之间的联系是通过临时变量实现的 1计算机执行用高级语言编写的程序主要有两种途径：_解释_和_编译_。 2扫描器是_词法分析器_，它接受输入的_源程序_，对源程序进行_词法分析_并识别出一个 个单词符号，其输出结果是单词符号，供语法分析器使用。 3自上
6、而下分析法采用_移进_、归约、错误处理、_接受_等四种操作。 4一个 LR 分析器包括两部分：一个总控程序和 _一张分析表_。 5后缀式 abc-/所代表的表达式是_a/(b-c)_。 6局部优化是在_基本块_范围内进行的一种优化。 三、对于文法 G(E): (8 分) ET|E+T TF|T*F F(E)|i 1. 写出句型 T*F+i1*i2 的最右推导并画出语法树。 2. 写出上述句型的短语，直接短语、句柄、素短语和最左素短语 答：1.E = E+T = E+T*F = E+T*i2 = E+F*i2 = E+i1*i2 = T*F +i1*i2 2.短语：T*F+i1*i2, T*F,
7、 i1*i2, i1, i2 直接短语：T*F, i1, i2 句柄：T*F 素短语：T*F, i1, i2 最左素短语：T*F 第 4 页共 6 页 3. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 解： w a b + c d e 10 - / + 8 + * + 编译原理期末试题（二） 一、是非题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 （ ） 3.已经证明文法的二义性是可判定的。 （ ） 4.每个基本块可用一个 DAG 表示。 （ ） 5.每个过程的活动记录的体积在编译时可静态确定。 （
8、 ） 6.2 型文法一定是 3 型文法。 （ ） 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 X ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 （ ） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 X ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的
9、。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 第 5 页共 6 页 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3 型文法一定是 2 型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 答案：1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 二、填空题： 2.编译过程可分为 （ 词法
10、分析） ， （语法分析） ， （语义分析与中间代码生成 ） ， （优化）和（目标 代码生成 ）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ 二义性的 ） 。 5.语法分析器的输入是（ 单词符号 ） ，其输出是（ 语法单位 ） 。 6.扫描器的任务是从（ 源程序中 ）中识别出一个个（ 单词符号 ） 。 13.根据优化所涉及的程序范围，可将优化分成为(局部优化） ， （循环优化） ， （全局优化）三个级别。 14.语法分析的方法大致可分为两类，一类是（ 自上而下 ）分析法，另一类是（ 自下而上 ）分析法。 15.预测分析程序是使用一张（ 分析表 ）和一个（ 符号栈
11、 ）进行联合控制的。 17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终 ）态。 19.语法分析是依据语言的（语法 ）规则进行。中间代码产生是依据语言的（语义）规则进行的。 24.最右推导亦称为（规范推导） ，由此得到的句型称为（规范）句型。 29.局限于基本块范围的优化称（ 局部优化 ） 。 31.2 型文法又称为（上下文无关）文法；3 型文法又称为（正则 ）文法。 33.算符优先分析法每次都是对(最左素短语）进行归约。 16.写出表达式 ab*(c-d)/e 的逆波兰式和三元序列。16.逆波兰式: abcd-*e/+ 三元序列: op arg1 arg
12、2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3) 五、计算题： 四、设文法 G(S)：(12 分)(|*)BA|Si 1构造各非终结符的 FIRSTVT 和 LASTVT 集合； 2构造优先关系表和优先函数。(12 分) 答：(6 分) FIRSTVT(S)= i，+ ，) ，( FIRSTVT(A)= +，)，( FIRSTVT(B)= )，( 第 6 页共 6 页 LASTVT(S)= i，+，*，( LASTVT(A)= +，*，( LASTVT(B)= *，( 优先关系表: (3 分) i + ( ) * i ) 优先函数: (3 分) i
13、 + ( ) * f 2 6 6 1 6 g 1 4 6 6 1 。 6.设有基本块 D:=A-C E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q K:=G*5 L:=K+J M:=L 假设基本块出口时只有 M 还被引用，请写出优化后的四元序列。6.优化后的四元序列 D:=A-C E:=A*C F:=D*E M:=F+20 9.已知文法 G(S) SaAcBe AAb| b Bd (1)给出句子 abbcde 的最左推导及画出语法树； (2)给出句型 aAbcde 的短语、素短语。 9.(1) S=aAcBe=AAbcBe=abbcBe=abbcd
14、e (2) 短语: aAbcde, Ab, d 素短语: Ab, d 第 7 页共 6 页 10.设文法 G(S): S(T) | aS | a TT,S | S 消除左递归和提公共左因子； 构造相应的 FIRST 和 FOLLOW 集合； 构造预测分析表。 10.(1) S (L) | aS SS | LSL L,SL | (2) FIRST(S)=a, ( FIRST(S)=a, (, FIRST(L)=a, ( FIRST(L)=, FOLLOW(S)=, ), # FOLLOW(S)=, ), # FOLLOW(L)= ) FOLLOW(L)= ) (3) ( ) a , # S S
15、(L) S aS S SS S SS S S L LSL LSL L,SL L L 12.已知文法 G(S) EE+T | T TT*F| F F(E)| i (1) 给出句型 (i+i)*i+i 的最左推导及画出语法树； (2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。 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),
16、(E+T)*i, (E+T)*i+F 素短语 i, E+T 最左素短语 E+T 第 8 页共 6 页 编译原理期末试题（二） 三、 设有字母表a，b上的正规式 R=(ab|a)*。 解：（1） 0 1 2 3 b a a - + （2）将（1）所得的非确定有限自动机确定化 a b -0 1 1 3 12 2 1 +3 0 1 2 a a b a-+ + + （3）对（2）得到的 DFA 化简，合并状态 0 和 2 为状态 2： 1 2 a a b -+ + （4）令状态 1 和 2 分别对应非终结符 B 和 A 给定文法 GS： 用子集法将 NFA 确 定化： a b -+013 123 +1
17、23 123 13 +13 123 第 9 页共 6 页 将 S、A、Q、BZ、DZ、D、B 重新命名，分别用 0、1、2、3、4、5、6 表示。 因为 3、4 中含有 z，所以它们为终态。 编译原理期末试题（五） 一、单项选择题(共 10 小题，每小题 2 分，共 20 分) 1语言是 A句子的集合 B产生式的集合 C符号串的集合 D句型的集合 2编译程序前三个阶段完成的工作是 A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析 C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化 3一个句型中称为句柄的是该句型的最左 A非终结符号 B短语 C句子 D直接
18、短语 4下推自动机识别的语言是 A0 型语言 B1 型语言 C2 型语言 D3 型语言 5扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法 单位即 A 字符 B单词 C句子 D句型 6对应 Chomsky 四种文法的四种语言之间的关系是 AL 0L1L2L3 BL 3L2L1L0 CL 3=L2L1L0 DL 0L1L2=L3 7词法分析的任务是 A识别单词 B分析句子的含义 C识别句子 D生成目标代码 8常用的中间代码形式不含 A三元式 B四元式 C逆波兰式 D语法树 9 代码优化的目的是 A节省时间 B节省空间 C节省时间和空间 D把编译程序进行等价交换 10代
19、码生成阶段的主要任务是 A把高级语言翻译成汇编语言 B把高级语言翻译成机器语言 C把中间代码变换成依赖具体机器的目标代码 D把汇编语言翻译成机器语言 a b 0 1 2 1 1 3 2 2 4 3 2 5 4 1 6 5 1 6 6 2 5 第 10 页共 6 页 二、填空题（本大题共 5 小题，每小题 2 分，共 10 分） 1编译程序首先要识别出源程序中每个(单词) ，然后再分析每个 (句子)并翻译其意义。 2编译器常用的语法分析方法有(自底向上) 和(自顶向下)两种。 3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序 的(分析) ，中间代码生成、代码优化与目
20、标代码的生成则是对源程序的(综合)。 4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静 态存储分配)方案和(动态存储分配)方案。 5对编译程序而言，输入数据是(源程序) ，输出结果是(目标程序)。 五、综合应用题(共 3 小题，每小题 10 分，共 30 分) 1证明下述文法 G： SaSbS|aS|d 是二义性文法。 解： 一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个 文法是二义性文法。 句子 aadbd 有两棵语法树。如下图： (1) (2) 由此可知，SaSbS|aS|d 定义的文法是二义性文法。 二、设=0，1上的正规集 S 由倒数第
21、二个字符为 1 的所有字符串组成，请给 出该字集对应的正规式，并构造一个识别该正规集的 DFA。(8 分) 答： 构造相应的正规式：(0|1)*1(0|1) (3 分) d S Sa bS Sa d S a S Sa bS dd 第 11 页共 6 页 NFA: (2 分) 1 1 1 0 0 确定化：(3 分) I 0I1I 0,1,2 1,2 1,2,3 1,2 1,2 1,2,3 1,2,3 1,2,4 1,2,3,4 1,2,4 1,2 1,2,3 1,2,3,4 1,2,4 1,2,3,4 0 1 0 1 0 0 0 1 1 1 三、写一个文法使其语言为 L(G)= anbmambn
22、 | m,n1。(6 分) 答：文法 G(S): S aSb | B B bBa | ba 四、对于文法 G(E): (8 分) ET|E+T TF|T*F F(E)|i 1. 写出句型(T*F+i)的最右推导并画出语法树。 2. 写出上述句型的短语，直接短语、句柄和素短语。 答： 1. (4 分 ) ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 0 1 2 3 4 0 1 2 3 4 E T F ( E ) E + T F i T T * F 第 12 页共 6 页 2. (4 分) 短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i
23、句柄：T*F 素短语：T*F, i 五、设文法 G(S)：(12 分)(|*)BA|Si 3构造各非终结符的 FIRSTVT 和 LASTVT 集合； 4构造优先关系表和优先函数。(12 分) 答：(6 分) FIRSTVT(S)= i，+ ，) ，( FIRSTVT(A)= +，)，( FIRSTVT(B)= )，( LASTVT(S)= i，+，*，( LASTVT(A)= +，*，( LASTVT(B)= *，( 优先关系表: (3 分) i + ( ) * i ) 优先函数: (3 分) i + ( ) * f 2 6 6 1 6 g 1 4 6 6 1 七、(8 分) 将语句 if
24、(A0) then while C0 do C:=C+D 翻译成四元式。(8 分) 答： 100 (j， B， 0， 104) 103 (j， -， -， 109) 104 (j， C， 0， 106) 105 (j， -， -， 109) 106 (+， C， D， T1) 107 (:=， T1， -， C) 108 (j， -， -， 104) 109 (控制结构 3 分，其他 5 分) 八、(10 分) 设有基本块如下： T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5 T6:=T5*T3 B:=T6 (1)画出 DAG
25、图； (2)设 A,B 是出基本块后的活跃变量，请给出优化后 的四元式序列。 答：(1) DAG 如右图：(6 分) (2) 四元式序列： (4 分) T1:=S+R T4:=S/R A:=T1-T4 B:=T1*4 九、(9 分) 设已构造出文法 G(S)： (1) S BB (2) B aB T1,T5, B 3 T2 4S R + / *_ T3 T4 A T6,B n4 n5n1 n2 n3 n6 n8n7 第 14 页共 6 页 (3) B b 的 LR 分析表如下 ACTION GOTO 状态 a b # S B 0 s3 s4 1 2 1 acc 2 s6 s7 5 3 s3 s4 8 4 r3 r3 5 r1 6 s6 s7 9 7 r3 8 r2 r2 9 r2 假定输入串为 abab，请给出 LR 分析过程(即按照步骤给出状态，符号，输入串 的变化过程)。 答： 步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB # 8 025 #BB # 9 01 #S # acc
