2.1 考虑文法G[S],其产生式如下: S→(L)|a L→L，S|S
(1) 试指出此文法的终结符号、非终结符号。
,,
终结符号为：{(,),a,} 非终结符号为：{S,L} 开始符号为：S
(2)给出下列各句子的分析树：
① (a,a)
②(a,(a,a))
③ (a,((a,a),(a,a)))
(3)构造下列各句子的一个最左推导： ① (a,a)
S (L) (L,S) (S,S) (a,S) (a,a) ② (a,(a,a))
S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S)) (a,(S,S)) (a,(a,S)) (a,(a,a)) ③ (a,((a,a),(a,a)))
S (L) (L,S) (S,S) (a,S) (a,(L)) (a,(L,S)) (a,(S,S)) (a,((L),S)) (a,((L,S),S)) (a,((S,S),S)) (a,((a,S),S)) (a,((a,a),S)) (a,((a,a),(L)))
(a,((a,a),(L,S))) (a,((a,a),(S,S))) (a,((a,a),(a,S))) (a,((a,a),(a,a)))
(4)构造下列各句子的一个最右推导： ①(a,a)
S (L) (L,S) (L,a) (S,a) (a,a) ②(a,(a，a))
S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,a)) (L,(S,a)) (L,(a,a)) (S,(a,a)) (a,(a,a) ③(a，((a，a)，(a，a))
S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,(L))) (L,(L,(L,S))) (L,(L,(L,a))) (L,(L,(S,a))) (L,(L,(a,a))) (L,(S,(a,a))) (L,((L),(a,a)))
(L,((L,S),(a,a))) (L,((L,a),(a,a))) (L,((S,a),(a,a))) (L,((a,a),(a,a))) (S,((a,a),(a,a))) (a,((a,a),(a,a))) (5)这个文法生成的语言是什么？
...
L(G[S]) = (α1,α2,,αn)或a
其中αi(1≤i≤n)，即L(G[S])是一个以a为原子的纯表，但不包括空表。 2.2 考虑文法G[S] S→aSbS|bSaS|ε
(1)试说明此文法是二义性的。可以从对于句子abab有两个不同的最左推导来说明。 S aSbS abS abaSbS ababS abab
S aSbS abSaSbS abaSbS ababS abab 所以此文法是二义性的。
(2)对于句子abab构造两个不同的最右推导。
S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab (3)对于句子abab构造两棵不同的分析树。 (一)
(二)
(4)此文法所产生的语言是什么？
此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。 2.4 已知文法G[S]的产生式如下：S → (L)|a L → L,S|S
属于L(G[S])的句子是 A ，(a,a)是L(G[S])的句子，这个句子的最左推导是 B ，最右推导是 C ，分析树是 D ，句柄是 E 。
A：① a ② a,a ③ (L) ④ (L,a)
B,C：① S (L) (L,S) (L,a) (S,a) (a,a) ② S (L) (L,S) (S,S) (S,a) (a,a)
③ S D：
(L) (L,S) (S,S) (a,S) (a,a)
E：① (a,a) ② a,a ③ (a) ④ a
解答： A：① B：③ C：① D：② E：④
3.1 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述,设有一有限状态自动机M的定义如下：
VT={0,1}，Q={q0,q1,q2}，Qf={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2
δ（q2，1）=q2 δ（q2，0）=q2
M是一个 A 有限状态自动机，它所对应的状态转换图为 B ,它所能接受的语言可以用正则表达式
表示为 C 。其含义为 D 。
A: ①歧义的 ②非歧义的 ③确定的 ④非确定的 B:
C： ①(0|1) ②00(0|1) ③(0|1)00 ④0(0|1)0 D：①由0和1所组成的符号串的集合；
②以0为头符号和尾符号、由0和1所组成的符号串的集合； ③以两个0结束的，由0和1所组成的符号串的集合；
*
*
*
*
④以两个0开始的，由0和1所组成的符号串的集合。
答案 A:③ B:② C:② D:④ 3.2 (1)有穷自动机接受的语言是正则语言。（） (2)若r1和r2是Σ上的正规式，则r1|r2也是。（）
(3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。
**
(4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b(a|b)。 (5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（）
(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（） 答案 (1) T (2) T (3) F (4) F (5) T 3.3 描述下列各正规表达式所表示的语言。
*
(1) 0(0|1)0
**
(2) ((ε|0)1)
*
(3) (0|1)0(0|1)(0|1)
****
(4) 0101010
****
(5) (00|11)((01|10)(00|11)(01|10)(00|11))
*
答案 (1) 以0开头并且以0结尾的，由0和1组成的所有符号串(2) {α|α∈{0,1}}
即由0和1组成的所有符号串。
(3) 由0和1组成的符号串，且从右边开始数第3位为0。
(4) 含3个1的由0和1组成的所有符号串。 {α|α∈{0,1}+，且α中含有3个1 }
*
(5) {α|α∈{0,1},α中含0和1的数目为偶数。}
4.10 已知文法G[S]，其产生式如下：S→(L)|a L→L,S|S
文法G[S]的算符优先关系由下表给出。建立与下表相应的算符优先函数并用算符优先分析法分析句子(a,(a,a))。
文法G[S]的算符优先关系表：
解：对每个终结符或＄建立符号f与g，把f(和g)分成一组。 根据G[S]的算符优先关系表，画出如下的有向图:
优先函数如下：
用算符优先分析法分析句子(a,(a,a))
4.19 (1) 存在有左递归规则的文法是LL(1)的。 (2) 任何算符优先文法的句型中不会有两个相邻的非终结符号。
(3) 算符优先文法中任何两个相邻的终结符号之间至少满足三种 关系(＜·，·＞，一。
)之
编译原理和技术期末考试复习题
