一、填空题(2 )1.若源程序是用高级语言编写的，目标程序是______，则其翻译程序称为编译程序。

2.词法分析和语法分析本质上都是对源程序的______进行分析。

3.如果源语言(编写源程序的语言)是高级语言，而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为_____。

4.对编译程序而言，输入数据是_______,输出结果是________。

5. ______，是构成语言文法的单词，是语法成分的最小单位。

6.由PL／0的EBNF可知，PL／0语言可看成是PASCAL语言的子集，它的编译程序是一个__________。

7.由于PL／0编译程序采用_________，所以语法分析过程BLOCK是整个编译过程的核心。

8.用语法图描述语法规则的优点是______、________。

9.每个非终结符是一个语法成分，在书写语言程序时并不出现，它是由_________和_________、或终结符串定义的。

10.PL／0的目标程序为假想栈式计算机的汇编语言，与具体计算机______。

11.PL／0的编译程序和目标程序的解释执行程序都是用_______书写的，因此PL／0语言可在配备_________的任何机器上实现。

12.PL／0编译程序是用PASCAL语言书写的，整个编译程序(包括主程序)是由______个嵌套及并列的过程或函数组成13.当源程序编译正确时，PL／0编译程序自动调用__________，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。

14.由于对某些非终结符可以递归定义，这就使得_________可用有穷的文法描述。

15. ______的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。

16. PL／0编译程序的语法分析采用了____________。

17.语法分析程序除总控外主要有两大部分的功能，即_________和__________.18.PL／0的词法分析程序GETSYM，是一个独立的过程，其功能是为_________提供单词用的，是______的基础，它把输入的字符串形式的源程序分割成一个个单词符号。

19.每个过程应有过程首部以定义局部于它自己过程的常量、变量和过程标识符，也称_____。

20.词法分析程序GETSYM将完成的任务有:______, 识别保留字；_______,拼数,拼复合词,输出源程序.21.如果一个PL／0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到_________，这时就说所输入的程序是正确的。

22.若要构造程序设计语言的编译程序，则首先要对程序设计语言本身有较为精确的描述。

而关于程序设计语言的描述，将涉及_____、语义和______三个方面。

23.凡是具有某种特殊性质的客体的聚合，都可称为______。

24.如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为_______，记为φ。

25.设有集合A和B，如果A和B有相同的元素，则称这两个集合是_______.26.设A、B为任意两个集合，由所有属于集合A或属于集合B的元素组成的集合，叫做集合A与B的_______．27. 设A、B为任意两个集合，由所有用于集合A且属于集合B的元素组成的集合，称为集合A与B的_______.28. 如果一个集合，它能包含我们所要考虑目标之内的所有元素，则称此集合为_____，记为E。

29.设A为一集合，由A的所有子集(包括空集及A本身)所组成的集合，称为A的______.30. 由两个按一定次序排列的客体组成的序列，称为_____.31. 设A和B为任意两个集合，若序偶的第一个成员是集合A的一个元素，第二个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的__________.32.在集合X上的关系R，如对任意x∈X，均有(x，x) ∈R，则称关系R是______。

33.在集合X上的关系R，如果合(x，y) ∈R，便必有(y，x) ∈R，则称关系R是________。

34.在集合X上的关系R，如果合(x，y) ∈R且(y，z) ∈R，必有(x，z) ∈R，则称关系R 是______。

35.例设 P={（1，2），（3，4），（2，2）}Q={（4，7），（2，9），（3，1）}则P·Q=____________________________36.符号串与符号组成顺序______，如符号串ab______ba，符号申001也______010。

37.假设G是一个文法，S是文法的开始符号，如果S=>*x,则称x是________。

38. 文法G产生的_______的全体是该文法描述的语言。

39.一个文法G[Z]若存在推导序列Z=>+···Z···,则称G(z)是______文法，这类文法所产生的句子有______个。

40.乔姆斯基把文法分成____类型.41.四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是_______.42.最右推导常被称为________。

43.由规范推导所得的句型称为______。

44.文法的二义性和语言的二义性是两个_________的概念。

45.对于上下文无关文法，_______是句型推导过程的几何表示。

