编译原理试卷及答案

秦 皇 岛 分 校 东 北 大 学

C、绝对机器指令代码 D、中间代码 3、一个控制流程图就是具有 C 的有向图

A、唯一入口结点 B、唯一出口结点 C、唯一首结点 D、唯一尾结点 4、设有文法G[S]:S→b|bB

B→bS ,则该文法所描述的语言是 C 。

学 号

课程名称: 编译原理 试卷: (B )答案 考试形式: 闭卷

授课专业: 计算机科学与技术 考试日期: 年 月 日 试卷:共 2 页 班 级

姓 名

装 订 装 线 订 线 内 不 要 答 题 题号 一 二 三 四 总分 得分 阅卷人 一、填空题(每空2分,共30分)

1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段,另外还有两个重要的工作是 理 和出错处理。表格管

2、规范规约中的可归约串是 句柄 ,算符优先分析中的可归约串是 最左素短语 。3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。 4、LR(0)文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。 5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。

6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。

7、确定有穷自动机DFA是 NFA 的一个特例。 8、表达式 (a+b)*c 的逆波兰表示为 ab+c* 。

二、选择题(每题2分,共20分)

1、LR语法分析栈中存放的状态是识别 B 的DFA状态。

A、前缀 B、可归前缀 C、项目 D、句柄 2、 D 不可能是目标代码。

A、汇编指令代码 B、可重定位指令代码

A、L(G)={bi|i≥0} B、L(G)={b2i|i≥0}

C、L(G)={b2i+1|i≥0} D、L(G)={b2i+1|i≥1}

5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。

A、编译器 B、汇编器 C、解释器 D、预处理器 6、在目标代码生成阶段,符号表用于 D 。

A、目标代码生成 B、语义检查 C、语法检查 D、预处理器地址分配0

7、规范归约是指 B 。

A、最左推导的逆过程 B、最右推导的逆过程 C、规范推导 D、最左归约逆过程 8、使用 A 可以定义一个程序的意义。

A、语义规则 B、词法规则 C、语法规则 D、左结合规则 9、经过编译所得到的目标程序是 D 。

A、三元式序列 B、四元式序列 C、间接三元式 D、机器语言程序或汇编语言程序10、在一个基本块内进行的代码优化是 B 。

A、全局优化 B、局部优化 C、循环优化 D、代码外提

三、简答题(3小题,共30分) 1、已知文法G[S]:S→Ac|aB

A→ab

B→bc

证明该文法具有二义性(本题6分)

证明:因为该文法的句型abc存在如下两棵语法树:

- 1 -

所以,该文法具有二义性

四、综合题(20分)

设有文法G[S]:S→BA

A→BS|d

B→aA|bS|c

3、若有文法G[S]:S→bAb A→(B|a B→Aa)。构造该文法的简单优先关系矩阵。

学 号

班 级

姓 名

装 订 装 线 订 线 内 不 要 答 题 (10分) 解:

4、构造正规表达式(a|b)* b的DFA并化简。(14分)

解:先构造其NFA如下:

确定化为DFA:

将其最小化如下:

(1) 证明文法G是LL(1)文法。 (2) 构造LL(1)分析表。 (3) 写出句子adccd的分析过程。 解:(1)

可见,文法G是是LL(1)文法。 (2) (3)

