一、名词解释（每小题６分，共５*６分=３0分）1、什么叫编译程序？什么叫解释程序？它们两者的区别是什么？编译程序是把源程序翻译成目标语言的程序.编译得到的目标程序再经过连接装配形成可执行程序文件.用户运行可执行程序文件时不再需要源程序和编译程序.解释程序是把源程序翻译成目标语言并执行的程序.解释程序的工作方式是逐条读入源程序中的语句,将该语句翻译成目标语言并执行.用户每次执行同样的程序都需要源程序文件和解释程序.2、请解释源程序，目标程序，遍。源程序是一种计算机的代码。它会符合一定的语法，经过编译器编译或解释后生成具有一定功能的可执行文件或组件，也可以是某种接口。是用程序设计语言编写的程序。目标程序又称“目的程序”。由语言处理程序（汇编程序，编译程序，解释程序）将源程序处理（汇编，编译，解释）成与之等价的由机器码构成的，计算机能够直接运行的程序，该程序叫目标程序。遍指游历，即指令的顺序。有三种顺序：左根右，左右根，根左右。3、请解释字母表，符号串，推导。字母表是符号的非空有穷集合。符号串是由字母表中的符号所组成的任何有穷序列。推导：分直接推导产生式右部代替左部。4、请解释正规式。５、请解释句子，句型，上下文无关文法。二、填空题（每空2分，共10*２分=２0分）1、有穷自动机分为：和２、.有穷自动机接受的是语言.3、已知文法G[S]的产生式如下：S→(L)∣aL→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）=q2M是一个＿＿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)*0C：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|aBA→abB→bc写出L(G[S])的全部元素。2、文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？4、分析DFA与NFA的主要区别？四、分析题（每小题15分，共2*15分=３0分）1、考虑文法G[bexpr]：bexpr->bexprorbterm︱btermbterm->btermorbfactor︱bfactorbfactor->notbfactor︱(bexpr)︱ture︱false请指出此文法的终结符号、非终结符号和开始符号。试对句子not(trueorfalse)构造一棵语法树。