【正文】 要求（希望） 1. 牢固掌握基本概念 2. 靈活使用基本方法 3. 歸納總結(jié)所學內(nèi)容（鍛煉提高抽象能力） 一、引言 二、詞法分析 三、語法分析 四、語義分析 —語法制導翻譯生成中間代碼 學習不能走捷徑，付出多少勞動就有多少收獲。語法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語言的各種結(jié)構(gòu)，即 語法規(guī)則 ；根據(jù)語法規(guī)則識別輸入序列（記號流）中的語言結(jié)構(gòu)，即 語法分析 。 與前兩章詞法分析和語法分析不同的是 ， 詞法分析和語法分析的討論側(cè)重于理論 ， 而本章則側(cè)重于結(jié)合程序設計語言的實際例子討論語言結(jié)構(gòu)的具體翻譯方法和一些實用的技術(shù) 。 ? 總之一句話，學習方法的掌握是個人努力的結(jié)果，單純靠別人教是學不會的。 2（ 1分 ） 正規(guī)式 r和 s等價說明 相同 。 0 1 2b ba,ba,b 解： 1. 含有至少兩個連續(xù) b的 a、 b串 ， 例如 bb、 bbb等 。 } F→(E) { =。 反之亦然 。 program main(input output)。 兩種解題的思路： 1. 把自己當作計算機 ， 按照參數(shù)傳遞的實現(xiàn)方式 “ 運行 ” 一遍程序 ， 得出結(jié)果； 2. 找臺機子把程序敲進去試試 （ 輔助手段 ） 困惑的是： 表達式 a+b如何作為引用調(diào)用和復寫 恢復的實參 ？ 解決方案： 忽略返回值問題 。 如果基于的假設是 LR(0)項目集中沒有沖突 ， 則構(gòu)造方法 可以簡化 （ 無需計算 FOLLOW集合 ） ， 得到的是 LR(0)分析表 ?！? S. then action[i, ]:=acc。 解： （ 1） n=1時 ， addr(A[i1])=a+(i11)*4 n=2時 ， addr(A[i1,i2])=a+(i21)*d1*4+(i11)*4 addr(A[i1,i2,…,in])=??? n維數(shù)組元素的地址計算 addr(A[i1， i2， ...， in]) =a+((in1)*dn1*dn2*...*d1+(in11)*dn2*dn3*...*d1+...+ (i11))*w =a(dn1*dn2*...*d1+dn2*dn3*...*d1+...+d1+1)*w +(in*dn1*dn2*...*d1+in1*dn2*dn3*...*d1+...+i2*d1+i1)*w =a–c*w+v*w 其中： c=dn1*dn2*dn3… *d1+dn2*dn3*dn4… *d1+*dn3*dn4*dn5… *d1… +d1+1 =(dn1+1)*dn2*...*d1+dn3*dn4...*d1+...+d1+1 =((dn1+1)*dn2+1)*dn3*dn4...*d1+...+d1+1 ...... =(...((dn1+1)*dn2+1)*dn3...+1)*d1+1 同理： v = (...((in*dn1+in1)*dn2+in2)*dn3...+i2)*d1+i1 n維數(shù)組元素的地址計算（續(xù) 1） c=(...((dn1+1)*dn2+1)*dn3...+1)*d1+1 v=(...((in*dn1+in1)*dn2+in2)*dn3...+i2)*d1+i1 令： v0 = in 則： v1 = in*dn1+in1 = v0*dn1+in1 v2 = (v0*dn1+in1)*dn2+in2 = v1*dn2+in2 ...... 于是有： v0 = in vj = vj1*dnj+inj (j=1， 2， ..., n1) 同理可得： c0 = 1 cj = cj1*dnj+1 (j=1， 2， ..., n1) （ 2） 要適合 LR分析 ， 應該將文法改成右遞歸的 。出發(fā) ” ，將 “ 稱為 D的初態(tài) ” 改為 “ 稱為 D39。 如果真出口不是下一條三地址碼 ， 則仍需要生成兩條 goto語句 。 end loop。 else goto[i,x]:=j。 (0|1)*011(0|1)* ： 至少含一個 011的 01串 。 begin a:=2。 習題 （解） （ 1） 構(gòu)造基于 LR(0)項目集的識別活前綴的 DFA （ 2） 指出 DFA中所有含有沖突的項目集 ， 并說明這些沖突可以用 SLR(1)方法解決； E 39。 解： (a) 短 語： (T+F)*id、 (T+F)、 T+F、 id 直接短語： T+F、 id 句柄： T+F (b) a*b+c*d的中間代碼： (1) (+, b, c, t1) (2) (*, a, t1, t2) (3) (*, t2, d, t3) (c) 計算結(jié)果： t3=288 (d) 識別活前綴的 DFA： E ’→. EE →. E * TE →. TT →. T + FT →. FF →. i dE ’→E .E →E . * TE →T .T →T . + FT →F .F →i d .E →E * . TT →. T + FT →. FF →. i dT →T + . FF →. i dE →E * T .T →T . + FFETFid*+ +TididI0I1I2I3I4I5I6I7T →T + F . I8F28 部分習題解答 習題 寫出下述語言的正規(guī)式描述 （ 1） 由偶數(shù)個 0和奇數(shù)個 1構(gòu)成的所有 01串 （ 2） 所有不含子串 011的 01串 （ 3） 每個 a后面至少緊隨兩個 b的 ab串 （ 4） C的形如 /*…*/ 的注釋 。 } | T { =。 三、計算題（ 1） 1（ 13分 ） 已知一個 NFA如圖 。 3（ 4分 ） 試證明正規(guī)式 (ab)*a與 a(ba)*是等價的 。 ? 習題與試題的目的區(qū)別：習題的目的是通過反復的練習理解、掌握所學知識，會有不少繁、難、大量步驟的題；試題的目的是考察對本課程綜合掌握的情況，特點是短時間內(nèi)覆蓋大量內(nèi)容。 5. 二義性的消