内容发布更新时间 : 2024/12/23 23:16:52星期一 下面是文章的全部内容请认真阅读。
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),S))
(a,(S,S)) (a,((L),S)) (a,((L,S),S))
(a,((a,S),S)) (a,((a,a),S)) (a,((a,a),(L)))
(a,((a,a),(a,S)))
(a,((a,a),(L,S))) (a,((a,a),(a,a)))
(a,((a,a),(S,S)))
(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)) (S,(a,a))
(L,(L,a)) (a,(a,a)
(L,(S,a)) (L,(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,(a,a)))
(L,(L,(L,a))) (L,(S,(a,a)))
(L,(L,(S,a))) (L,((L),(a,a)))
(L,((S,a),(a,a))) (a,((a,a),(a,a)))
(L,((L,S),(a,a))) (L,((a,a),(a,a)))
(L,((L,a),(a,a))) (S,((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 S
aSbS aSbS
abS
abaSbS
ababS
abab
abab
abSaSbS abaSbS ababS
所以此文法是二义性的。
(2)对于句子abab构造两个不同的最右推导。 S S
aSbS aSbS
aSbaSbS aSb
aSbaSb
aSbab
abab
abSaSb abSab abab
(3)对于句子abab构造两棵不同的分析树。 (一)
(二)
(4)此文法所产生的语言是什么?
此文法产生的语言是:所有a的个数与b的个数相等的由a和b组成的字符串。