编译原理期末试题（8套含答案+大题集）

《编译原理》期末试题（一）

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．编译程序是对高级语言程序的解释执行。(× )

2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。 (√ ) 4．语法分析时必须先消除文法中的左递归 。 (×)

5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (√) 6．逆波兰表示法表示表达式时无须使用括号。 (√ ) 7．静态数组的存储空间可以在编译时确定。 (×)

8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (×) 9．两个正规集相等的必要条件是他们对应的正规式等价。 (× ) 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． 文法G：S→xSx|y所识别的语言是_____。

A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。 A．( )最左推导和最右推导对应的语法树必定相同 B．( ) 最左推导和最右推导对应的语法树可能不同 C．( ) 最左推导和最右推导必定相同

D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。

A．( )源程序 B．( ) 目标语言 C．( ) 编译方法 D．( ) 以上三项都是 6．四元式之间的联系是通过_____实现的。 A．( ) 指示器 B．( ) 临时变量 C．( ) 符号表 D．( ) 程序变量

第1页共6页

7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。 A. ( ) ┐AB∨∧CD∨ B．( ) A┐B∨CD∨∧ C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨ 8. 优化可生成_____的目标代码。

A．( ) 运行时间较短 B．( ) 占用存储空间较小

C．( ) 运行时间短但占用内存空间大 D．( ) 运行时间短且占用存储空间小 9．下列______优化方法不是针对循环优化进行的。 A. ( ) 强度削弱 B．( ) 删除归纳变量 C．( ) 删除多余运算 D．( ) 代码外提 10．编译程序使用_____区别标识符的作用域。 A. ( ) 说明标识符的过程或函数名

B．( ) 说明标识符的过程或函数的静态层次 C．( ) 说明标识符的过程或函数的动态层次 D. ( ) 标识符的行号

三、填空题(每空1分，共10分)

1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。

2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。 4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。 5．后缀式abc-/所代表的表达式是___a/(b-c)__。 6．局部优化是在__基本块___范围内进行的一种优化。 四、简答题（20分）

1. 简要说明语义分析的基本功能。

答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。

2. 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S

消除文法的左递归及提取公共左因子。 解：消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子：

第2页共6页

S→(T) | aS′ S′→+S | ε T→ST′ T′→,ST′| ε

3. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 解： w a b + c d e 10 - / + 8 + * +

4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： while (A

if (A ≥ 1) C=C+1; else while (A ≤ D) A=A+2;

}。

解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)： 100 (j<,A,C,102) 101 (j,_,_,113) 102 (j<,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j≤,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 113

5. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。 证明：

由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：

第3页共6页

因此，文法G[S]为二义文法。

五.计算题（10分） 已知文法 A->aAd|aAb| ε

判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。 解：增加一个非终结符S/后，产生原文法的增广文法有： S'->A A->aAd|aAb|ε 下

面

构

造

它

的

LR(0)

项

目

集

规

范

族

第4页共6页

为

：

从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。 其SLR(1)分析表为：

对输入串ab#给出分析过程为：

第5页共6页

static long cc = 30; short dd = 40; }

.file \ .version \gcc2_compiled.: .data

.align 4

.type aa,@object .size aa,4 aa:

.long 10 .globl bb .align 2

.type bb,@object .size bb,2 bb:

.value 20 .align 4

.type cc.2,@object .size cc.2,4 cc.2:

.long 30 .text

.align 4 .globl func

.type func,@function func:

pushl ?p

movl %esp,?p subl $4,%esp

movw $40,-2(?p) .L1:

leave ret .Lfe1:

.size func,.Lfe1-func .ident \(GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)\ 8．（10分）C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型

第46页共6页

语言。 9．（10分）如果在A机器上我们有C语言编译器CCA，也有它的源码SA（用C语言写成）。如何利用它通过尽量少的工作来得到B机器的C语言编译器CCB。 10．（5分）表达式(?x.(?yz.(x + y) + z) 3) 4 5和(?x.(?yz.(x + y) + z) 3 5) 4有同样的结果。在抽象机FAM上，哪一个表达式对应的目标代码的执行效率高？为什么？

参考答案 1．

others start 1 / 2 * 2 * others 4 *

/ 5

2．LR（1）文法 LR（1）文法 二义文法 S ? AB | aABb S ? AB S ? AASb | ? A ? aaAb | ? A ? aaAb | ab | ? A ? a | ?

B ? Bb | ? B ? Bb | ? 3． int real id , $ D D?TL D?TL T T?int T?real L L?id R R R ?, id R R ? ?

4． S? ? S print(S.num) S ? (L) S.num := L.num +1 S ? a S.num := 0 L ? L1,S L.num := L1.num + S.num L ? S L.num := S.num S? ? {S.depth := 0} S S ? {L.depth := S.depth +1} (L) S ? a {print(S.depth)} L ? {L1.depth := L.depth} L1, {S.depth := L.depth} S L ? { S.depth := L.depth} S 5． t1 := initial t2 := final if t1 > t2 goto L1 v := t1 L2: stmt

第47页共6页