备注: 学生不得在试题纸上答题(含填空题、选择题等客观题

- 2 -

6.一个LL( l)文法一定是无二义的。…………………………………………… … ( )

一、 填空题(每空1分,共20分)

1.编译过程一般分为 、 、中间代码生成、 和目标代码生成五个阶段。

2.语法分析最常用的两类方法是 和 分析法。 3.确定的有穷自动机是一个 ,通常表示为 。 4.所谓最右推导是指 。 5.语法分析器的任务是 。 6.如果一个文法的任何产生式的右部都不含有 的非终结符,则这种文法称为 文法。 7.进行确定的自上而下语法分析要求语言的文法是无 和 的。

8.LR分析法是一种 的语法分析方法。

9.根据优化对象所涉及的程序范围,代码优化分为 、 和 等。

10.常用的优化技术包括: 、 、强度削弱、复写传播、 等。

二、 是非题(下列各题,你认为正确的,请在题后的括号内打“ √”,错的打“×”。

每题2分,共20分)

1.正规文法产生的语言都可以用上下文无关文法来描述。 …………………… ( )

2.仅考虑一个基本块,不能确定一个赋值是否真是无用的。………………………( ) 3.如果一个文法是递归的,则其产生的语言的句子是无穷个。 …………………( ) 4.四元式之间的联系是通过符号表实现的。…………………………………………( ) 5.文法的二义性和语言的二义性是两个不同的概念。 ……………………… …( )

7.在规范规约中用最左素短语来刻划可归约串。………………… …………… ( ) 8.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。…………… ( ) 9.编译程序是对汇编程序的翻译。 ……………………………………( ) 10.逆波兰法表示的表达式亦称前缀式。 …………………………………………… ( )

三、 简答题(每题5分,共15分)

1、简述栈式存储管理策略; 2、何谓DAG; 3、何谓文法的二义性;

四、 给出下述文法对应的正规式 (7分)

S→ 0A| 1B A→1S | 1 B→0S | 0

五、 已知文法G(E):

E→T | E+T | E-T T→F | T*F | T/F F→(E) | i

证明E+T*F是该文法的一个句型,并指出该句型的所有短语、直接短语和句柄。(8分)

六、 设有文法G[S]:

S?aBc|bAB A?aAb|b B?b|ε

构造其LL(1)分析表,并分析符号串baabbb是否是该文法的句子. (10分)

- 3 -

七、 设有文法G[E]:

E? (E) |ε

试判断该文法是否为SLR(1)文法,若不是,请说明理由;若是请构造SLR(1)分析表。(10分)

八、 假设可用寄存器为R0和R1,试写出下列四元式序列对应的目标代码。(10

分) T1=B-C T2=A*T1 T3=D+1 T4=E-F T5=T3*T4

参考答案 一、填空题(1X20=20分)

1. 词法分析、语法分析、代码优化 2. 自上而下、自下而上 3. 五元组、DFA=(K ,∑, M, S, Z) 4. 任何一步

都是对

中最右非终结符进行替换

5. 分析一个文法的句子结构 6. 相邻、算符 7. 左递归、公共左因子 8. 自下而上

9. 局部优化、循环优化、局部优化

10. 删除公共子表达式、代码外提、变换循环控制条件、合并已知量、删除

无用赋值(任选3个)

二、是非题(2X10=20分)

1、× 2、√ 3、√ 4、× 5、√ 6、√ 7、 × 8、√ 9、× 10、×

三、简答题(见书中相应部分)(5X3=15分) 四、解:首先得正规式方程组: S=0A+1B A=1S+1 B=0S+0 求解该方程组得:

S=(01|10)(01|10)* (8分)

五、解 (2分)

是文法G[S]的句型。

短语:E+T*F, T*F (2分) 直接短语:T*F (2分) 句柄:T*F (2分) 六、解:

、因为FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}(2分),所以构造文法G[S]的LL(1)分析表(5)如下:

a B c

#

S aBc bAB A aAb

b

B

b

ε ε

符号串baabbb是该文法的句子(3分)(分析过程略)。

(2分)

所以该文法为SLR(1)文法。其分析表如下:(8分) 状态

ACTION

GOTO

(

) # E 0 S2

r2

r2 1

1

acc

- 4 -

S2

r2 r2

3

S4

r1

r1

目标代码为: (10分) LD R0,B

- 5 -

2 3 4

八、 SUB R0,C LD R1,A MUL R1,R0 LD R0,D ADD R0,1 ST R1,M LD R1,E SUB R0,F MUL R0,R1 LD R1,M DIV R1,R0 ST R1,W

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4