46.直接短语也称_______.47.每棵语法树的叶子组成一个______.48.每棵子树的叶子组成一个______.49. 每棵简单子树的叶子组成一个_______.50. 最左边简单子树的叶子组成_______.51.一个句型的最左直接短语称为该句型的_______。

52.关于句型或句子的直接推导"=>"和推导"=>+"，实际上均可视为符号串之间关系，而且推导"=>+"为直接推导"=>"的_________。

53. ________是语言文法的等价表示，可用它来代替BNF规则集合。

54.某条规则U→u中的左部符号U(U不是识别符号)，不在所属文法的任何其他规则右部出现，那么这条规则在推导中不起作用，即所有句子的推导始终不会用到此规则，显然这种规则是多余的。

也称这种非终结符为_________.55.从文法的某个非终结符号U推不出终结符号串，显然，所有含有U的规则是多余的。

也称这种非终结符为________。

56.若L是上下文有关语言、上下文无关语言或正规语言，则L∪{ε}和L - {ε}分别是上下文有关语言、_____和正规语言。

57.设有文法G，对于其中某一非终结符号U可能作出一些不同推导U =>+ Sx，其中S叫头符号，由于推导不同，由U产生的头符号S也可能不同，这些头符号S构成的集合，称为U 的推导的__________.58.一个上下文无关文法G包括四个组成部分依次是：_____,______,_______,_______.59.文法所描述的语言是_______的集合。

60.词法分析器工作的第一步是输入源程序文本。

输入串一般是放在一个缓冲区中，这个缓冲区称________。

61.词法分析的工作(单词符号的识别)可以直接在______中进行。

62.分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置(指向新单词的首字符)，另一个用于_______以寻找单词的终点。

63.在状态转换图中，结点代表____，用圆圈表示。

64.一个状态转换图可用于识别(或接受)一定的______。

65.确定的有穷自动机是一个_____.66.如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个_____作间隔.67.一个程序语言的所有单词符号的识别也可以用________予以描述。

68.转换图容易用程序实现。

最简单的办法是让每个状态结点对应________。

69.程序设计语言中的单词是基本_______。

70.正规式也称正则表达式，也是表示______的工具。

71.一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，_____一个定义同一个语言的正规式。

72.设文法G[A]为：A->[BB->X]|BAX->Xa|Xb|a|b试写出文法G[A]产生的语言对应的正则式。

73. 编译过程中扫描器所完成的任务是从______中识别出一个个具有______。

74. 确定的有穷自动机是一个______，通常表示为______。

75.递归下降分析器的优点是程序结构和_____清晰明了，易于手工实现；且_________。

76.与那些使用部分自动化系统的方法相比，递归下降分析方法的主要缺点是需要做更多的工作：更多的编写程序工作和更多的_______。

77.文法具有递归性。

消除文法的左递归不等于消除了文法的________.78、自顶向下语法分析方法的基本思想是：从______出发，不断建立____ ，试图构造一个推导序列，最终由它推导出与输入符号串相同的____。

79.实现LL（1）分析的另一种有效方法是使用____和____进行联合控制.80.一个预测分析器是由预测分析程序,__ __，____三个部分组成。

81、自顶向下语法分析方法会遇到的主要问题有______和______。

82、LL(1)分析法中，第一个L的含义是______，第二个L的含义是______，“1”的含义是______。

83.所谓____就是从输入串开始，逐步进行"归约"，直至归约到文法的开始符号.84.自底向上分析的中心问题是，怎样判断栈顶的符号串的____，以及____。

85.各种不同的自底向上分析法的一个共同特点是，边____，边归约。

86、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行______，试图______到文法的______。

87. 算符优先关系表可由______和______.88. 为了求算符优先关系表,我们定义了如下两个集合____和____.89.规范归约(最左归约-最右推导的逆过程)的关键问题是____。

90.一个LR分析器实质上是一个带先进后出存储器(栈)的_____.91.LR分析器的核心部分是____。

92.LR（0）分析表构造的思想和方法是构造其他LR分析表的____。

93、LR(0)分析法的名字中，“L”的含义是______，“R”的含义是______，“0”的含义是______。

94.算符优先分析法的归约过程与规范归约是____。

95.设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他素短语。