if v = t2 goto L1 v := v + 1 goto L2 L1: 6．由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。 7．aa是静态外部变量，而bb是外部变量，它们都分配在静态数据区（由.data伪指令开始），但是bb由伪指令.globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。cc是静态局部变量，同aa和bb一样，它的生存期是整个程序并分配在静态数据区。由于cc在源程序中的作用域是函数func的体，而在目标文件中，它的作用域至少已是整个文件了，为避免同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了cc.2。由于cc不是全局的，因此cc.2前面没有伪指令.globl。dd是自动变量，其作用域是函数func的体，其生存期是该函数激活期间，因此它分配在栈区，并且置初值是用运行时的赋值来实现。

8．例如联合体的类型检查一般也不可能在编译时完成，虽然下面例子是可静态判断类型错误的。 union U { int u1; int *u2;} u; int ?p; u.u1 = 10; p = u.u2; ?p = 0;

9． ? 修改源码SA 的代码生成部分，让它产生B机器的代码，称结果程序为SB。 ? 将SB提交给CCA进行编译，得到一个可执行程序。

? 将SB提交给上述可执行程序进行编译，得到所需的编译器CCB。

10．第一个表达式在执行?yz.(x + y) + z) 3时出现参数个数不足的情况，因此有FUNVAL的值进入栈顶，然后发现参数个数不足，又把它做成FANVAL的情况。而第二个表达式执行的是(?yz.(x + y) + z) 3 5，不会出现参数个数不足的情况。因此第二个表达式的执行效率比第一个表达式的高。

《编译原理》期末大题

1. 设有如下文法G（S），试消除其左递归。

G（S）：S—>Ac|c A—>Bb|b B—>Sa|a

解：

S→abcS′|bcS′|cS′, S′→abcS′|?

2. 试构造与下面G（S）等价的无左递归的文法。

G（S）：S—>Sa|Nb|c N—>Sd|Ne|f

解：S→fN′bS′|cS′, S′→aS′|dN′bS′|?, N′→eN′|? 3. 设有文法G（S）：

S—>aBc|bAB

第48页共6页

A—>aAb|b B—>b|ε

①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。 ②构造LL(1)分析表，并分析符号串baabbb是否是。

解：（1）FIRST(aBc)={a}, FIRST(bAB)={b} FIRST(aAb)={a}, A→b: FIRST(A→b)={b}, B→b: FIRST(b) = {b}, FIRST(ε)={ε} FOLLOW(A)={b, #}, FOOLOW(B)={c, #}

SELECT(S→aBc)={a}, SELECT(S→bAB) ={b}, SELECT(A→aAb)={a}, SELECT(A→b)={b}, SELECT(B→b)={b}, SELECT(B→?)={c, #}

因此，所得的LL(1)分析表如表A-4所示。

表A-4 LL(1)分析表 （2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。

步骤 符号栈 输入串 所用的产生式 1 #S baabbb# S?bAB 2 #BAb baabbb# 3 #BA aabbb# A?aAb 4 #BbAa aabbb# 5 #BbA abbb# A?aAb 6 #BbbAa abbb# 7 #BbbA bbb# A?b 8 #Bbbb 9 #Bbb 10 #Bb 11 #B 12 # bbb# bb# b# # # B?ε 成功

输输入符号 入 a b c # VN S S→aBc S→bAB A A→aAb A→b B B→b B→? B→? 图A-16 识别串baabbb的过程

4. 对下列文法G(S)：

S—>D(R) R—>R;P|P P—>S|I D—>i

①计算文法G中每个非终结符的FIRSTVT集和LASTVT集。 ②构造文法G的算符优先关系矩阵。 解：（1）FIRSTVT(S)={(, i}，FIRSTVT(D) ={i}，FIRSTVT(R)={;, (, i}，FIRSTVT(P)={i, (}，LASTVT(S)={)}，LASTVT(D)={i}，LASTVT(R) = {;, ), i}，LASTVT(P)={i, )}

第49页共6页

（2）算符优先矩阵，如表A-5所示。

表A-5 优先矩阵 ( ) ; i # ( ) ; i # ?? B ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? B 5. 已知文法G(S)： S—>a|(T) T—>T,S|S

①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。

解：（1）最左推导：S?(T)?(T,S)?(S,S) ?(a,S)?(a,(T))?(a,(T,S))?(a,(S,S))?(a,(a, S))?(a,(a,a))

语法树：如图A-16所示。

S( T )T , SSa( T )T , SSaa图A-16 (a,(a,a))的语法树

（2）句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。

短语：a || T,a || (T) || T , a , (T) || (T , a , (T)) 直接短语：a || (T) 素短语：a || (T) 最左素短语：a 句柄：a

活前缀：? || ( || (T || (T , || (T , a

S( T )T , ST , S( T )a 图A-17 (T,a,(T))的语法树

6. 设文法Ｇ（Ｓ）为：

Ｓ—＞ａ｜ａＡｂ Ｓ—＞ｂ｜ｂＢａ Ａ—＞１Ａ０｜ε Ｂ—＞１Ｂ０｜ε

第50页共6页

本文来源：https://www.bwwdw.com/article/u0ax.html