編譯原理(第二版)張素琴清華大學(xué)-答案詳解

....................................最右推導(dǎo)1〈表達式〉〈表達式〉運算符〉達式〉〈表達式〉運算符〉達式〉*aa+a*a最右推導(dǎo)2〈表達式〉〈表達式〉運算符〉達式〉〈表達式〉運算符〉達式〉〈表達式〉運算符〉達式〉〈表達式〉運算符〉達式〉*aa+a*a..............<2>產(chǎn)生式有：S..可能元素有：abbaaaaabbaa....................G[S]:S也可為<觀察得來>:G[S]:S<1>i;<2>i*i+i<3>i+i*i<4>i+<i+i>................xx=aaaaaa|xx|=6x5=aaaaaaaaaaaaaaa|x5|=15A*=A0xy=abcb|xy|=4xyz=abcbaab|xyz|=7......VT={+,-,*,/,〔,,i}..................................................................................{1,2,3,4,5}a{0,1,3,5}∵{4}a{0},所以得到新分劃∵{1,5}b{4}{2,3}b{1,2,3,5},故得到新分劃{1,5}a{1,5}....|10<s||dd*.dd*10<s|化簡.........??....??....................a,b................r=b*a<c|da>*bb*=b*a<c|da>*b+..a>每個1至少有一個0跟在后邊的串..............由A由A得S得S由S由S由S....................0>A1>A2>B3>B4>B0>A1>A2>B3>B4>N5>N....................C..文法G[E]是LL<1>文法:....switch<lookahead>{switch<lookahead>{....文法G[E]是LL<1>文法:..................歸約,Sa歸約,LS歸約,Sa歸約,TS..歸約,Sa歸約,TT,S歸約,S<T>歸約,TT,S歸約,S<T>....歸約,Sa歸約,TS歸約,Sa歸約,TT,S歸約,S<T>....VT|ViTTF|T+FF>V*|<....SGHT....;<>;<=·>=·..<>>>....對于文法S<L>|aLL,S|S<1>S=><L>=><L,S>=><L,<L>>=><L,<L,S>>=><L,<L,<L>>>=><L,<L,<L,S>>>=><L,<L,<L,..歸約,Sa歸約,LS歸約,Sa歸約,LS..歸約,Sa歸約,LL,S歸約,S<L>歸約,LS歸約,Sa歸約,LS歸約,Sa歸約,LL,S歸約,S<L>歸約,LL,S歸約,S<L>歸約,LL,S歸約,S<L>......AAA2A3AFirst<S'>={First<A>={Follow<S'>={#}Follow<A>={d,b,#}Follow<A>..題目1的SLR<1>分析表狀態(tài)?！瞫tatestack文法符號?！瞚nputleftab#....Shiftb#....Reduceby:Ab#....Shift#....Reduceby:A#......SLBSLB1S2S3L4L5B6BFirst<S'>={0,1}First<S>={0,1}First<L>={0,1}First<B>={0,1}Follow<S'>={#}Follow<S>={#}Follow<L>={.,0,1,#}Follow<B>={.,0,1,#}..Follow<s>題目2的SLR<1>分析表?.......〔inputleft101.110#....Shiftby:Bby:S01.110#....Shiftby:Bby:S1.110#....Shiftby:Bby:S.110#....Shift110#....Shiftby:Bby:S10#....Shiftby:Bby:S0#....Shiftby:Bby:S#............actionS4/r3S4/r1S3/r1..歸約Sb歸約Aa歸約SbI0:S'·S,#S·AS,#S·b,#S·SA,a/bA·a,a/b:S'S·,#S·A,a/b?a,a/b?SA,a/b?AS,a/b?b,a/bI2:SA·S,#S·b,#S·AS,#A·SA,a/b..I3:SI4:AI5:A?a,a/bb·,#a·,a/bSA·,a/bA·S,a/b?AS,a/b..S·b,a/bA·SA,a/bA·a,a/bS·A,a/b?SA,a/b?a,a/b?AS,a/b?b,a/b..I7:SI8:Sb·,a/bAS·,#S·A,a/b?SA,a/b?a,a/b?AS,a/b?b,a/b..:A·S,#?AS,#?b,#?SA,a/b?a,a/b:AS·,a/bS·A,a/b?SA,a/b?a,a/b?b,a/b?AS,a/b..I11:..A·S,a/b?b,a/b..?AS,a/b?SA,a/b?a,a/b:SA·,a/bA·S,a/b?b,a/b?AS,a/b?SA,a/b?a,a/b..〔1列出這個文法的所有LR<0>項目0S'....I0:S'·S,#S·AS,#S·b,#S·SA,a/bA·a,a/b:S'S·,#S·A,a/b?a,a/b?SA,a/b?AS,a/b?b,a/b..I2:SI3:SI4:AI5:AA·S,#?b,#?AS,#?SA,a/b?a,a/bb·,#a·,a/bSA·,a/bA·S,a/b?AS,a/b..S·b,a/bA·SA,a/bA·a,a/bS·A,a/b?SA,a/b?a,a/b?AS,a/b?b,a/b..I7:SI8:Sb·,a/bAS·,#S·A,a/b?SA,a/b?a,a/b?AS,a/b?b,a/b..:A·S,#?AS,#?b,#?SA,a/b?a,a/b:AS·,a/bS·A,a/b?SA,a/b....?a,a/b?b,a/b..?AS,a/b:A·S,a/b?b,a/b?AS,a/b?SA,a/b?a,a/b:SA·,a/bA·S,a/b?b,a/b?AS,a/b?SA,a/b?a,a/b....文法G=<{U,T,S},{a,b,c,d,e},P,S>TU<1>判斷G是LR<0>,SLR<1>,LALR<1>還是LR<1>,說明理由。TU1S2S3T4T5T6U7UFirst<S'>={d,e}First<S>={d,e}First<U>={e}First<T>={d,e}Follow<S'>={#}Follow<S>={a,b,c,d,e,#}Follow<U>={d,e}Follow<T>={a,b}..S'Follow<S'>Follow<T>Follow<U>Follow集解決,所以G是SLR<1>文法。..〔State是LR<1>但不是SLR<1>。<其中'$'相當于'#'>..0S'1A2A3B4DFirst<S'>={a,b}....First<A>={a,b}First<B>={First<D>={Follow<S'>={#}Follow<A>={#}Follow<B>={a,b}Follow<D>={a,b}..Follow<B>不是SLR<1>文法。r4.......S4..............r4............S9..............S<2>該文法是LR<0>嗎?是SLR<1>嗎?說明理由。a>or優(yōu)先性大于do;c>;優(yōu)先性大于do；d>;優(yōu)先性大于or；首先化簡文法,用d代替do;用o代替or;用a代替act;文法可寫成：S1S2S3S4SFirst<S'>={d,a}First<S>={d,a}Follow<S'>={#}Follow<S>={o,;,#}....<2>該文法不是LR<0>也不是SLR<1>因為：又由于Follow<S>={o,;,#}Follow<S>Follow<S>S`S`a>or優(yōu)先性大于do;d>;優(yōu)先性大于or；....〔State;..試判別如下文法是否LR<0>或SLR<1>文法:a>文法G[E]:Tb>文法G[S]:A..Follow<T>={+,},},#},不含[,所以G[E]是SLR<1>文法?？疾炷芊袷褂肧LR<1>方法解決沖突：I4中,因為Follow<S>={#}而Follow<B>={c}.所以可以解決。I3中,因Follow<A>=,不含a,因此該移進/歸約沖突也可解決.文法是SLR<1>文法<0>S'<1>S<2>X<3>X..<0>P'<1>P<2>P<3>P<4>A..I0:I1:I9:P..PP,</#,</#,</#P<I3:I6:..I2:PPP,,,</#</></>P,</>..PI4:PI5:,,

</><I8:PPP,,,,</></></></>..I7:>PPI11:<I10:,..PP>PP..〔2可以看出：I2和I6,I3和I8,I4和I9,I5和I10,I7和I11是同芯狀態(tài).通過....I0:I1:..PP,</#,</#,</#P<I3-8:..I2-6:PPP,,,</>/#</></>..P,</>,<I4-9:I5-10:I7-11:..PPP>P..BA|aB|b<0>S'S<1>S<2>A<3>A<5>BFIRST<A>={..FIRST<B>={a,b}I0:[S'?S,#][S?A,#]I1:[S'S?,#]I2:[SA?,#]..[A?BA,#][A?,#][B?aB,a|b|#][B?b,a|b|#]I3:B?A,#]?BA,#]?,#]?aB,a|b|#]?b,a|b|#]I6:[ABA?,#]..I5:I4:I7:[BaB?,a|b|#]..[Bb?,a|b|#][Ba?B,a|b|#][B?aB,a|b|#][B?b,a|b|#]....歸約Bb歸約BaB歸約Bb歸約BaB歸約A歸約SAS'SL..SSLL{print<S.num>}....S{S.num:=L.num+1;}{S.num:=0;}L{L.num:=L1.num+S.num;}{L.num:=S.num;}..<a,<a>>的分析和計值過程〔語義棧中的值對應(yīng)S.num或L.num..--1--2..{N.val:=S1.val+2}....{S.val:=2*S.val+B.val;S.len:=S.len+1}{S.val=B.val;S.len:=1}{B.val:=0}..{B.val:=1}..{N.val:=S1.val+2..SRR.slen:=R1.slen}R{B.val:=0}{B.val:=1}realParseN<>{<S1val,S1len>:=ParseS<>;//變量S1val,S1len分別對應(yīng)屬性S1.val,MatchToken<'?'>;<S2val,S2len>:=ParseS<>;//變量S2val,S2len分別對應(yīng)屬性S2.val,Nval:=S1val+2^<-S2len>*S2val;/變量Nval對應(yīng)屬性N.valreturnNval;}<int,int>ParseS<>//〔int,int代表一個記錄/結(jié)構(gòu)類型{..Bval:=ParseB<>;Rival:=Bval;Rilen:=1;<Rsval,Rslen>:=ParseR<Rival,Rilen>;Sval:=Rsval;Slen:=Rslen;return<Sval,Slen>;}<int,int>ParseR<intRival,intRilen>{..switch<lookahead>{Bval:=ParseB<>;R1ival:=2*Rival+Bval;R1ilen:=Rilen+1；..<R1sval,R1slen>:=ParseR<R1ival,R1ilen>;Rsval:=R1sval;Rslen:=R1slen;Rsval:=Rival;Rslen:=Rilen;default:printf<"syntaxerror\n">exit<0>;}return<Rsval,Rslen>;}..intParseB<>{switch<lookahead>{MatchToken<'0'>;Bval:=0;MatchToken<'1'>;Bval:=1;default:printf<"syntaxerror\n">exit<0>;....}returnBval;}量分別用v[i].val和v[i].len表示。..{N.val:=S1.val+2..SRR.slen:=R1.slen}R..{B.val:=0}{B.val:=1}{N.val:=S1.val+2..SR.sval;S.len:=R.slen}RR1.ilen:=P.slen}R1{R.sval:=R1.sval;R.slen:=R1.slen}R{B.val:=0}{B.val:=1}MPNSR{v[top+1].val:=v[top].val;v[top+1].len:=v[top].len}..v[top-1].len+1}{v[top].val:=0}{v[top].val:=1}{v[top+1].val:=v[top].val;v[top+1].len:=1}{v[top+1].val:=2*v[top-1].val+v[top].val;v[top+1].len:=....歸納：..........100<+,a,b>101<+,c,d>102<*,<1>,<2>>....100<+,a,b>101<+,c,d>102<*,<1>,<2>>103<-,<3>,/>104<+,<1>,c>105<-,<4>,<1>>....101<+,c,d>102<*,<1>,<2>>103<-,<3>,/>104<+,<1>,c>105<-,<4>,<1>>間接碼表：100101103100104..................................................SL.L|LLLB|BB0|1S`S..SL1.L2LL1B........EE+T|TTnum.num|num..EE1+TTnum.numTnum....EE1+TTnum.numTnum....DiLL,iL|:TTinteger|real..DiLL,iL1L:TTintegerTreal....〔100ifA<Bgoto〔102〔101goto〔107〔102ifC<Dgot〔104〔103goto〔100〔104T∶=Y+Z〔105X∶=T〔106goto〔100........................L1,{S.f:=L.f}..DL,id|LLTidTint|real..DL,idLTidTintTreal....Tnum.num|num..Tnum.