内容发布更新时间 : 2024/11/20 15:15:54星期一 下面是文章的全部内容请认真阅读。
3 4 5 6 7 8 9
038 02 026 0267 0269 025 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所示。
第11页共6页
步骤 符号栈 输入串 所用的产生式 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第12页共6页
I1: S′?S· SaAbI2: S?a· S?a·Ab A?·1A0 ? A?·I4: S?aA·b AI8: S?aAb· I9: A?1A·0 01I5: A?1·A0 A?·1A0 ? A?·1I12: A?1A0· I0: S′?·S S?·a S?·aAb S?·b S?·bBa BbI3: S?b· S?b·Ba B?·1B0 ? B?·I6: S?bB·a aBI10: S?bBa· I11: B?1B·0 011I7: B?1·B0 B?·1B0 ? B?·I13: B?1B0· 项目集族和DFA
1、w a b + c d e 10 - / + 8 + * + 2、abcd-*e/+ 3、abc+e*bc+f/+:= 4、4231
5、句子b(aa)b的规范归约过程： 步骤 0 1 2 3 4 5 6 7 8 9 10 6、消除左递归 S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF | +a
# #b #b( #b(a #b(A #b(Ma #b(Ma) #b(B #bA #bAb #S 符号栈 输入串 b(aa)b# (aa)b# aa)b# a)b# a)b# )b# b# b# b# # # 预备 移进 移进 移进 归约 移进 移进 归约 归约 移进 接受 动作 第13页共6页