编译原理期末复习题.doc

一、名词解释（每小题６分，共５*６分=３0分）
1、什么叫编译程序？什么叫解释程序？它们两者的区别是什么？
编译程序是把源程序翻译成目标语言的程序.编译得到的目标程序再经过连接装配形成可执行程序文件.用户运行可执行程序文件时不再需要源程序和编译程序.
解释程序是把源程序翻译成目标语言并执行的程序.解释程序的工作方式是逐条读入源程序中的语句,将该语句翻译成目标语言并执行.用户每次执行同样的程序都需要源程序文件和解释程序.

2、请解释源程序，目标程序，遍。
源程序是一种计算机的代码。它会符合一定的语法，经过编译器编译或解释后生成具有一定功能的可执行文件或组件，也可以是某种接口。是用程序设计语言编写的程序。
目标程序又称“目的程序”。由语言处理程序（汇编程序，编译程序，解释程序）将源程序处理（汇编，编译，解释）成与之等价的由机器码构成的，计算机能够直接运行的程序，该程序叫目标程序。
遍指游历，即指令的顺序。有三种顺序：左根右，左右根，根左右。

3、请解释字母表，符号串，推导。
字母表是符号的非空有穷集合。符号串是由字母表中的符号所组成的任何有穷序列。推导：分直接推导产生式右部代替左部。

4、请解释正规式。

５、请解释句子，句型，上下文无关文法。

二、填空题（每空2分，共10*２分=２0分）
1、有穷自动机分为：和
２、.有穷自动机接受的是语言.
3、已知文法G[S]的产生式如下：
S→(L)∣a
L→L,S∣S
属于L（G[S]）的句子是A，（a，a）是L（G[S]）的句子，这个句子的最左推导是B，最右推导是C，语法树是D。
A：eq\o\ac(○,1)aeq\o\ac(○,2)a，aeq\o\ac(○,3)（L）eq\o\ac(○,4)（L，ａ）
B，C：eq\o\ac(○,1)Ｓ＝＞（Ｌ）＝＞（Ｌ，Ｓ）＝＞（Ｌ，ａ）＝＞（Ｓ，ａ）＝＞（ａ，ａ）
eq\o\ac(○,2)Ｓ＝＞（Ｌ）＝＞（Ｌ，Ｓ）＝＞（Ｓ，Ｓ）＝＞（Ｓ，ａ）＝＞（ａ，ａ）
eq\o\ac(○,3)Ｓ＝＞（Ｌ）＝＞（Ｌ，Ｓ）＝＞（Ｓ，Ｓ）＝＞（ａ，Ｓ）＝＞（ａ，ａ）
Ｄ：

３、有穷自动机可用五元组（Ｑ，ＶＴ，δ，q0，F）来描述，设有一有穷自动机M定义如下：
VT={0，1}，Q={q0，q1，q2}，F={q2}，δ的定义为：
δ（q0，0）=q1δ（q1，0）=q2
δ（q2，1）=q2δ（q2，0）=q2
M是一个＿＿A有限状态自动机，它所能接受的语言可以用正规式＿＿B，其含义为＿＿C．
A：eq\o\ac(○,1)歧义的eq\o\ac(○,2)非歧义的eq\o\ac(○,3)确定的eq\o\ac(○,4)非确定的
B：eq\o\ac(○,1)(0︱1)*eq\o\ac(○,2)00(0︱1)*eq\o\ac(○,3)(0︱1)*00eq\o\ac(○,4)0(0︱1)*0
C：eq\o\ac(○,1)由0和1所组成的符号串的结合．
eq\o\ac(○,2)以0为头符号和尾符号，由０和１所组成的符号串的集合．
eq\o\ac(○,3)以两个０结束的，由０和１所组成的符号串的集合
eq\o\ac(○,4)以两个０开始的，由０和１所组成的符号串的集合．
三、简要分析题（1、2小题4分，3、4小题6分，共20分）
1、文法G＝({A,B,S},{a,b,c},P,S)其中P为：
S→Ac|aB
A→ab
B→bc
写出L(G[S])的全部元素。

2、文法G[S]为：
S→Ac|aB
A→ab
B→bc
该文法是否为二义的？为什么？

4、分析DFA与NFA的主要区别？

四、分析题（每小题15分，共2*15分=３0分）
1、考虑文法G[bexpr]：
bexpr->bexprorbterm︱bterm
bterm->btermorbfactor︱bfactor
bfactor->notbfactor︱(bexpr)︱ture︱false
请指出此文法的终结符号、非终结符号和开始符号。
试对句子not(trueorfalse)构造一棵语法树。