题目

第1题,编译程序的工作情况有三种，分别是解释型、编译型和（）。
A、综合型
B、并列型
C、汇编型
D、不确定型
正确答案: C

第2题,文法中不包含左公共因子是LL(1)文法的（）。
A、充分条件
B、必要条件
C、充要条件
D、即不充分也不必要的条件
正确答案: B

LL(1)方法要求：无左递归、无公共左因子

第3题,在规范归约中用来刻画可归约串的是（）。
A、短语
B、句柄
C、最左素短语
D、素短语
正确答案:B

在"算符优先分析"中，用“最左素短语”来刻画“可归约串”

在“规范归约”分析中，则用“句柄”来刻画“可归约串”。

句柄：直接短语中的最左直接短语为该句型的句柄

素短语：是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语

最左素短语：最左素短语就是句型定义的素短语

4.中间代码设计原则是（）。
A、简洁，占用内存少
B、接近自然语言
C、可替代编译程序
D、容易生成和翻译为目标代码
正确答案:D

第6题,设有文法G[S]： S→S8|S9|Sa|Sc|a|b|c
下列句子中符合该文法的有（）。①ab9 ②a9c98 ③aaa ④bc89
可选项有：
A、①
B、②③④
C、③④
D、①②③④
正确答案:B

第7题,编译程序工作的后端包含的阶段有（）。
A、语义分析、代码优化、代码生成
B、词法分析、语法分析、代码生成
C、中间代码生成、代码优化、代码生成
D、语义分析、中间代码生成、代码优化
正确答案:C

编译前端主要包括词法分析、语法分析、语义分析、中间代码生成这几个部分，后端则包含代码优化和目标代码生成部分。前端的特点是仅与编译的源语言有关，而后端则仅与编译的目标语言及运行环境有关

编译程序工作时，先分析，后综合，从而得到目标程序。
分析指的是：词法分析、语法分析、语义分析。
综合指的是：代码优化，存储分配、代码生成。

第8题,一个句型中称为句柄的是该句型的最左（）。
A、最左终结符号
B、所有短语
C、所有句子
D、最左直接短语
正确答案:D

同3

第9题,设文法G[S]：S→SB|B ，B→0|b
则对句子0b0，以下推导为规范推导的是（）。
A、S SB SBBBBB0BB0bB0b0
B、S SB SBBBBBBB0Bb00b0
C、S SB SBBSB0Sb0Bb00b0
D、S SB S0 SB0 Sb0 Bb0 0b0
正确答案:D

最右推导也称为规范推导,用规范推导推导出的句型称为规范句型。
规范推导的逆过程,称为最左归约,也称为规范归约。

第11题,一个LR分析器由三部分组成，分别是总控程序、分析表和（）。
A、运算器
B、缓冲器
C、记录表
D、分析栈
正确答案:D

LR文法是最大的、可以构造出相应的移入-归约语法分析器的文法类，其中L表示的是对输入进行从左到右的扫描，而R代表的就是反向构造出一个最右的推导序列

LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程

1、总控程序**，**也可以称为驱动程序。对所有的LR分析器来说，总控程序都是相同的

2、分析表或分析函数。不同的文法分析表会不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可以分为动作(ACTION)表和状态转换(GOTO)表两个部分，它们都可用二维数组表示

3、分析栈，包括文法符号栈和相应的状态栈，它们都是先进后出栈分析器不需向前查看输入符号

第13题,扫描器识别出的具有独立含义的最小语法单位是（）。
A、算符
B、单词
C、字符
D、表达式
正确答案:B

第16题,占用编译程序绝大多数时间的模块是（）。
A、出错处理
B、词法分析
C、目标代码生成
D、管理表格
正确答案:D

编译的每个阶段所需要的信息多数从表格中读取，产生的中间结果都记录在相应的表格中，可以说整个编译过程就是造表、查表的过程。

第17题,一个短语文法G包括以下组成部分：有限个终结符，有限个非终结符，一个开始符号，以及一组（）。
A、运算符
B、产生式
C、数符
D、句子
正确答案:

由文法G[S]的开始符S经n步(n≥0)推导产生的文法符号序列α是（）。
A、待选式
B、句子
C、句型
D、正规式
正确答案:C

乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中2型文法
是（B）。
A、正则文法B、上下文无关文法C、上下文有关文法D、短语文法

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
S-> aaS|a是什么型的，为什么
S-> aSb|ab是什么型的，为什么
S-> SaS|b是什么型的，为什么
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

答：三种文法都属于上下文无关文法,2型文法。

四种文法的判断非常简单，说到到，四种文法就是规定产生式的左和右边的字符的组成规则不同而已，其它的不能理解就不要去想了，你只要知道判断的时候就是以产生式的左边和右边符合的规则进行判断。下面解释一下如何根据产生式左边和右边的特征来进行判断。

首先，应该明确，四种文法，从0型到3型，其规则和约定越来越多，限制条件也越来越多，所以，我们判断时可以从最复杂的3型进行判断，依次向下判断，如果不符合3型的，那再看是不是2型的，不是2型的，再看是不是1型的，当然，对于作题作的熟的朋友，不用这么复杂，可以一眼直接看出来。

