admin 管理员组文章数量: 1184232
2025年1月1日发(作者：mysql创建表设置主键)
毕节学院课程考试试卷纸
得分 评卷人
毕节学院期中课程试卷
2009 ~2010学年度第二学期《编译原理》
计科系07级计算机科学与技术专业 班
姓名 学号 得分
主考教师：黄正鹏 试卷类型：（半期考试）
一、填空题（每空1分，共20分）
1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,
中间代码生成,代码优化等几个基本阶段,同时还会伴有__
表格处理
___和 ___
出错处理
__。
2．若源程序是用高级语言编写的,___
目标程序
__是机器语言程序或汇编程序,则其翻译程
序称为 ___
编译程序
__ 。
3．编译方式与解释方式的根本区别在于__
是否生成目标代码
___。
4．对编译程序而言,输入数据是___
源程序_
_, 输出结果是__
目标程序
___。
5．若两个正规式e1和e2所表示的正规集相同,则e1和e2等价,写作e1=e2。
6．一个句型中的最左简单短语称为该句型的___
句柄
__。
7．词法分析基于__
正则
___文法进行，即识别的单词是该类文法的句子。
二、是非题（请在括号内，正确的划√，错误的划×）（每个1分，共10分）
得分 评卷人
1．计算机高级语言翻译成低级语言只有解释一种方式。(×)
2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×)
3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙
机的操作系统功能完全相同。 (√ )
4．正则文法其产生式为 A->a ， A->Bb, A,B∈V
N
， a 、 b∈V
T
。 (×)
5．每个文法都能改写为 LL(1) 文法。 (√)（2班做）
毕节学院《编译原理》课程试卷 第 页 共 8 页
1
毕节学院课程考试试卷纸
6.有穷自动机接受的语言是正规语言。 (√)（1班做）
7.对任何一个NFA M都存在一个DFA M’,使得L(M’)=L(M).( √ )
8．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×)
9．确定的自动机以及不确定的自动机都能正确地识别正规集。(√)
10．词法分析作为单独的一遍来处理较好。 (× )
11．有穷自动机接受的语言是正规语言。（√）
得分 评卷人
三、选择题（每小题2分，共20分）
1． 文法 G 产生的_____的全体是该文法描述的语言。
A．( ) 句型 B．( ) 终结符集 C．( ) 非终结符集
句子
2． 若文法 G 定义的语言是无限集，则文法必然是 _____。
A
．
( )
递归的
B．( ) 前后文无关的
C．( ) 二义性的 D．( ) 无二义性的
3． 四种形式语言文法中，1型文法又称为 _____文法。
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． 采用自上而下分析，必须_____。
（2班做）
A．( ) 消除左递归 B．( ) 消除右递归
C
．
( )
消除回溯
D
．
( ) 提取公共左因子
9．在规范归约中，用_____来刻画可归约串。
（2班做）
A．( )直接短语 B
．
( )
句柄
C．( )最左素短语 D．( )素短语
毕节学院《编译原理》课程试卷 第 页 共 8 页
D
．
( )
2
毕节学院课程考试试卷纸
10．词法分析器用于识别_____。
A．( ) 字符串 B．( )语句
C
．
( )
单词
D．( )标识符
11．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。
A. ( )
短语文法
B．( ) 正则文法
C．( ) 上下文有关文法 D．( ) 上下文无关文法
12．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符
号，一个开始符号，以及一组 _____。
A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式
得分 评卷人
四、简答题（每小题5分，共30分）
1.高级语言程序有哪两种执行方式？其特点是什么？
答：高级语言程序有编译程序和解释程序两种执行方式；
编译程序（Compiler）——将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语
言,机器语言)程序的翻译程序。
解释程序（Interpreter）——将高级程序设计语言写的源程序作为输入，边解释边执行源程
序本身，而不产生目标程序的翻译程序。
2、考虑文法G[S]：S→aSbS|bSaS|
(1)试用最左推导说明此文法是二义性的
（2）对于句子abab构造两个相应的最右推导
（3）对于句子abab构造两个相应的分析树
解答：
(1) 句子abab有如下两个不同的最左推导：
S => aSbS => abS =>abaSbS => ababS => abab
S => aSbS => abSaSbS => abaSbS => ababS => abab
所以此文法是二义性的。
(2) 句子abab的两个相应的最右推导：
S => aSbS => aSbaSbS => aSbaSb => aSbab => abab
S => aSbS => aSb => abSaSb => abSab => abab
(3) 句子abab的两棵分析树：
毕节学院《编译原理》课程试卷 第 页 共 8 页
3
毕节学院课程考试试卷纸
(a)
3、已知文法 G[E] 为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E) |i
① 该文法的开始符号（识别符号）是什么？
② 请给出该文法的终结符号集合 V
T
和非终结符号集合 V
N
。
③ 找出句型 T+T*F+i 的所有短语、简单短语和句柄。
解：① 该文法的开始符号（识别符号）是E。
②该文法的终结符号集合VT={+、-、*、/、（、）、i}。 非终结符号集合VN={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i; 简单短语为i、T*F、第一个T;
句柄为第一个T。
4. 构造正规式相应的 NFA : 1(0|1)*101
解：1(0|1)*101对应的NFA为
(b)
5.画出接受以/*和*/括起来的注释的状态转换图。
．解答：
毕节学院《编译原理》课程试卷 第 页 共 8 页
4
毕节学院课程考试试卷纸
6.用状态转换图表示识别偶数个0或偶数个1的字符串的有穷自动机。
解答：
得分 评卷人
五.计算题（10分）
1、构造下述文法 G[S] 的自动机：
①S->A0 ②A->A0|S1|0
该自动机是确定的吗？若不确定，则对它确定化。
解：由于该文法的产生式S->A0，A->A0|S1中没有字符集VT的输入，所以不是确定的自
动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把S->A0代入产生式A->S1
有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S->A0有该文法的正规式：0(0|01)*0，所以，
改写该文法为确定的自动机为：
由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：
下表由子集法将NFA转换为
DFA:
毕节学院《编译原理》课程试卷 第 页 共 8 页
5
毕节学院课程考试试卷纸
由上表可知DFA为：
2、设计一个状态数最小的DFA,其输入字母表是{0,1}，它能接受以00或01结尾的所有序
列，并给出相应的正规文法。（1班做）
解答：
正规式为：(0|1)
*
(00|01) 化简：(0|1)
*
0(0|1)
不确定的有穷自动机为：
确定化，并最小化得到：
正规文法为：
S→1S | 0A
A→0B | 0 | 1C | 1
B→0B | 0 | 1C | 1
C→1S | 0A
3、对下面的文法G:
E→TE’
E’→+E|
毕节学院《编译原理》课程试卷 第 页 共 8 页
6
毕节学院课程考试试卷纸
T→FT’
T’→T|
F→PF’
F’→*F’|
P→(E)|a|b|∧
(1) 计算这个文法的每个非终结符的First集和Folow集；
(2) 证明这个文法是LL(1)的；
(3) 构造它的预测分析表。
解答：
(1) 求First和Follow集
First(E)=First(T)={(,a,b,∧} ⑦
First(E')={+, } ⑥
First(T)=First(F)={(,a,b, ∧} ④
First(T')=｛(,a,b, ∧, ｝ ⑤
First(F)=First(P)={(,a,b, ∧} ③
First(F')=｛*，｝ ②
First(P)={(,a,b, ∧} ①（计算顺序）
Follow(E)= {#, ) }
Follow(E')= Follow(E)={#，)} (1)（使用的产生式）
Follow(T) = First(E')＼{}∪Follow(T') (1,2)
= {+}∪{),#}={+,),#}
Follow(T')= Follow(T)={+,},#} (3)
Follow(F)= First(T')＼{}∪Follow(T) (3,4)
= {(,a,b,∧,+ ,),#}
Follow(F')= Follow(F) (5)
= {(,a,b,∧,+ ,),#}
Follow(P)= First(F')＼{}∪Follow(F) (5,6)
={*,(,a,b,∧,+ ,),#}
(2) 证明:
∵a. 文法不含左递归；
b. 每个非终结符的各个侯选式的First集不相交；
c. First(E')∩Follow(E')={+, }∩{#,),}=
First(T')∩Follow(T')={(,a,b,∧, }∩{+,)}=
First(F')∩Follow(F')={*, }∩{,a,( ∧,+,},#}=
毕节学院《编译原理》课程试卷 第 页 共 8 页
7
毕节学院课程考试试卷纸
∴改造后的文法满足LL(1)文法的三个条件，是LL(1)文法。
(3) 预测分析表如下所示。
a b * + ∧ ( ) #
E E→TE' E→TE' E→TE'
E' E'→+E
E'→ E'→
T T→FT' T→FT' T→FT' T→FT'
T' T'→T T'→T T'→T T'→T
T'→ T'→
F F→PF' F→PF' F→PF' F→PF'
F'
F'→ F'→
F'→*F'
F'→ F'→ F'→ F'→ F'→
P P→a P→b P→∧ P→(E)
毕节学院《编译原理》课程试卷 第 页 共 8 页
8
版权声明：本文标题：编译原理半期考试答案 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1735747326a1688020.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论