编译原理期末复习题.doc

一、 名词解释（每小题分，共*分=0分）1、什么叫编译程序？什么叫解释程序？它们两者的区别是什么？编译程序是把源程序翻译成目标语言的程序.编译得到的目标程序再经过连接装配形成可执行程序文件.用户运行可执行程序文件时不再需要源程序和编译程序.解释程序是把源程序翻译成目标语言并执行的程序.解释程序的工作方式是逐条读入源程序中的语句,将该语句翻译成目标语言并执行.用户每次执行同样的程序都需要源程序文件和解释程序.2、请解释源程序，目标程序，遍。源程序是一种计算机的代码。它会符合一定的语法，经过编译器编译或解释后生成具有一定功能的可执行文件或组件，也可以是某种接口。是用程序设计语言编写的程序。目标程序又称“目的程序”。由语言处理程序（汇编程序，编译程序，解释程序）将源程序处理（汇编，编译，解释）成与之等价的由机器码构成的，计算机能够直接运行的程序，该程序叫目标程序。遍指游历，即指令的顺序。有三种顺序：左根右，左右根，根左右。3、请解释字母表，符号串，推导。字母表是符号的非空有穷集合。符号串是由字母表中的符号所组成的任何有穷序列。推导：分直接推导产生式右部代替左部。4、请解释正规式。、请解释句子，句型，上下文无关文法。二、 填空题（每空2分，共10*分=0分）1、有穷自动机分为： 和 、.有穷自动机接受的是 语言.3、已知文法GS的产生式如下： S(L)a L L,SS属于L（GS）的句子是 A ，（a，a）是L（GS）的句子，这个句子的最左推导是 B ，最右推导是 C ，语法树是 D 。A：a a，a （L） （L，）B，C：（）（，）（，）（，）（，） （）（，）（，）（，）（，）（）（，）（，）（，）（，）：、有穷自动机可用五元组（，q0，F）来描述，设有一有穷自动机M定义如下：VT=0，1，Q=q0，q1，q2，F= q2，的定义为：（q0，0）= q1 （q1，0）= q2（q2，1）= q2 （q2，0）= q2M是一个A有限状态自动机，它所能接受的语言可以用正规式B，其含义为CA：歧义的 非歧义的 确定的 非确定的B：(01)* 00(01) * (01) *00 0(01) *0C： 由0和1所组成的符号串的结合以0为头符号和尾符号，由和所组成的符号串的集合以两个结束的，由和所组成的符号串的集合以两个开始的，由和所组成的符号串的集合三、 简要分析题（1、2小题4分，3、4小题6分，共20分）1、文法 G(A,B,S,a,b,c,P,S)其中 P为： SAc|aB Aab Bbc 写出 L(GS)的全部元素。 2、文法 GS为： SAc|aB Aab Bbc 该文法是否为二义的？为什么？ 4、分析DFA与NFA的主要区别？ 四、分析题（每小题15分，共2*15分=0分）1、考虑文法Gbexpr： bexpr-bexpr or btermbterm bterm-bterm or bfactorbfactor bfactor-not bfactor(bexpr) ture