编译原理题库——简答题.doc

编译原理A
1. 简要说明语义分析的基本功能。
2. 考虑文法 G[S]:
S → (T) | a+S | a
T → T,S | S
消除文法的左递归及提取公共左因子。
3试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。
4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列：
while (A<C ∧ B<D)
{
if (A ≥ 1) C=C+1;
else while (A ≤ D)
A=A+2;
}。
5. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。
A答案
1答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。
2解：消除文法G[S]的左递归：
S→(T) | a+S | a
T→ST′
T′→,ST′| ε
提取公共左因子：
S→(T) | aS′
S′→+S | ε
T→ST′
T′→,ST′| ε

3答：w a b + c d e 10 - / + 8 + * +
4答：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)：
100 (j<,A,C,102)
101 (j,_,_,113)
102 (j<,B,D,104)
103 (j,_,_,113)
104 (j=,A,1,106)
105 (j,_,_,108)
106 (+, C, 1, C)
107 (j,_,_,112)
108 (j≤,A,D,110)
109 (j,_,_,112)
110 (+, A, 2, A)
111 (j,_,_,108)
112 (j,_,_,100)
113
5答：证明： 　　　
　　由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：

因此，文法G[S]为二义文法。 　　
编译原理B
1. 什么是句子？ 什么是语言 ?
2. 写一文法，使其语言是偶正整数的集合,要求：
   (1)允许0打头；
   (2) 不允许0打头。
3. 已知文法 G[E] 为：
    E→T|E+T|E-T
    T→F|T*F|T/F
    F→ （ E ） |i
