编译原理与技术 - 习题集（含答案）(3)

如有过程，则过程占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 页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理与技术 - 习题集（含答案）(3)在线全文阅读。