精品文档
构造LR(1)分析表 如下：
状态 action a b c d e # goto S A 0 S2 S3 1 1 ac
S5 2 S7 3
S8 4
S9 r5 5 二、设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识S10 6 别该正规集的DFA。(8分) r5 S11 答： 7 构造相应的正规式： (3分) r1 8 (0|1)*1(0|1) NFA: (2分) r3 9 1 1 r2 10
? ? r4 11 ? ? 1 0 1 2 3 4
0 0 确定化：(3分) I {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4} I0 {1,2} {1,2} {1,2,4} {1,2} {1,2,4} I1 {1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4}
0
1 0 1 0 0 0 1 2 3
0 1 精品文档 4 精品文档
1 1 四、对于文法G(E): (8分)
E?T|E+T T?F|T*F F?(E)|i
1. 写出句型(T*F+i)的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语、句柄和素短语。 答： 1. (4分)
E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i)
2. (4分)
短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i 句柄：T*F 素短语：T*F, i
九、(9分) 设已构造出文法G(S)：
(1) S ? BB (2) B ? aB
(3) B? b的LR分析表如下 状态 0 1 2 3 4 5 6 7 8 9 a s3 s6 s3 r3 s6 r2 ACTION b s4 s7 s4 r3 s7 r2 # acc r1 r3 r2 S 1 GOTO B 2 5 8 9 T * F i E T F ( E ) E + T T F
假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。 答： 步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 精品文档
精品文档 3 038 4 02 5 026 6 0267 7 0269 8 025 9 01
#aB #B #Ba #Bab #BaB #BB # #S
ab# ab# b# # # #
acc
1. 设有如下文法G（S），试消除其左递归。
G（S）：S—>Ac|c A—>Bb|b B—>Sa|a
解：S→abcS′|bcS′|cS′, S′→abcS′|?
2. 试构造与下面G（S）等价的无左递归的文法。
G（S）：S—>Sa|Nb|c N—>Sd|Ne|f
解：S→fN′bS′|cS′, S′→aS′|dN′bS′|?, N′→eN′|? 3. 设有文法G（S）：
S—>aBc|bAB A—>aAb|b B—>b|ε
①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。 ②构造LL(1)分析表，并分析符号串baabbb是否是。
解：（1）FIRST(aBc)={a}, FIRST(bAB)={b} FIRST(aAb)={a}, A→b: FIRST(A→b)={b}, B→b: FIRST(b) = {b}, FIRST(ε)={ε}
FOLLOW(A)={b, #}, FOOLOW(B)={c, #}
SELECT(S→aBc)={a}, SELECT(S→bAB) ={b}, SELECT(A→aAb)={a}, SELECT(A→b)={b}, SELECT(B→b)={b}, SELECT(B→?)={c, #}
因此，所得的LL(1)分析表如表A-4所示。
表A-4 LL(1)分析表 输输入符号 入 a b c # VN S S→aBc S→bAB A A→aAb A→b B B→b B→? B→?
（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。
精品文档
精品文档
步骤 符号栈 输入串 所用的产生式 1 #S baabbb# S?bAB 2 #BAb baabbb# 3 #BA aabbb# A?aAb 4 5 6 7 #BbAa #BbA #BbbAa #BbbA aabbb# abbb# A?aAb abbb# bbb# A?b bbb# bb# b# # # B?ε 成功 8 #Bbbb 9 #Bbb 10 #Bb 11 #B 12 #
图A-16 识别串baabbb的过程
4. 已知文法G(S)：
S—>a|(T) T—>T,S|S
①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。 解：（1）最左推导：S?(T)?(T,S)?(S,S) ?(a,S)?(a,(T))?(a,(T,S))?(a,(S,S))?(a,(a, S))?(a,(a,a)) 语法树：如图A-16所示。
S( T )T , SSa( T )T , SSaa 图A-16 (a,(a,a))的语法树
（2）句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。 短语：a || T,a || (T) || T , a , (T) || (T , a , (T)) 直接短语：a || (T) 素短语：a || (T) 最左素短语：a 句柄：a
活前缀：? || ( || (T || (T , || (T , a
S( T )T , ST , S( T )
图A-17 (T,a,(T))的语法树
a精品文档