如有过程，则过程占7分，否则该分加入最简DFA中，最简DFA对，则该过程满分，否则零分。
接受该语言的最简DFA是： start 1
b a a 2 b
(有初态1分， 2态3分，回朔3分，终态1分，共8分)
5. NFA：
(有初态1分，有末态2分，有中间态3分，共6分)
确定化:
i0{S} i1{A,C} i2{C} i3{C,Z} DFA M：
a {A,C} {C} / / b / {C,Z} {C,Z} {C,Z} 第 11 页 共 26 页
(内容一行1.5分，图１分，共7分
二、计算题2
6. 解：等价文法G[S]：
S→aA A→BcA’
A’→ASA’|ε B→iB’
B’→iB’|ε
（消除左递归２分）
First(S)={a} , FOLLOW(S)={#] FIRST(A)={i} , FOLLOW(A)={#，a}
First(A’)={i,ε}, FOLLOW(A’)= FOLLOW(A)={#，a] First(B)={i} , FOLLOW(B)= {c]
First(B’)={i,ε}, FOLLOW(B’)= FOLLOW(B)={c]
∵SELECT(A’→ASA’)∩SELECT(A’→ε)=Φ SELECT(B’→iB’)∩SELECT(B’→ε)=Φ ∴可知文法满足LL(1)文法的条件。
（有FIRST和FOLLOW ４分，有判断4分，结果正确1分,共9分）
分析表： a c S aA A A' ε B B' ε (一行1分，共6分)
i # BcA’ ASA’ iB’ iB’ ε 第 12 页 共 26 页
7. (1)消除左递归，提公因子
E→aTb|iE’
E’→E|ε T→ET’
T’→ET’|ε
（消除左递归2分，提公共因子2分）
(2)求FIRST和FOLLOW
FIRST(E)＝{a，i} FOLLOW(E)＝{#，a，b，i } FIRST(E’)＝{a，i,ε} FOLLOW(E’)＝{#，a，b，i } FIRST(T)＝{a，i} FOLLOW(T)＝{b} FIRST(T’)＝{a，i，ε} FOLLOW(T’)＝{b} （一条1分，共8分）
(3) ∵FIRST(E)∩ FOLLOW(E’)= {a，b，i}； ∴不是LL（1）文法
（有FIRST(E)∩ FOLLOW(E’)4分，结果正确1分，共5分） 1、 8. 消除左递归（２分）
E → T E’ E’→ or T E’|ε T → F T’ T’→ and F T’|ε
F → not F | (E) | true | false
构造First和Follow集合
First(E)={not,(,true,false) Follow(E)={（）,#} First(E’)={or,ε} Follow(E’)={（）,#} First(T)={not,(,true,false) Follow(T)={or,（）,#} First(T’)={and,ε} Follow(T’)={or,（）,#} First(F)={not,(,true,false) Follow(F)={or,and,（）,#} （一条１分，共１0分）
第 13 页 共 26 页
∵SELECT(E’→ or T E’)∩SELECT(E’→ε)=Φ； SELECT(T’→ and F T’)∩SELECT(T’→ε)=Φ； F 的SELECT()两两相交为Φ； ∴可知文法满足LL(1)文法的条件。
（有判断4分，结果正确1分,共5分）
9. 提公因子（2分）和消除左递归（2分）
D→TL T→int | real L→id L’ L’→,id L’|ε
构造First和Follow集合
First(D)={int，real} Follow(D)={#} First(T)={int，real} Follow(T)={id} First(L)={id} Follow(L)={#} First(L’)={‘，’,ε} Follow(L’)={#} （一条1分，共8分）
∵S{ T→int } ∪ S{ T→real }=Φ； S{ L’→,id L’} ∪ S{ T→ε}=Φ； ∴该文法是LL(1)文法
（有FIRST(E)∩ FOLLOW(E’)4分，结果正确1分,共5分）
10. 改造后的文法G[S]：
S → PS'
S' → aPS'| fS' |ε P → qP' P' → bP |ε
（消除左递归2分，提公共因子2分）
第 14 页 共 26 页
求FIRST和FOLLOW
FIRST(S)＝{q} FOLLOW(S)＝{#} FIRST(S’)＝{a ,f,ε} FOLLOW(S’)＝{#} FIRST(P)＝{q} FOLLOW(P)＝{a,f,#} FIRST(P’)＝{b，ε} FOLLOW(P’)＝{a,f,#}
（一条1分，共8分） LL(1) 分析表为
S S' P P' a aPS' ε b bP f fS' ε q PS' qP' # ε ε
(一行1分，共5分)
三、问答与作图题
11. 最左推导：S=>D=>H=>(S)=>(S+D)=>(D+D)=>(D,H+D)=>(D,H+H)=>(D,H+a) (一步0.25分,共2分)
最右推导：S=>D=>H=>(S)=>(S+D)=>(S+H)=>(S+a)=>(D+a)=>(D,H+a) (一步0.25分,共2分)
语法树： S S
S D * + D S
S + D S * D
D D
(一树２分，共４分)
短语：“(D,H＋a)”，“D,H＋a”，“D,H”，“a” (2分) 素短语：“D,H”，“a ” (2分)
第 15 页 共 26 页