编译原理和技术期末考试复习题

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］的产生式如...