① 该文法的开始符号（识别符号）是什么？
② 请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。
③ 找出句型 T+T*F+i 的所有短语、简单短语和句柄。
4. 构造正规式相应的 NFA : 1(0|1)*101。
5. 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列。
B卷答案
1答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。
(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈VT*} 。
2解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)
P:
S->PD|D
P->NP|N
D->0|2|4|6|8
N->0|1|2|3|4|5|6|7|8|9
(2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)
P:
S->PD|P0|D
P->NR|N
R->QR|Q
D->2|4|6|8
N->1|2|3|4|5|6|7|8|9
Q->0|1|2|3|4|5|6|7|8|9
3解：① 该文法的开始符号（识别符号）是E。
②该文法的终结符号集合VT={+、-、*、/、（、）、i}。 非终结符号集合VN={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i; 简单短语为i、T*F、第一个T;句柄为第一个T。
4解：1(0|1)*101对应的NFA为
5解：逆波兰表示： 　　　　　abc*＋ab＋/d－　　　　 　　　　　
三元式序列： 　　　　　 ① (*，b，c) 　　　　　 ② (＋，a，①) 　　　　　 ③ (＋，a，b) 　　　　　 ④ (/，②，③) 　　　　　 ⑤ (－，④，d)
编译原理C
1．(10分) 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。
（1） else 没有匹配的if
（2） 数组下标越界
（3） 使用的函数没有定义
（4） 在数中出现非数字字符
（5）函数调用时实参与形参类型不一致。
2．(15分) 构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1 都有0 直接跟在右边。并给出该语言的正规式
3．(10分) 为下面的语言设计文法：
（1） {ambn, 其中m ³ n }
（2） {w | wÎ{a, b}*，w的长度为奇数}
证明 E + T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。
5．(15分) 给定文法：
E → E + T | E - T |T
T → T * F | T / F |F
F → (E) | id
C卷答案
1答案：（每小题2分）
（1） 语法分析
（2） 语法分析
（3） 语义分析
（4） 词法分析
（5） 语义分析
2答案：
按题意相应的正规表达式是(0*10)*0*，或0*(0 | 10)*0* ，构造相应的DFA。

3答案：（每小题 10分）
（1）考虑在先产生同样数目的a,b，然后再生成多余的a。以下是一种解法：
S → aSb | aS | ε
（2） A → aB | bB
B → aA | bA | ε
5证明 E + T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。
答：，
短语：id，（id）， T*（id）， E+ T*（id）。
直接短语：id。
句柄是id。
编译原理D卷
3、何谓“标识符”，何谓“名字”，两者的区别是什么？
4、令 ＋、* 和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1＋1*2↑*1↑2的值：
（1）、优先顺序（从高至低）为＋、* 和↑，同级优先采用左结合。
（2）、优先顺序为↑、＋、*，同级优先采用右结合。
6、令文法G6为N→D∣ND，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9
（1）、G6的语言L(G6)是什么？
（2）、给出句子0127、34和568的最左推导和最右推导。
7、写一个文法，使其语言是奇数集，且每个奇数不以0开头。
8、令文法为E→T∣E+ T∣E-T
T→F∣T*F∣T/F
F→(E)∣i
（1） 给出i+i*i、i*(i+i)的最左推导和最右推导；
给出i+i+i、i+i*i和i-i-i的语法树。
9、证明下面的文法是二义的：S→iSeS∣iS∣i
11、给出下面语言的相应文法：
L1={anbnci∣n≥1，i≥0}，
L2={aibncn∣n≥1，i≥0}
L3={anbnambm∣n，m≥0}
L4={1n0m1m0n∣n，m≥0}
3解：标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线开头的，由数字、字母和下划线组成的一定长度的字符串，它只是一个标志，没有其他含义。名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值。
4解：
（1）、1＋1*2↑*1↑2 = 2*2↑*1↑2 = 4↑*1↑2 = 4↑↑2 =
（2）、1＋1*2↑*1↑2 =
6解：
（1）、L(G6)是由0到9这10个数字组成的字符串。
（2）、句子0127、34和568的最左推导：
N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127
N=>ND=>DD=>3D=>34
N=>ND=>NDD=>DDD=>5DD=>56D=>568
句子0127、34和568的最右推导：
N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127
N=>ND=>N4=>D4=>34
N=>ND=>N8=>ND8=>N68=>D68=>568
7解：
G(S)：A→2∣4∣6∣8∣D
B→A∣0
C→CB∣A
D→1∣3∣5∣7∣9
S→CD∣D
8解：
（1） 最左推导为：
E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*i
E => T => T*F => F*F => i*F => i*(E) => i*(E+ T) => i*(T+ T)
=> i*(F+ T) => i*(i+ T) => i*(i+ F) => i*(i+ i)
最右推导为：
E =>E+T =>E+T*F =>E+T*i =>E+F*i =>E+i*i => T+i*i => F+i*i => i+i*i
E => T => T*F => F*F => F*(E) => F*(E+T) => F*(E+ F) => F*(E+ i)
=> F*(T+i) => F*(F+i) => F*(i+i) => i*(i+ i)
（2） 语法树：
T
E
+
E
F
i
+
T
F
i
i
E
+
T
E
F
i
*
T
F
i
T
F
i
E
E
-
T
E
F
i
T
F
i
-
F
i

9解：考虑句子iiiei，存在如下两个最右推导：
S=>iSeS=>iSei=>iiSei=>iiiei
S=>iS=>iiSeS=>iiSei=>iiiei
由此该文法是二义的。
11解：
L1的文法：S→AC；A→aAb∣ab；C→cC∣ε
L2的文法：S→AB；A→aA∣ε；B→bBc∣bc
L3的文法：S→AB；A→aAb∣ε；B→aBb∣ε
L4的文法： S→1S0∣A； A→0A1∣ε；

编译原理E卷
1、 令A、B和C是任意正规式，证明以下关系成立：
A∣A=A
(A*)*= A*
A*=ε∣A A*
(AB)*A=A(BA)*
(A∣B)*=(A*B*)*=(A*∣B*)*
A=b∣aA当且仅当A=a*b
2、 构造下列正规式相应的DFA
1(0∣1)*101
1(1010*∣1(010)*1)*0
0*10*10*10*
(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)*
3、 给出下面正规表达式：
（1） 以01结尾的二进制数串；
（2） 能被5整除的十进制整数；
包含奇数个1或奇数个0的二进制数串；

4、 对下面情况给出DFA及正规表达式：
（1）{0，1}上不含子串010的所有串。
5、 将图3.18的（a）和（b）分别确定化和最小化。
1
0
a，b
a
a
(a)

2
0
b
a
a
(b)
1
5
4
3
b
b
b
b
b
a
a
a
a
a

6、 构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。、
7、 给定右线性文法G：
S→0S∣1S∣1A∣0B
A→1C∣1
B→0C∣0
C→0C∣1C∣0∣1
求出一个与G等价的左线性文法。
文法G对应的状态转换图如下所示：
S
Z
1
0
0，1
B
C
A
1
0，1
0，1
0
0
1

E卷答案

1证明：
（1）、A∣A=A
L(A∣A)=L(A)∪L(A)=L(A)，所以有A∣A=A。
（2）、(A*)*= A*

（3）、A*=ε∣A A*
通过证明两个正规式所表示的语言相同来证明两个正规式相等。
L(ε∣A A*)=L(ε)∪L(A)L(A*)= L(ε)∪L(A)(L(A) )*
=L(ε)∪L(A)((L(A))0∪(L(A))1∪(L(A))2∪(L(A))3∪…)
=L(ε)∪(L(A))1∪(L(A))2∪(L(A))3∪(L(A))4∪…
=(L(A))*=L(A*)
即：L(ε∣A A*)=L(A*)，所以有：A*=ε∣A A*
（4）、(AB)*A=A(BA)*
利用正规式的分配率和结合律直接推导。
(AB)*A=((AB)0∣(AB)1∣(AB)2∣(AB)3∣…)A
=εA∣(AB)1A∣(AB)2A∣(AB)3A∣…
=Aε∣A (BA)1∣A (BA)2∣A (BA)3∣…
=A(ε∣(BA)1∣(BA)2∣(BA)3∣…)
=A(BA)*
即：(AB)*A=A(BA)*
（5）、(A∣B)*=(A*B*)*=(A*∣B*)*
证明:先证(A∣B)*=(A*B*)*
因为L(A)L(A) *L(B) *,L(B) L(A) *L(B) *
故:L(A) ∪L(B) L(A) *L(B) *
于是由本题第二小题结论可知(L(A)∪L(B)) *(L(A) *L(B)*)* ①
又L(A)L(A)∪L(B), L(B) L(A)∪L(B)
故:L(A)*(L(A)∪L(B))*
L(B)*(L(A)∪L(B))*
因此有:L(A)*L(B)* (L(A)∪L(B))* (L(A)∪L(B))*=( (L(A)∪L(B))*) 2
故(L(A)*L(B)*)*((L(A)∪L(B))*)*
由本题第二小题得: ((L(A)∪L(B))*)*= (L(A)∪L(B)) *
故得: (L(A)*L(B)*)*(L(A)∪L(B)) * ②
则由①②得: (L(A)∪L(B)) *=(L(A)*L(B)*)*
由于L((A*B*))*=(L(A*B*))*=(L(A*)L(B*))*=(L(A)*L(B)*)*
即有(L(A)∪L(B))*=L((A*B*))* ③
而(A|B)*对应的语言为(L(A)∪L(B))*,且(A*B*)*对应的语言为L((A*B*))*
则根据③得(A|B)*=(A*B*)*
再证:(A*|B*)*=(A*B*)*
因为:A,B是任意正规式,由以上结论得: (A*|B*)*=((A*)*(B*)*)*
又由本题第二小题目的结论可得：（A*）*=A*，（B*）*=B*
因此，（A*|B*）*=（A*B*）*
综合上述两种结论，最后得：(A∣B)*=(A*B*)*=(A*∣B*)*
2解：
(1)、1(0∣1)*101
第一步：根据正规式构造NFA，先引入初始状态X和终止状态Y：
X
1(0∣1)*101
Y

再对该转换图进行分解，得到分解后的NFA如下图：
X
1
2
3
4
5
Y
1
ε
1
0
1
ε
0
1

第二步：对NFA进行确定化，获得状态转换矩阵：
状态
0
1
{X}
Ø
{1，2，3}
{1，2，3}
{2，3}
{2，3，4}
{2，3}
{2，3}
{2，3，4}
{2，3，4}
{2，3，5}
{2，3，4}
{2，3，5}
{2，3}
{2，3，4，Y}
{2，3，4，Y}
{2，3，5}
{2，3，4}
根据转换矩阵获得相应的DFA：
0
1
2
3
4
1
0
0
0
1
0
1
1
1
5
0
1

第三步：化简该DFA，获得最简的DFA即为所求。
首先根据是否终止状态将所有状态分为两个集合{0，1，2，3，4}和{5}，这里集合{5}已经不可划分，只需考虑集合{0，1，2，3，4}。
{0，1，2，3，4}0={2，4，-}，{0，1，2，3，4}1={1，3，5}
因为{1，3，5}和{2，4，-}不在一个集合里面，所以需要对集合{0，1，2，3，4}进行进一步的划分，检查其中的所有状态。状态0不能接受字符0，需要把状态0划分出来；另外，只有状态4读入字符1后进入状态5，因此将状态4划分出来，划分的结果为4个集合：{0}，{1，2，3}，{4}，{5}。
检查集合{1，2，3}，{1，2，3}0={2，4}，不属于同一个集合，因此要对集合{1，2，3}进行进一步划分，划分结果为5个集合：{0}，{1，2}，{3}，{4}，{5}。
检查集合{1，2}，{1，2}0={2}，{1，2}1=3，不需要进行进一步划分。所以最终划分结果为5个集合：{0}，{1，2}，{3}，{4}，{5}。
所以，最终所求DFA如下图示：
0
1
3
4
1
0
0
1
0
1
1
5
0
1

3解：
（1）以01结尾的二进制数串；
(1︱0)*01。
（2）能被5整除的十进制整数；
(1︱2︱3︱4︱5︱6︱7︱8︱9) (0︱1︱2︱3︱4︱5︱6︱7︱8︱9)*(0︱5)(0︱5)。
（3）包含奇数个1或奇数个0的二进制数串；
1*0（1︱01*0）*︱0*1（0︱10*1）*。
4解：
（1）、直接写出满足条件的正规表达式。考虑满足条件的字符串中的1：在串的开始部分可以有0个或多个1，串的尾部也可以有0个或多个1，但串的中间只要出现1则至少在两个以上，所以满足条件的正规表达式为1*(0∣111*)*1*。
所求的DFA如下图所示：
A
S
1
0a
1
1
B
0

5 解：
（1）、图（a）中为一个NFA，所以需要先对它进行确定化，得到DFA，然后再对DFA进行最小化。
首先进行确定化，如下两个表所示：

206

状态
a
b
{0}
{0，1}
{1}
{0，1}
{0，1}
{1}
{1}
{0}
Ø

状态
a
b
0
1
2
1
1
2
2
0

根据状态转换矩阵得到如下图所示的DFA：
2
1
0
b
b
a
a
a

化简后的DFA为：
2
0
b
a
a

（2）、题中所给即为一个DFA，不需要确定化，只对它进行最小化即可。
首先将状态划分为两个集合{{0，1}，{2，3，4，5}}。有{0，1}a={1}，{0，1}b={2，4}和{2，3，4，5}a={1，3，0，5}，{2，3，4，5}b={2，3，4，5}，所以可以进一步划分为{{0，1}，{2，4}，{3，5}}，然后有{0，1}a={1}，{0，1}b={2，4}，{2，4}a={1，0}，{2，4}b={3，5}，{3，5}a={3，5}，{3，5}b={2，4}。因此，最后划分结果是{{0，1}，{2，4}，{3，5}}。
最小化后的DFA如下图所示：
1
0
b
a
a
2
b
b
a

6解：第一步：写出正规表达式。根据题意，该DFA接受的字符串由0和1组成，并且每个1的后面都有0直接跟在右边，因此，可以将该字符串理解为由0和10构成的串，则相应的正规表达式就是(0︱10)*。
第二步：构造NFA。首先得出下图：
(0︱10)*
X
Y

然后对上图进行分解后得到如下图所示的NFA。
X
Y
ε
1
2
ε
0
1
0

第三步：确定化，得到DFA。确定化结果如表14.1所列；给状态编号，得到表14.2所示的状态转换矩阵：

状态
0
1
{X，1，Y}
{1，Y}
{2}
{1，Y}
{1，Y}
{2}
{2}
{1，Y}
Ø
表14.1 状态转换矩阵
状态
0
1
0
1
2
1
1
2
2
1

表14.2 新的状态转换矩阵

根据状态转换矩阵得到DFA如下图所示：
2
1
0
1
1
0
0
0

第四步：对该DFA进行最小化。其分析过程如下：
{0，1}，{2}
{0，1}0={1}，{0，1}1={2}
{0，1}，{2}
最小化后的DFA如图所示，该DFA即为所求。
1
0
1
0
0

对状态转换图进行确定化，得到状态转换矩阵：
状态
0
1
{S}
{S，B}
{S，A}
{S，B}
{S，B，C，Z}
{S，A}
{S，A}
{S，B}
{S，A，C，Z}
{S，B，C，Z}
{S，B，C，Z}
{S，A，C，Z}
{S，A，C，Z}
{S，B，C，Z}
{S，A，C，Z}
给状态编号，得到新的状态转换矩阵：
状态
0
1
0
1
2
1
3
2
2
1
4
3
3
4
4
3
4
根据状态转换矩阵获得DFA如下：
0
4
0
1
2
3
1
0
0
1
0
1
1
0
1

还可以对上图的DFA进行化简，状态3和4可以合并，化简后的DFA如下图所示：
0，1
S
T
0
1
B
A
0
1
0
1

不难看出，该DFA接受的语言是{0，1}上包含00或11的字符串。根据化简后的DFA，我们可以写出相应的左线性文法G’：
T→A0∣B1∣T0∣T1
A→B0∣0
B→A1∣1
编译原理F卷
1、考虑下面的文法G1：
S→a∣∧∣(T)
T→T，S∣S
（1）消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。
（2）经改写后的文法是否是LL(1)的？给出它的预测分析表。
（2）计算每个非终结符的FIRST集合和FOLLOW集合：
FIRST（S）={a，∧，( }
FIRST（T）={a，∧，( }
FIRST（T’）={，，ε}

FOLLOW（S）={ )，’，’，#}
FOLLOW（T）={ ) }
FOLLOW（T’）={ ) }
从而可见改造后的文法符合LL(1)文法的充分必要条件，所以是LL(1)的。
该文法的预测分析表

a
^
(
)
,
#
S
S->a
S->^
S->(T)

T
T->S T’
T->S T’
T->S T’

T’

T’->ξ
T->,S T’

2、对下面的文法G：
E→TE’
E’→+E∣ε
T→FT’
T’→T∣ε
F→PF’
F’→*F’∣ε
P→(E)∣a∣b∣∧
（1） 计算这个文法的每个非终结符的FIRST和FOLLOW。
（2） 证明这个文法是LL(1)的。
（3） 构造它的预测分析表。
（4） 构造它的递归下降分析程序。

3、下面文法中，哪些是LL(1)的，说明理由。
（1）、
S→Abc
A→a∣ε
B→b∣ε

（2）、
S→Ab
A→a∣B∣ε
B→b∣ε

（3）、
S→ABBA
A→a∣ε
B→b∣ε

（4）、
S→aSe∣B
B→bBe∣C
C→cCe∣d
4、对下面文法：
Expr→-Expr
Expr→(Expr)∣Var
ExprTail→-Expr∣ε
Var→id VarTail
VarTail→(Expr)∣ε
（1）、构造LL(1)分析表。
（2）、给出对句子id--id((id))的分析过程。
5、把下面文法改写为LL(1)的：
Declist→Declist；Decl∣Decl
Decl→IdList：Type
IdList→IdList，id∣id
Type→ScalarType∣array(ScalarTypeList) of Type
ScalarType→id∣Bound..Bound
Bound→Sign IntLiteral∣id
Sign→+∣-∣ε
ScalarTypeList→ScalarTypeList，ScalarType∣ScalarType
1、令文法G1为
E→E+T∣T
T→T*F∣F
F→(E)∣i
证明E+T*F是它的一个句型，指出这个句型的所有短语，直接短语和句柄。
2、考虑下面的表格结构文法G2：
S→a∣∧∣(T)
T→T，S∣S
（1） 给出(a，(a，a))和(((a，a)，∧，(a))，a)的最左和最右推导。
指出(((a，a)，^，(a))，a)的规范归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。
3、（1）计算练习2文法G2的FIRSTVT和LASTVT。
（2）计算G2的优先关系。G2是一个算符优先文法吗？
（3）给出输入串（a，（a，a））的算符优先分析过程。
4、考虑文法：
S→AS︱b
A→SA︱a
（1） 列出这个文法的所有LR(0)项目。
（2） 构造这个文法的LR(0)项目集规范族及识别活前缀的DFA。
（3） 这个文法是SLR的吗？若是，构造出它的SLR分析表。
（4） 这个文法是LALR或LR(1)的吗？

F卷答案
1答：解：
（1）按照T、S的顺序消除左递归，得到文法：

G’(S)
S→a∣∧∣(T)
T→ST’
T’→，ST’ ∣ε
对于非终结符S,T, T’的递归子程序如下：
Procedure S;
Begin
If sym = ‘a’ or sym = ‘^’
Then advance
Else if sym = ‘(‘
Then begin
Advance ;
T;
If sym = ’)’
Then advance
Else error
End
Else error
Ends;

Procedure T;
Begin
S; T’;
Ends;
Procedure T’
Begin
If sym = ‘,’
Then begin
Advance ;
S; T’
Ends
ends;
2解：
（1） 计算每个非终结符的FIRST集合和FOLLOW集合如下：
FIRST（E）={(，a，b，∧}
FIRST（E’）={+，ε}
FIRST（T）={(，a，b，∧}
FIRST（T’）={(，a，b，∧，ε}
FIRST（F）={(，a，b，∧}
FIRST（F’）={*，ε}
FIRST（P）={(，a，b，∧}

FOLLOW（E）={#，)}
FOLLOW（E’）={#，)}
FOLLOW（T）={+，)，#}
FOLLOW（T’）={+，)，#}
FOLLOW（F）={(，a，b，∧，+，)，#}
FOLLOW（F’）={(，a，b，∧，+，)，#}
FOLLOW（P）={*，(，a，b，∧，+，)，#}
（2） 本文法是LL ( 1 )文法。
证明： 通过观察可知文法中不含有左递归，满足LL (1)文法定义的第一个条件。
考虑下列产生式：
E’→+E∣ε
T’→T∣ε
F’→*F’∣ε
P→(E)∣a∣b∣∧
因为：
FIRST（+E）∩FIRST（ε）={+}∩{ε}=Ø
FIRST（E’）∩FOLLOW（E’）={+}∩{#，)}= Ø
FIRST（T）∩FIRST（ε）={(，a，b，∧}∩{ε}=Ø
FIRST（T’）∩FOLLOW（T’）={(，a，b，∧}∩{+，)，#}=Ø
FIRST（*F’）∩FIRST（ε）={*}∩{ε}=Ø
FIRST（F’）∩FOLLOW（F’）={*}∩{(，a，b，∧，+，)，#}= Ø
FIRST（（E））∩FIRST（a）∩FIRST（b）∩FIRST（∧）= Ø
所以该文法是LL(1)文法。
（3） 构造其预测分析表：

预测分析表

+
*
(
)
a
b
^
#
E

EàT E’

EàT E’
EàT E’
EàT E’

E’
E’à+E

E’ àξ

E’ ->ξ
T

T àFT’

T’àFT’
TàFT’
TàFT’

T’
T’àξ

T’ à T
T’àξ
T’àT
T’àT
T’ àT
T’àξ
F

F àPF’

FàPF’
PàPF’
FàPF’

F’
F’ à ξ
F’ à*F’
F’ à ξ
F’àξ
F’àξ
F’àξ
F’àξ
F’àξ
P

P à(E)

Pàa
Pàb
Pà ^

（4） 构造其递归下降分析程序：
Procedure E;
Begin
T ; E’
End ;

Procedure E’ ;
Begin
If sym = ‘ + ’
Then begin
Acvance ;
E
End
End ;

Procedure T ;
Begin
F ; T’
End ;

Procedure T’ ;
Begin
If sym ∈first ( T )
Then T
Else if sym = ‘*’ then error
End ;

Procedure F ;
Begin
If sym ∈first ( P )
P; F’;
End ;

Procedure F’
Begin
If sym = ‘ * ’
Then begin
Advance ;
F’
End
End;
Procedure P
Begin
If sym = ‘ a ’ or sym = ‘ b ‘ or sym = ‘ ^
Then acvance
Else if sym = ‘ ( ‘
Then begin
Advance ;
E ;
If sym = ‘ ) ‘
Then advance
Else error
End
Else error
End;
3 解：
（1） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集合如下：
FIRST（S）={a，b，c}
FIRST（A）={a，ε}
FIRST（B）={b，ε}
FOLLOW（S）={#}
FOLLOW（A）={b，c}
FOLLOW（B）={c}
可见该文法满足LL(1)文法的三个条件，是LL(1)文法。
（2） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集合如下：
FIRST（S）={a，b}
FIRST（A）={a，b，ε}
FIRST（B）={b，ε}
FOLLOW（S）={#}
FOLLOW（A）={b}
FOLLOW（B）={b}
考虑A→a∣B∣ε，因为FIRST（B）∩FOLLOW（A）={b}≠Ø，所以该文法不是LL(1)文法。
（3） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集合如下：
FIRST（S）={a，b，ε}
FIRST（A）={a，ε}
FIRST（B）={b，ε}
FOLLOW（S）={#}
FOLLOW（A）={a，b，#}
FOLLOW（B）={a，b，#}
考虑A→a∣ε和B→b∣ε，因为
FIRST（a）∩FOLLOW（A）={a}≠Ø
FIRST（b）∩FOLLOW（B）={b}≠Ø
所以该文法不是LL(1)文法。
（4） 该文法不含左递归，计算每个非终结符的FIRST集合和FOLLOW集合如下：
FIRST（S）={a，b，c，d}
FIRST（B）={b，c，d}
FIRST（C）={c，d}
FOLLOW（S）={e，#}
FOLLOW（B）={e，#}
FOLLOW（C）={e，#}
可见该文法满足LL(1)文法的三个条件，是LL(1)文法。
4 解：
（1）、计算每个非终结符的FIRST集合和FOLLOW集合如下：
FIRST(Expr)={-，(，id}
FIRST(ExprTail)={-，ε}
FIRST(Var)={id}
FIRST(VarTail)={(，ε}
FOLLOW(Expr)={)，#}
FOLLOW(ExprTail)={)，#}
FOLLOW(Var)={-，)，#}
FOLLOW(VarTail)={-，∣，#}
构造其预测分析表如下：

-
id
(
)
#
Expr
Expr→- Expr
Expr Expr
Expr→-( Expr)

ExprTail
ExprTail→-Expr

ExprTail→ε
ExprTail→ε
Var

Var→id VarTail

VarTail
VarTail→ε

VarTail→(Expr)
VarTail→ε
VarTail→ε
（2）、句子id--id((id))的分析过程如下：

步骤
符号栈
输入串
所用产生式
0
# Expr
id--id((id)) #

1
# ExprTail Var
id--id((id)) #
Expr→Var ExprTail
2
# ExprTail VarTail id
id--id((id)) #
Var→id VarTail
3
# ExprTail VarTail
--id((id)) #

4
# ExprTail
--id((id)) #
VarTail→ε
5
# Expr -
--id((id)) #
ExprTail→-E