图2-8-2 语法树
（2）句子acabcbbdcc的最左推导如下：
S?aAcB?aAaBcB?acaBcB?acabcB?acabcbScA?acabcbBdcA ?acabcbbdcA?acabcbbdcc 5、对于文法G[S]：
S→（L）|aS|a L→L, S|S （1）画出句型（S,（a））的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。 【解答】 S （1）句型（S,（a））的语法树如图2-8-3所示 （ L ）
L ， S
S ( L ) S （2）由图2-8-3可知：
①短语：S、a、(a)、S,(a)、(S,(a))； a ②直接短语：a、S； 图2-8-3 句型（S,（a））的语法树 ③句柄：S；
④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；
# ·（·， ·（ ·a· ）· ）· # 因此素短语为a。
6、考虑文法G[T]： T→T*F|F F→F↑P|P P→（T）|i
证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。 T 【解答】 T * F 首先构造T*P↑（T*F）的语法树如图2-8-4所示。 F ↑ P 由图2-8-4可知，T*P↑（T*F）是文法G[T]的一个句型。 P （ T ） 直接短语有两个，即P和T*F；句柄为P。
T * F 图2-8-4 句型T*P↑（T*F）的语法树
一、单项选择题
1、词法分析所依据的是 。
a. 语义规则 b. 构词规则 c. 语法规则 d. 等价变换规则 2、词法分析器的输出结果是 。
a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 3、正规式M1和M2等价是指 。
a. M1和M2的状态数相等 b. M1和M2的有向弧条数相等
c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等 4、状态转换图（见图3-6-1）接受的字集为 。
0
X 1 Y 0
图3-6-1
a. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。 a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好
c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段 解答 1、b 2、c 3、c 4、d 5、b 二、多项选择题
1、在词法分析中，能识别出 。 a. 基本字 b. 四元式 c. 运算符 d. 逆波兰式 e. 常数
2、令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。 a. b(ab)* b. b(ab)+ c.(ba)*b
+
d. (ba)b e. b(a|b) 解答 1、a、c、e 2、a、b、d 三、填空题
1、确定有限自动机DFA是 的一个特例。
2、若二个正规式所表示的 相同，则认为二者是等价的。 3、一个字集是正规的，当且仅当它可由 所 。 解答 1、NFA 2、正规集 3、DFA（NFA）所识别 四、判断题
1、一个有限状态自动机中，有且仅有一个唯一终态。 （ ） 2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。 （ ） 3、自动机M和M′的状态数不同，则二者必不等价。 （ ） 4、确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ） 5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 （ ） 6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。 （ ） 7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。 （ ） 8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。 （ ） 解答 1 、2、3、错 4、5、6、7、8、正确 五、基本题
1、设M＝（{x,y}, {a,b}, f,x,{y}）为一非确定的有限自动机，其中f定义如下：
f（x,a）＝{x,y} f（x,b）＝{y} f（y,a）＝φ f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。
解答：对照自动机的定义M=(S,Σ,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。
a a
b
X b Y
b
图3-6-2 NFA M
用子集法构造状态转换矩阵表3-6-3所示。 I {x} {y} Ia {x,y} — Ib {y} {x,y}
{x,y} {x,y} {x,y} 将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。 表3-6-4 状态转换矩阵 0 1 2 a 2 — 2 b 1 2 2 即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其状态转换图如图3-6-5所示。
a
a,b
0 2 b b 1 图3-6-5 DFA M′ 将图3-6-5的DFA M′最小化。首先，将M′的状态分成终态组{1，2}与非终态组{0}；其次，考察{1,2}。由于{1,2}a={1,2}b={2}?{1,2}，所以不再将其划分了，也即整个划分只有两组{0}，{1,2}：令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图3-6-6所示化简DFA M′。
a
a,b 1 0
b
图3-6-6 化简后的DFA M′
2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M；
解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7所示。
b*(d|ad)(b|ab)(b|ab)* X Y b* 1 (d|ad) 2 (b|ab) 3 (b|ab)* Y X
b X ε 4 ε b X ε 4 ε 1 a 1 ad d 2 a 6 d d 2 ab b b b|ab 3 ε 5 ε b 3 ε 5 a 7 b 8 ε b Y Y 图3-6-7 的NFA M
1、 构造下面文法的LL（1）分析表。
D→ TL
T→ int | real L→ id R R→ , id R | ε
解答： LL（1）分析表见表4-3-1
分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。
FIRST（D）=FIRST（T）={int, real} FOLLOW（D）=FOLLOW（L）={#}
FIRST（L）={id} FOLLOW（T）={id} FIRST（R）={，, ε} FOLLOW（R）={#}
有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部α的FIRST（α）就不是件难事了。
填表时唯一要小心的时，ε是产生式R→ε右部的一个开始符号，而#在FOLLOW（R）中，所以R→ε填在输入符号#的栏目中。
表4-3-1 LL（1）分析表 非终结符 D T L R int D→TL T→int 输入符号 real D→TL T→real id L→id R ， R→,id R # R→ ε
2、 下面文法G[S]是否为LL（1）文法？说明理由。
S → A B | P Q x A → x y B → b c P → d P | ε Q → a Q | ε
解答： 该文法不是LL（1）文法，见下面分析中的说明。 分析 只有三个非终结符有两个选择。
1、P的两个右部d P 和ε 的开始符号肯定不相交。
2、Q的两个右部a Q 和 ε 的开始符号肯定不相交。
3、对S来说，由于x ∈ FIRST(A B)，同时也有x ∈ FIRST(P Q x)（因为P和Q都可能为空）。所以该文法不是LL（1）文法。 3、 设有以下文法：
G[S]：S→aAbDe|d A→BSD|e B→SAc| cD| ε D→Se| ε
（1）求出该文法的每一个非终结符U的FOLLOW集。 （2）该文法是LL（1）文法吗？ （3）构造C[S]的LL（1）分析表。
解答： （1）求文法的每一个非终结符U的FOLLOW集的过程如下： 因为：
① S是识别符号，且有A→BSD、B→SAc、D→Se，所以FOLLOW（S）应包含
FIRST(D)∪FIRST(Ac) ∪FIRST(e) ∪{#} ={a,d}∪{a,d,c,e}∪{e}∪{#} ={a,c,d,e#}
② 又因为A→BSD和D→ε，所以FOLLOW中还包含FOLLOW(A)。 因为S→aAbDe和B→SAc,所以
FOLLOW（A）=FIRST（bDe）∪FIRST（c）={b,c}
综合①、②得FOLLOW（S）={a,d,c,e,#}∪{a,b,c,d,e,#}
因为A→BSD，所以 FOLLOW（B）=FIRST（SD）={a,d} 因为S→aAbDe | d、A→BSD| e和B→SAc | cD，所以 FOLLOW（D）=FIRST（e）∪FOLLOW（A）∪FOLLOW（B） ={e}∪{b,c}∪{a,d}={a,b,c,d,e} （2）G[S]不是LL（1）文法。 因为产生式B→SAc|cD| ε 中
FIRST（SAc）∩FOLLOW（B）={a,d}≠? （3）构造G[S]的LL（1）分析表。
按照LL（1）分析表的构造算法构造方法G[S]的LL（1）分析表如表4-3-2所示。
表4-3-2 G[S]的LL（1）分析表 S A B D a aAbDe BSD Sac/ε Se/ε b ε c BSD cD ε d d BSD Sac/ε Se/ε e e ε # 4、 将文法G[V]改造成为LL(1)的。 G[V]：V→N|N[E] E→V|V+E N→i
解答： 对文法G[V]提取公共左因子后得到文法： G′[V]：V→NA
A→ε|[E] E→VB B→ε|+E N→i
求出文法G′[V]中每一个非终结符号的FIRST集： FIRST(V)={i} FIRST(A)={[, ε} FIRST(E)={i} FIRST(B)={+, ε} FIRST(N)={i}
求出文法G′[V]中每一个非终结符号的FOLLOW集： FOLLOW(V)={#}∪FIRST(B)\\{ε}∪FOLLOW(E)={#,+,]} FOLLOW(A)= FOLLOW(V)={+,,#} FOLLOW(E)= FIRST(])\\{ε}∪FOLLOW(B)= FIRST(])\\{ε}∪FOLLOW(E)={]} FOLLOW(B)= FOLLOW(E)={ ]} FOLLOW(N)= FIRST(A)\\{ε}∪FOLLOW(V)={[,],+,#} 可以看到，对文法G′[V]的产生式A→ε|[E]，有 FIRST([E])∩FOLLOW(A)={[}∩{+,],#}= ? 对产生式B→ε|+E，有