• /  48
  • 下載費用: 19.9積分  

編譯原理課件CHAPTER 4(Syntax Analysis-3).ppt

'編譯原理課件CHAPTER 4(Syntax Analysis-3).ppt'
Chapter4 Syntax Analysis語法分析概述 (An overview of parsing)自頂向下分析(Top-down Parsing)自底向上分析(Bottom-up Parsing)算符優先分析 (Operator-precedence Parsing)LR 分析(LR Parser)Date14.5 LR分析LR(k)分析技術:L 指從左至右掃描輸入符號串R 指構造一個最右推導的逆過程(最左歸約)k 指在作出分析決定前要向前看的輸入符號個數,通常為 0 或 1LR 分析技術是功能最強的(自底向上)語法分析技術,適用文法廣,效率高,分析能力強Date24.5 LR分析LR分析器的邏輯結構:P217 Fig4.29LR分析程序——固定不變的分析表——動作表(action)、狀態轉移表(goto)?!獱顟B符號、文法符號輸入緩沖輸出——產生式序列Date34.5 LR分析LR分析器運行:根據當前棧頂狀態符號與輸入符號查分析表決定下一步動作假設當前 (s0X1s1X2s2…Xmsm, aiai+1…an$)1、action (sm, ai) = shift s (s0X1s1X2s2…Xmsmais, ai+1…an$)2、action (sm, ai) = reduce A→β (s0X1s1X2s2…Xm-rsm-rAs, aiai+1…an$)Date44.5 LR分析LR分析算法: P 218-219LR分析的關鍵問題是如何構造分析表,不同的構造方法形成不同的分析方法,主要有 LR(0)、SLR、LR(1)、LALRDate54.5 LR分析例子: 分析句子:abbcde文法G[S]: (1) S → aAcBe (2) A → b (3) A → Ab (4) B → dDate64.5 LR分析ACTIONGOTOacebd$SAB0S211Acc2S433S5S64R2R2R2R2R2R25S876R3R3R3R3R3R37S98R4R4R4R4R4R49R1R1R1R1R1R1LR(0)分析表P218 算法4.7Date74.5 LR分析對 abbcde$ 的分析過程步驟棧輸入串ACTIONGOTO10abbcde$S220a2bbcde$S430a2b4bcde$R2340a2A3bcde$S650a2A3b6cde$R3360a2A3cde$S570a2A3c5de$S880a2A3c5d8e$R4790a2A3c5B7e$S9100a2A3c5B7e9$R11110S1$AccDate84.5 LR分析LR分析過程中的性質與特點:棧中的文法符號串并上剩余的輸入串構成一個右句型(規范句型)當該右句型的句柄出現在棧頂時,歸約,否則,移進棧中的文法符號串是當前句型的前綴,該前綴不包含句型句柄后面的符號,稱之為活前綴(Viable Prefixes)Date94.5 LR分析活前綴:上例 aAbcde ? , a , aA , aAb可歸前綴:包含完整句柄的活前綴設 G=(Vn,Vt,P,S)為一文法,若有S’ ? αAω ?αβω 是一規范推導,且γ是αβ的前綴,則稱是文法G的活前綴。Date104.5 LR分析分析過程可以看作是識別文法規范句型活前綴的過程。只要每一時刻棧中的文法符號串是某規范句型的活前綴,則說明已分析的部分是正確的一個文法的規范句型的所有活前綴構成一個語言,而且是正規語言,可以用一個 DFA 來識別Date114.5 LR分析例子:文法G[S]: (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d014235769SabAbcBed8?*Date124.5 LR分析每個狀態都是活前綴的識別態,雙圈狀態是可歸前綴(句柄)識別態,標識了*的狀態是句子識別態分析句子的過程可以看作在上面這個 DFA 上運行的過程014235769SabAbcBed8?*(1) S → aAcBe (2) A → b (3) A → Ab (4) B → dDate13例子:步驟棧輸入串ACTIONGOTO10abbcde$S2014235769SabAbcBed?*8Date14例子:步驟棧輸入串ACTIONGOTO10abbcde$S220a2bbcde$S4014235769SabAbcBed8?*Date15例子:步驟棧輸入串ACTIONGOTO10abbcde$S220a2bbcde$S430a2b4bcde$R23014235769SabAbcBed8?*Date16例子:步驟棧輸入串ACTIONGOTO10abbcde$S220a2bbcde$S430a2b4bcde$R2340a2A3bcde$S6014235769SabAbcBed8?*Date17例子:步驟棧輸入串ACTIONGOTO10abbcde$S220a2bbcde$S430a2b4bcde$R2340a2A3bcde$S650a2A3b6cde$R33014235769SabAbcBed8?*Date18例子:步驟棧輸入串ACTIONGOTO30a2b4bcde$R2340a2A3bcde$S650a2A3b6cde$R3360a2A3cde$S5*014235769SabAbcBed8?Date19例子:步驟棧輸入串ACTIONGOTO40a2A3bcde$S650a2A3b6cde$R3360a2A3cde$S570a2A3c5de$S8*014235769SabAbcBed8?Date20例子:步驟棧輸入串ACTIONGOTO50a2A3b6cde$R3360a2A3cde$S570a2A3c5de$S880a2A3c5d8e$R47014235769SabAbcBed8?*Date21例子:步驟棧輸入串ACTIONGOTO60a2A3cde$S570a2A3c5de$S880a2A3c5d8e$R4790a2A3c5B7e$S9014235769SabAbcBed8?*Date22例子:步驟棧輸入串ACTIONGOTO70a2A3c5de$S880a2A3c5d8e$R4790a2A3c5B7e$S9100a2A3c5B7e9$R11014235769SabAbcBed8?*Date23例子:步驟棧輸入串ACTIONGOTO80a2A3c5d8e$R4790a2A3c5B7e$S9100a2A3c5B7e9$R11110S1$Acc014235769SabAbcBed8?*Date244.5 LR分析構造識別活前綴的DFA拓廣文法:增加產生式 S’→S,S’作為新的開始符號文法等價確保文法的開始符號只在產生式的左部出現為了在分析過程中區別是歸約到了文法的最初開始符號還是產生式右邊出現的開始符號Date254.5 LR分析LR(0)項目(item)在文法產生式右部的適當位置添加圓點構成項目例: A→XYZ A→·XYZ A→X·YZ A→XY·Z A→XYZ·例: A→ε 。省略部分。sure ( { E’ ? ·E } ) 若 A→α·Bβ在 closure(I),且 B→γ是產生式,將 B→·γ添加到 closure(I) 中E’ ? E E ? E + T | TT ? T * F | FF ? ( E ) | idDate284.5 LR分析goto 函數goto ( I, X )例: 求 goto ( { E’ ? E·, E ? E ·+ T } , +) goto ( I, X ) = closure (A→αX·β),其中 A→α·Xβ在 I 中E’ ? E E ? E + T | TT ? T * F | FF ? ( E ) | idDate294.5 LR分析構造規范的 LR(0)項目集族算法 P 224C = { closure ( { S’ ? ·S }) }C = C ∪ goto ( I, X )例子:P 224-225Date304.5 LR分析構造識別文法所有活前綴的 DFA項目集作為狀態,項目集族作為狀態集例子:P 226goto ( I, X ) 作為狀態轉換函數Date314.5 LR分析每個狀態都是識別態,識別的是從初態到該狀態的通路上標記的文法符號構成的活前綴初態是活前綴 ε 的有效項目集活前綴的有效項目(Valid items)集活前綴γ的有效項目集是從初態出發經過γ道路所到達的那個狀態所代表的項目集分析過程中分析棧中的活前綴的有效項目集是棧頂狀態 Sm 所代表的那個集合,棧頂狀態體現了棧里一切有用的信息Date32例:文法G’ S’? E E ? T + E E ? T T ? int * T T ? int T ? (E)4.5 LR分析Date33 S’ ? . EE ? . TE ? .T + ET ? .(E)T ? .int * TT ? .intS’ ? E .E ? T.E ? T. + ET ? int. * TT ? int.T ? (. E)E ? .TE ? .T + ET ? .(E)T ? .int * TT ? .intE ? T + E.E ? T + . EE ? .TE ? .T + ET ? .(E)T ? .int * TT ? .intT ? int * .TT ? .(E)T ? .int * TT ? .intT ? int * T.T ? (E.)T ? (E).ET(intint*)EETint((int+(1234567891011TTDate344.5 LR分析項目集合中的沖突移進-歸約沖突項目集合中同時含有形如 A→α · aβ和 B→γ·的項目歸約-歸約沖突項目集合中同時含有形如 A→α· 和 B→ β· 的項目Date354.5 LR分析如果文法 G 的規范 LR(0)項目集族中不含有移進-歸約沖突和歸約-歸約沖突,則稱文法 G 為 LR(0)文法構造分析表時沒有向前看,或者說向前看了 0 個符號Date364.5 LR分析構造 LR(0)分析表:若 goto (Ik,a)= Ij,則 action (k,a)= Sj若 goto (Ik,A)= Ij,則 goto(k,A)= j若 Ik 包含 S’→S · ,則action(k,$)= acc若 Ik 包含 A→α· ,則aciton(k,a)= rj,a為任何終結符號或 $,j為產生式 A→α的編號Date37例:文法G’ (0)S’? S (1)S ? aA (2)S ? bB (3)A ? cA (4)A ? d (5)B ? cB (6)B ? d Date38 (0)S’? S (1)S ? aA (2)S ? bB (3)A ? cA (4)A ? d (5)B ? cB (6)B ? d I0: S‘ → ?S S → ?aAS → ?bBI4: A → c?A A → ?cAA → ?dI2: S → a?A A → ?cAA → ?dI5: B → c?B B → ?cBB → ?dI3: S → b?B B → ?cBB → ?dI1: S‘ → S?I8: A → cA?I10: A → d?I6: S → aA?I7: S → bB?I11: B → d?I9: B → cB?baSccccAddABddBDate39ACTIONGOTOabcd$SAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6LR(0)分析表Date40 分析一個句子:accd$步驟棧輸入串ACTIONGOTO10accd$S220a2ccd$S430a2c4cd$S440a2c4c4d$S1050a2c4c4d10$R4860a2c4c4A8$R3870a2c4A8$R3680a2A6$R1190S1$AccDate414.5 LR分析對于規范 LR(0)項目集族中有沖突的項目集合,有的可以通過向前看一個符號(考察當前正在掃描的符號)來解決沖突當存在沖突時才向前看一個符號,因此是一種簡單的LR(1)分析方法,稱為 SLR 分析Date42文法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)分析表Date434.5 LR分析解決方法:假設一個LR(0)項目集規范族中有如下項目集合: {X → α·bβ,A → γ·,B → δ·} 即存在移進-歸約沖突和歸約-歸約沖突Date444.5 LR分析如果FOLLOW(A)∩ FOLLOW(B)∩  =ф,則可以如下來解決沖突(假設當前符號是 a ):1、若 a = b,則移進2、若 a∈ FOLLOW(A),則用產生式 A → γ歸約3、若 a∈ FOLLOW(B),則用產生式 B → δ歸約4、否則,報錯Date45文法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,iSLR(1)分析表Date464.5 LR分析如果文法 G 的規范LR(0)項目集族中的移進-歸約沖突和歸約-歸約沖突可以用上述方法解決,則稱文法 G 為 SLR(1)文法。Date47The End!Date48
關 鍵 詞:
chapter 編譯 syntax analysis 原理
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:編譯原理課件CHAPTER 4(Syntax Analysis-3).ppt
鏈接地址: http://www.476824.live/p-51497022.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

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

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

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 吉林11选5手机助手 疯狂飞艇计划 湖北快3形态走势图 大发快三首页 股票涨跌的秘密 福利彩票北京pk拾官网 合肥定盘星配资公司 内蒙古快3中奖规则 买台湾马资料 北京11选五前三组奖金