• /  72
  • 下載費用: 24.9積分  

編譯原理——第五章-3.ppt

'編譯原理——第五章-3.ppt'
*編譯方法中國人民大學信息學院陳文萍*第五章 語法分析——自下而上分析5.1 自下而上分析基本問題5.2算符優先分析5.3 LR 分析法5.4 語法分析器的自動產生工具 YACC*5.1 自下而上分析基本問題自下而上語法分析試圖將一個字符串反向歸約至開始符號比自上而下語法分析更有效率,對語法的限制更少移進-歸約過程移進:將一個終結符推進棧歸約:當棧頂形成某個產生式的候選式時,把這些符號從棧中彈出,把產生式的左部符號壓入棧*文法G[S]: (1) S → aAcBe (2) A → b (3) A → Ab (4) B → dbbcdeA 3) #ab bcde# 歸約(A→b)A 5) #aAb cde# 歸約(A→Ab)B 8) # aAcd e# 歸約(B→d)S10) #aAcBe # 歸約(S→aAcBe)分析符號串abbcde是否G[S]的句子步驟符號棧輸入符號串動作 1) # abbcde# 移進 2) #a bbcde# 移進 4) #aA bcde# 移進 6) #aA cde# 移進 7) #aAc de# 移進 9) #aAcB e# 移進11) #S # 接受對輸入串abbcde#的移進-規約分析過程S?aAcBe?aAcde?aAbcde?abbcdea*規范歸約短語、直接短語、句柄的定義: 文法G[S],S αAδ,且A β則稱β是句型αβδ相對于非終結符A的短語。 若有A ? β,則稱β 是句型α β δ相對于該規則A → β的直接短語。 一個句型的最左直接短語稱為該句型的句柄。規范歸約:設α是文法G的一個句子,稱序列αn ,αn-1,…, α0 是α的一個規范規約,如果此序列滿足:αn = αα0 為文法的開始符,即α0 = S對任何i,0<i=<n, αi-1 是對αi,把句柄 替換為相應產生式的左部符號而得到的自頂向下最右推導的逆過程規范推導:最右推導規范句型:規范推導所得的句型*規范歸約例 句型 歸約規則 abbcde (2) A → b aAbcde (3) A → Ab aAcde (4) B → d aAcBe (1)S → aAcBe S從語法樹角度看句柄: 最左子樹端末結的自左至右排列,這棵子樹只有而且必須有父子兩代SaAcBeAbbSaAcBeAbSddaAcBed*規約T ? intT + int | 移進T + | int移進int | * int + int移進int * | int + int移進|int * int + intE |規約E ? T + ET + E |規約E ? TT + T |移進T | + int規約T ? int * Tint * T | + int規約 T ? intint * int | + int文法G[E]: E ? T + E | TT ? int * T | int | (E)ETE+int*intTintT*移進-歸約過程 (1)+int*intint?|int * int + int文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(2)+int*intint?int | * int + int|int * int + int文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(3)+int*intint?int | * int + intint * | int + int|int * int + int文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(4)+int*intint?int | * int + intint * | int + int|int * int + intint * int | + int文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(5)+int*intintTint | * int + intint * | int + int|int * int + intint * T | + intint * int | + int?文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(6)T+int*intintTint | * int + intint * | int + int|int * int + intT | + intint * T | + intint * int | + int?文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(7)T+int*intintTT + | intint | * int + intint * | int + int|int * int + intT | + intint * T | + intint * int | + int?文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(8)T+int*intintTT + int | T + | intint | * int + intint * | int + int|int * int + intT | + intint * T | + intint * int | + int?文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(9)T+int*intTintTT + int | T + | intint | * int + intint * | int + int|int * int + intT + T |T | + intint * T | + intint * int | + int?文法G[E]: E ? T + E | TT ? int * T | int | (E)*移進-歸約過程(10)TE+int*intTintTT + int | T + | intint | * int + intint * | int + int|int * int + intT + E |T + T |T | + intint * T | + intint * int | + int?文。省略部分。 A ?b A ?Ab B ?dI0 : S’ ? ? S S ? ? a A c B e I1 : S’ ? S ?I2 : S ? a ? A c B e A ? ? b A ? ? AbI3 : S ? a A ? c B e A ? A ? bI4 : A ? b ?I5 : S ? a A c ? B e B ? ? dI7 : S ? a A c B ? eI8 : B ? d ?I9 : S ? a A c B e ?I6 : A ? A b ?SaAbbcBedG[L]= ab+ cde*例 G[S]的LR(0)分析表*Step states. Syms. The rest of input action goto 1 0 # abbcde# s2 2 02 #a bbcde# s4 3 024 #ab bcde# r2 3 4 023 #aA bcde# s6 5 0236 #aAb cde# r3 3 6 023 #aA cde# s5 7 0235 #aAc de# s8 8 02358 #aAcd e# r4 7 9 02357 #aAcB e# s9 10 023579 #aAcBe # r1 1 11 01 #S # acc 對輸入串abbcde#的分析過程*Step states. Syms. The rest of input action goto 1 0 # abbce# s2 2 02 #a bbce# s4 3 024 #ab bce# r2 3 4 023 #aA bce# s6 5 0236 #aAb ce# r3 3 6 023 #aA ce# s5 7 0235 #aAc e# 出錯說明abbce#不是 文法 G[S]的句子 對輸入串abbce#的分析過程*SLR分析法為什么SLR?LR(0)文法項目集的規范族中可能含有沖突的項目(狀態),因沒有查看下一符號,決定分析動作僅僅根據到目前已經看到的東西.解決方法:向前查看(“展望”): SLR(1),LR(1),LALR(1)*例:文法G‘: (0) S’ ? S (1) S ? rD (2) D? D,i (3) D ? iI0: S‘ → ? S S‘ → ?rDI2: S → r?D D → ?D,i D → ? iI3: S → rD ? D →D ?,iI4: D → i ?I5: D → D,?iI1: S‘ → S ?I6: D →D,i ?SriD,iLR(0)分析表I3中的兩個項目互相沖突,如何解決?*SLR分析法利用FOLLOW(S) ? {, } =? 信息解決沖突向前查看一個符號,看其是否是S的后跟符號(FOLLOW(S)),若否則移進,是則歸約。SLR(1)分析表I3: S → rD ? D →D ?,i*SLR分析法SLR分析方法的特征如果文法的有效項目集中有沖突動作,可通過考察有關非終結符號的FOLLOW集合而得到解決一個LR(0)規范族中含有如下的項目集(狀態)I I = {X →? ? b? , A → ? ? , B → ? ? } 若有:FOLLOW(A) ∩FOLLOW(B) = ? FOLLOW(A) ∩ = ? //移進識別 FOLLOW(B) ∩ = ? //移進識別狀態I面臨某輸入符號a 1) 若a=b,則移進 2) 若a?FOLLOW(A), 則用產生式 A → ? 進行歸約 3) 若a?FOLLOW(B), 則用產生式 B → ? 進行歸約 4) 此外,報錯若一個文法的LR(0)分析表中所含有的動作沖突都能用上述方法解決,則稱這個文法是SLR(1)文法*SLR分析表的構造構造文法G的SLR(1)分析表構造文法G的拓廣文法G’的LR(0)項目集規范族C,及活前綴識別自動機的狀態轉換函數GO。構造SLR(1)分析表的ACTION表和GOTO表: a) 若項目A→? ? a?屬于Ik,且轉換函數GO(Ik,a)= Ij ,當a為終結符時,則置ACTION[k,a]為Sj b) 若項目A→? ?屬于Ik ,則對a為任何終結符或‘#’,且滿足a?FOLLOW(A)時,置ACTION[k,a] = rj ,j為產生式在文法G‘中的編號 c) 若GO(Ik,A)= Ij ,則置GOTO[k,A]=j,其中A為非終結符,j為某一狀態號 d) 若項目S‘→S ?屬于Ik ,則置ACTION[k,#] = acc e) 其它填上“報錯標志”*SLR(1)文法如果分析表中每個表項中的動作都是唯一的,既不含有沖突動作,則稱它為文法G的SLR分析表具有SLR分析表的文法,稱為SLR(1)文法使用SLR分析表的分析器,稱為SLR分析器
關 鍵 詞:
編譯 第五 原理
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:編譯原理——第五章-3.ppt
鏈接地址: http://www.476824.live/p-51497027.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 北京pk10基本走势图360 河南十一选五走势图表 河北快三预测推荐号码 极速时时彩官方开奖 乾鑫配资 甘肃十一选五前三走势图 陕西省体彩11选五开奖 股票上涨下跌的原理 好运快三合法吗 大乐透开奖结果查询