【正规文法】3型文法遵循什么规范呢？
第一点：左边必须只有一个字符，且必须是非终结符；
第二点：其右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。【右边至少有一个终结符】
第三点：对于3型文法中的所有产生式，其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须前面是终结符而后面是非终结符。反之亦然，要么，就全是：非终结符＋终结符。 S->aS|bS，不能是S->aS|Sb

依以上规则判断，你所给的三个文法显然都不属于3型文法。

【上下无关文法】2型文法如何判断：
第一点：与3型文法的第一点相同，即：左边必须有且仅有一个非终结符。
第二点：2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。

依2型文法的判断规则，你的三个文法都属于2型文法，即：上下文无关文法。

【上下有关文法】1型文法如何判断：
第一点：1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。
第二点：与2型文法第二点相同。

依1型文法判断规则，显然，你的文法也是属于1型的。

最后是0型文法，这个就不用看了，只要你能描述出来，都属于这个类型，即0型。

所以，取其最高的符合规则，最后的答案是其符合：上下文无关文法规则，即2型。

本人补充:一般考试里面分辨0型文法(短语结构文法)和2型文法(上下文无关文法)!!!

左部长度>右部长度一点是0型文法(短语结构文法)

一个递归文法所产生的语言的句子是（）。
A、无穷个
B、有穷个
C、可枚举
D、无法确定
正确答案:A

第19题,在自顶向下的语法分析处理中，FIRST集、FOLLOW集、SELECT集均是（）。
A、非终结符集
B、终结符集
C、字母表
D、状态集合
正确答案:

第22题,编译程序第三步工作是（）。
A、语义分析
B、词法分析
C、语法分析
D、代码优化
正确答案:A

第23题,常用的中间代码形式有（）。
A、状态机
B、四元式
C、转换表
D、语法树
正确答案:B

逆波兰表示、四元式、三元式和树表示等

第28题,编译程序中语法分析器的输入是（）。
A、单词
B、表达式
C、直接短语
D、句柄
正确答案:A

有限自动机识别的语言是（）。
A、短语文法语言
B、上下文有关文法语言
C、上下文无关文法语言
D、正规文法语言
正确答案:D

如果一个文法存在某个句子对应两颗不同的语法树，则该文法是二义的。（）
T、对
F、错
正确答案:T

如果一个文法存在某个句子对应两棵不同的语法树,则说这个文法是二义性的。

或者说,若一个文法中存在某个句子,它有两个不同的最左(最右)推导,则这个文法是二义性的。

设有文法 G [ E ]:

1 2	E → E + E \| E * E \| ( E ) \| i 1

句子 i * i + i 有两个不同的最左推导,对应两棵不同的语法树,见图 2.6 和图 2.7 。

最左推导 1

 E ⇒ E + E ⇒ E * E + E 
    ⇒ i * E + E
     ⇒ i * i + E
    ⇒ i * i + i 
    
12345

最左推导 2

E ⇒ E * E ⇒ i * E
 ⇒ i * E + E
 ⇒ i * i + E
 ⇒ i * i + i

第33题,简单优先文法中，任意两个产生式不允许具有相同右部。（）
T、对
F、错
正确答案:T

简单优先文法的性质

在文法符号V中，任意两个字符之间只存在唯一的一种关系（等于，小于或者大于）

文法中，任意两个产生式没有相同的右部【如：A → bc，B → bc，这样规约的时候就不知道该规约到谁，保证规约的一致性】

第36题,已知文法G[S]：S→A B|PQx， A→xy ，B→bc ，P→d P|ε ，Q→aQ|ε
该文法是LL（1）文法。（）
T、对
F、错
正确答案:T

第37. 给出奇数集的上下文无关文法，且每个奇数不以0开头

答

N->AB|B

A->AC|D 【若只有A->D，则这个数不会出现0】

B->1|3|5|7|9

D->B|2|4|6|8

C->0|D 【C->0保证这个数可以有0，但0不开头】

第38. 给出语言L={a^m^ b a^n^ |m,n>=0}的正规文法

正规文法：只能是左线性或右线性文法，左边一个非终结符。右边最多两个字符，而且右边必须包含一个终结符

答

S->aS|bB

B->aB|e[空]

【给的是右线性文法，右线性文法：A-> αB 或 A-> α 。非终结符只能靠右】

第39. NFA转DFA题目

答

先确定化

确定化中，因为这是包含空串的，每次求完a/b后还要求空串的闭包

如：{B} 在a下为{A}，再求{A}对空串的闭包为{Z}，所以{B}在a下为**{A,Z}**

再最小化

最后0、1合并在一起

题目40. 题目

消除回溯：提取最左公共因子

答

对L->L,S|S消除左递归

对S->(L)|aS|a提取最左公因子

得到下面四个文法

First集

Follow集

求First原因：不希望回溯，希望【根据读头下面的符号选择相应的后选式】，那就得知道候选式的第一个符号是什么

但当某个符号 可以用空串替换时，需要求Follow集，知道这个符号后面的符号是什么

题目41.题目

对文法G构造算符优先表

判断是否为算符文法
构造FirstVt和LastVt
根据优先关系构造表

答

先对文法进行扩展：S’->#S#；保证文法开始符号不出现在任何产生式右部，即增加产生式S’->S，并令S’→●S作为初态项目;

题目42.