编译原理期中考试试卷.doc

编译原理期中考试试卷
一、（10分）解释下列术语及概念。

1、字母表：符号的非空有限集合
2、串：符号的又穷序列，句子：属于语言的串
3、字母表的闭包：字母表上的一切符号串的集合
4、编译程序：可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成为一个等
价的、用另一种语言（目标语言）编写的程序。

二义性：若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法
二、（5分）编译程序有那些主要成分构成？各自的主要功能是什么
编译程序的主要成分构成：词法分析程序，语法分析程序，语义分析程序，中间代码生成程序，代码优化程序、目标代码生成程序、表格管理程序及出错处理程序。

词法分析程序：从左到右扫描漏§序，识别单词及其有关属性；
语法分析程序：分析源程序的结构判别它是否为相应程序设计语言中的一个合法程序：
语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息；
中间代码生成程序：将源程序变成一种内部表示形式；
代码优化程序：对前阶段产生的中间代码进行变换或进行改造，使生成的目标代码更为高效目标代码生成程序：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或
汇编指令代码；
表格管理程序：保存编译过程中的各种信息；
出错处理程序：若编译过程中发现源程序存在错误，则报告错误的性质和错误发生的地点，有些还可以自动校正错误。

三、（5分）什么是解释程序？它与编译程序的主要不同是什么？
解释程序接受某个语言的程序并立即运行这个源程序。

它的工作模式是一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员交互方式的工作情况。

而编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序再机器上运行以生成结果。

它们的主要不同在于：解释程序是边解释边执行，解释程序运行结束即可得到该程序的运行结果，而编译程序只是把源程序翻译成汇编或者二进制程序，这个程序再执行才能得到程序的运行结果（当然还有其他不同，比如存储缈只方式不同）
四、（10 分）文法G=（{A, B, S}, （a, b, c）, P, S）其中P 为：
S-Ac|aB
A—ab
B~*bc
写出G[S]所表示的语言。

L （G[S]） =（abc）
五、（10分）文法G[N]为：
N->D|ND
D->0|l|2|3|4|5|6|7|8|9
G[N]表示的语言是什么？
G[N]的语言是VL V= （0,1,2, 3,4, 5,6, 7, 8, 9）
N=>ND=〉NDD.... =>NDDDD... D=>D ... D
六、（10分）写文法，使其语言是偶正整数的集合，要求不允许0打头。

E->NT D
T->FT|G
N->D|1|3|5|7|9
D->2 468
F->N 0
G->D|O
允许0打头
E->NT|D
T->NT|D
N->D|1|3|5|7|9
D->0|2|4|6|8
七、(10 分)DFA 的M=({S,U,V,Q}, {a,b},f,S, {Q}),其中f 为: f(S, a)=U, f(S, b)=V,
f(U, a)=Q
f(U, b)=V, f(V, a)=U, f(V, b)=Q
f (Q, a) =Q, f (Q, b) =Q
画出DFA的状态图。

八、（10分）将下面NFA确定化。

九、（10分）将下面的DFA最小化。

-、(10分)NFA M状态图如下,求正规式R,是L(R)=L(M).
a,b
b
b
a,b
T-一、(10 分)L(R) =(a|b)*(aa|bb) (a|b)*,构造NFA N 使L(N)使与L(R)等价。

9, 10互为答案。