编译原理A答案.docVIP

淮 阴 师 范 学 院 2011级计算机科学与技术专业《编译原理》课程考试A卷 2013-2014学年第1学期 参考答案及评分标准 Solution : Regular expression is a(a|b)*ab …………………………………………(5’) Re→NFA …………………………………………(7’) NFA →DFA State Σ a b I0={S} {A,B }=I1 I1 { A ,B，C}= I2 I1 I2 I2 {A,B,Z}=I3 I3 I2 I1 …………………………………………(11’) DFA →minDFA First ,we divide states into K1={I0,I1,I2},K2=I3. For K1, input a: f(I0,a)= I1, f(I1,a)= I2, f(I2,a)= I2, so K1 can be divided into K11={ I0},k12={ I1,I2}; For K12, input b: f(I1,b)= I1, f(I2,b)= I3, so K12 can be divided into{ I1},{I2} ,we can obtain the minDFA : …………………………………………(15’) minDFA →RG I0→aI1 I1→aI2|b I1 I2→aI2|b I3|b I3→aI2|b I1 ………………………………………(20’) Solution: 1）Elimination of Left Recursion： (0) E (TE’ (1) E’(+TE’ |ε (2) T ( FT’ (3) T’ (* FT’| ε (4) F( (E)|i …………………………………………(4’) 2) First and Follow of every Nonterminal: First(E)= First(T)=First(F)={(,i}, First(E’)={+, ε}, First(T’)={*, ε}; ………(8’) Follow(E)=Follow(E’)={},#}, Follow(T)=Follow(T’)={+,},#} Follow(F)={*,+,},#} ………………………………… (12’) 3) Construct the predictive parsing table: Stack Σ + * ( ) i # E E(TE’ E(TE’ E’ E’(+TE’ E’ (ε E’ (ε T T(FT’ T(FT’ T’ T’ (ε T’(*FT’ T’ (ε T’ (ε F F((E) F(i All spaces are filled in Error. ………………(16’) Parse the input string i+i*i#: step stack Input string action 1 #E i+i*i# E(TE’ 2 #E’T i+i*i# T(FT’ 3 #E’T’F i+i*i# F(i 4 #E’T’F i+i*i# Match 5 #E’T’F +i*i# T’ (ε 6 #E’T’F +i*i# E’(+TE’ 7 #E’T’F +i*i# match 8 #E’T’F i*i# T(FT’ 9 #E’T’F i*i# F(i 10 #E’T’F i*i# match 11 #E’T’F *i# T’(*FT’ 12 #E’T’F *i# match 13 #E’T’F i# F(i 14 #E’T’F i# match 15 #E’T’F # T’ (ε 16 #E’ # E’ (ε 17 # # success Solution: Extend the grammar, increase production S’→#A# ………………(2’) Calculate Firstvt and Lastvt of each nonterminal: Firstvt(A)={ ∨, ∧, ┐,(, i}, Firstvt(B)={ ∧, ┐,(, i }, Firstvt(C)={ ┐,(, i }, Firstvt(D)={ (, i };