编译原理期末复习题

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：　　 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）= q2

M是一个＿＿A有限状态自动机，它所能接受的语言可以用正规式＿＿B　，其含义为＿＿C　．

A：歧义的   非歧义的  确定的  非确定的

B： (0︱1)*   00(0︱1) *   (0︱1) *00  0(0︱1) *0

C：由0和1所组成的符号串的结合．

以0为头符号和尾符号，由０和１所组成的符号串的集合．

以两个０结束的，由０和１所组成的符号串的集合

以两个０开始的，由０和１所组成的符号串的集合．

三、 简要分析题（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->bexpr or bterm︱bterm

bterm->bterm or bfactor︱bfactor

bfactor->not bfactor︱(bexpr) ︱ture︱false

（1）请指出此文法的终结符号、非终结符号和开始符号。

（2）试对句子not(true or false)构造一棵语法树。