语法复习题(.doc

一、单项选择题
1．如果文法G是无二义的，则它的任何句子α 。 　A
a. 最左推导和最右推导对应的语法树必定相同
b. 最左推导和最右推导对应的语法树可能不同
c. 最左推导和最右推导必定相同
d. 可能存在两个不同的最左推导，但它们对应的语法树相同
2.语法分析时所依据的是 。A
a. 语法规则 b. 词法规则
c. 语义规则 d. 等价变换规则
3．文法G：S→xSx|y所识别的语言是 。C
a. xyx b. (xyx)*
c. xnyxn (n≥0) d. x*yx*
4.由文法的开始符号出发经过若干步（包括0步）推导产生的文法符号序列称为______B________。
A．语言 B．句型 C．句子 D．句柄
5．在自上而下的语法分析中，应从 C 开始分析。
A．句型 B．句子 C．文法开始符号 D．句柄
6..文法G：S → x xS | y 所识别的语言是（ D　）。
A．xxy* B．(xxy)* C．xx*yx D．(xx)*y
7.文法G：S → xS | y 所识别的语言是（ D　）。
A．xy* B．(xy)*
C．xx*yx D．x*y
8.设有文法G[T]:
T→T*F|F
F→F↑P|P
P→(T)|a
该文法句型T*P↑(T*F)的句柄是下列符号串（ C ）
A.（T*F） B. T*F C. P D. P↑(T*F)
9.最左简单子树的叶结点，自左至右排列组成句型的________C____________。
A．短语 B．句型 C．句柄 D．间接短语

二、填空题
语法分析部分：（基本概念、递归下降子程序）
1． 语法分析的方法通常分为两类： 自上而下分析方法 和 自下而上分析方法 。
2．文法中的终结符集和非终结符集的交集是 空集 。
3．一个句型的最左直接短语称为该句型的___句柄________________。
4．常用的自上而下语法分析方法有递归下降子程序方法和预测分析表方法（LL（1）方法）。
5．关于非终结符A的直接左递归产生式：A→Aα|β，其中α、β是任意的符号串且β不以A开头，则可以将A的产生式改写为右递归的形式为： A→βA’ , A’→αA’|ε000000000000000000000000 。
6．在消除回溯，提取公共左因子时，关于A的产生式A → δβ1 | δβ2 | … | δβi | βi+1 | …| βj，可以改写为： A → δA’ | βi+1 | …| βj ， A’ →β1 | … |βi 。
7．设G[S] 是一文法，如果符号串x是从识别符号推导出来的，即有x，则称x是文法G[S]的____句型__，若x仅由终结符号组成，即，则称x为文法G[S]的__句子 。
三、判断题（第1，2章，第三章概念，递归下降子程序）
1．设r和s分别为正规式，则有L(r|s) = L(r) | L(s).。( × )
2．一个文法的所有句型的集合形成该文法所能接受的语言。( × )
3．语法分析之所以采用上下文无关文法是因为它的描述能力最强。( × )
4．自动机M和M’的状态个数不同，则二者必不等价。( × )
5．最左推导也被称为规范推导。（× ）
6．用高级语言编写的源程序必须经过编译，产生目标程序后才能运行。（ × ）
7．对于任何一个正规式e，都存在一个DFA A，使得L（e）=L（A）。（ √ ）
8．最小化的DFA，它的状态数最小。（ √ ）
9．NFA的确定化算法具有消除ε边的功能。（ √ ）
10．每个非终结符产生的终结符号串都是该语言的子集。（ × ）
11．一个语言的文法是不唯一的。（ √ ）
12．语法错误校正的目的是为了把错误改正过来。（ × ）
13．源程序和目标程序是等价关系。（ √ ）
14．编译程序中错误处理的任务是对检查出的错误进行修改。（ × ）
15．使用有限自动机可以实现单词的识别。（ √ ）
16．一个非确定的有限自动机NFA可以通过多条路径识别同一个符号串。（ √ ）
17．最小化的DFA所识别接受的正规集最小。（ × ）
18．一个语言（如C语言）的句子是有穷的。（ × ）
19．语法分析器可以检查出程序中的所有错误。（ × ）
三、多项选择题
1. 编译器的各个阶段的工作都涉及到（AE　）
A. 表格处理 B. 词法分析
C. 语法分析 D. 语义分析
E. 出错处理
2. 令S＝{a,b}，则S上的符号串的全体可用下面的正规式表示。（ABE　）
A. (a|b)* B. (a*|b*)*
C. (a|b)+ D. (ab)*
E. (a*b*)*
3. 自上而下的分析方法有：（AD　）
A. 递归下降分析法 B. LR（0）分析法
C. LALR（1）分析法 D. LL（1）分析法
E. SLR（1）分析法
4.　文法G：G[S]：S→CD Ab→bA
　　C→aCA Ba→aB
C→bCB Bb→bB
　　AD→aD C→ε
　　BD→bD D→ε
　　Aa→bD
是（ABE　）。
A. 0型文法 B. 1型文法
C. 2型文法 D. 3型文法
E. 上下文有关文法
5.一个编译器可能有的阶段为（ABCDE　）
A. 词法分析 B. 语法分析
C. 语义分析 D. 中间代码生成
E. 目标代码生成
6. 令S＝{a,b}，则S上的所有以b开头，后跟若干个（可为0个）ab的符号串的全体可用下面的正规式表示。（AB　）
A.b (ab)* B. (ba)*b
C. b(a|b)+ D. (ba)+b
E. b (a|b)*
7. 一般来说，编译器可分为前端和后端，下列编译阶段可被划分为编译的前端的有：（ABCDE　）
A. 词法分析 B. 语法分析
C. 语义分析 D. 中间代码生成 E. 中间代码优化
8．下列符号串是符号集S＝{a,b}上的正规式的有：（　ABCDE）
A. ε B.　a C.　ab D.　(ab｜a) (ab｜a)
E.　ab｜ab
9．正规式服从的代数规律有：（ABDE　）
A. “或”运算服从交换律 B. “或”运算服从结合律
C. “连接运算服从交换律 D. “连接”运算服从结合律
E. “连接”运算可对“或”运算进行分配
10． 令S＝{a,b}，则S上的所有以b开头，后跟若干个（可为0个）ab的符号串的全体可用下面的正规式表示。（AB　）
A.b (ab)* B. (ba)*b C. b(a|b)+
D. (ba)+b E. b (a|b)*
五．简答题
1．令文法G[N]为 G[N]: N→D|ND
D→0|1|2|3|4|5|6|7|8|9
给出句子568的最左、最右推导。
解：最左推导：N ND NDD DDD 5DD 56D 568
最右推导：N ND N8 ND8 N68 D68 568

2．给出字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；
解： G[S]：S→aA|bB
A→aS|bC|b
B→bS|aC|a
C→bA|aB|ε
3．对于文法G[E]: E→E+T | T
T→T+P | P
P→(E) | i
写出句型P+T+(E+i)的所有短语、直接短语、句柄。
解：短语：P、P+T、i、E+i、(E+i )、P+T+(E+i )；
直接短语：P、i；
句柄：P；

4．已知文法G[S]: S→aSbS|bSaS|ε
试证明G[S]是二义文法
证明： 该文法产生的语言是a的个数和b的个数相等的串的集合。该文法二义，例如句子abab有两种不同的最左推导。
SaSbSabSabaSbSababSabab
SaSbSabSaSbSabaSbSababSabab

5．构造一文法，使其描述的语言L = {ω |ω ∈ (a, b)*，且ω中含有相同个数的a和b}。
解：
S→ ε| aA|bB
A→ b| bS| aAA
B→ a| aS| bBB
6．已知文法G(S)：
S→S*aP| aP| *aP
P→+aP| +a
(1) 将文法G(S)改写为确定的文法G’(S)；
解：
（1）消除左递归，文法变为：
S→aPS’| *aPS’
S’→ *aPS’ | ε
P→+aP| +a
提取公共左因子，文法变为G’(S)：
S→aPS’| *aPS’
S’→ *aPS’ |ε
P→+aP’
P’→P| ε

7．设有文法G[S]:
S→a|（T）|e
T→T,S|S
试给出句子(a,a,a)的最左推导。
【解】(1) (a,a,a)的最左推导
S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a)

8．设有文法G[S]:
S→S*S|S+S|(S)|i
该文法是否为二义文法,并说明理由？
【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图所示。

9．设有如下文法：
G[E]：E→EWT|T
T→T/F|F
F→（E）|a|b|c
W→+|-
证明符号串a/(b-c)是句子。

解答：有推导EÞTÞT/FÞF/FÞa/FÞa/(E)Þa/(EWT)Þ a/(TWT)Þ a/(FWT)Þ a/(bWT)Þ a/(b-T)Þ a/(b-c)，即从文法开始符号E能够推导出a/(b-c)，所以a/(b-c)是文法G[E]的句子。
10．设有文法G[S]:
S→aAcB|Bd
A→AaB|c
B→bScA|b
该文法句型aAcbBdcc的句柄是_______Bd_____________。