《編譯原理-LR分析法.ppt》由會員分享，可在線閱讀，更多相關《編譯原理-LR分析法.ppt（54頁珍藏版）》請在裝配圖網(wǎng)上搜索。

7自底向上分析 Bottom upParsing LR分析器 7 1LR分析器 自底向上分析 Bottom upParsing L left to rightscanning自左向右掃描 R rightmostderivationinreverse最右推導的逆 5 3 4 1LR分析方法概述5 3 4 2LR 0 分析器5 3 4 3SLR 1 分析器5 3 4 4LR 1 分析器5 3 4 5LALR 1 分析器 7 1 1LR 0 分析器 例 考慮文法G S S aAA cA d識別accd是否該文法的句子 A c AA cAA ds2 S a AA cAA ds1 S aAs0 start A cA s4 S aA s5 A d s3 A d d A c a c A c AA cAA ds2 S a AA cAA ds1 S aAs0 start A cA s4 S aA s5 A d s3 A d d A c a c s0accd shifts0as1ccd shifts0as1cs2cd shifts0as1cs2cs2d shifts0as1cs2cs2ds3 reduceA ds0as1cs2cs2As4 reduceA cAs0as1cs2As4 reduceA cAs0as1As5 reduceS aAs0S accept G S 1 S aA2 A cA3 A daccd L G S 根據(jù)上述例子 可以總結如下 一 概念產(chǎn)生式右部符號被識別的多少 在產(chǎn)生式右部加上 指示位置 項目 在文法產(chǎn)生式右部某個位置標有 的產(chǎn)生式 稱為文法的一個LR 0 項目 為了敘述方便 形如A 的項目稱為歸約項目 形如A B 的項目稱為待約項目 基本項目 形如A a 的項目稱為移進項目 定義 有效項目 項目A 1 2對活前綴 1是有效的 如果存在規(guī)范推導S Aw 1 2w 若項目A 1 B 2對活前綴 1是有效的 且B 是產(chǎn)生式 則項目B 對活前綴 1也是有效的 據(jù)假設 存在一個規(guī)范推導S Aw 1B 2w設 2w xw 則對任何B 有規(guī)范推導rmS Aw 1B 2w 1Bxw 1 xw所以B 對活前綴 1也是有效的 伽馬 艾塔 定義 有效項目集 項目集規(guī)范族 文法G的某個活前綴 的所有有效項目組成的集合 稱為活前綴 的LR 0 有效項目集 文法G的所有有效項目集組成的集合 稱為G的LR 0 項目集規(guī)范族 定義 項目閉包 設I是文法G的一個LR 0 項目集合 I的項目閉包closure I 定義如下 1 I closure I 2 若項目A B closure I 且B 是G的產(chǎn)生式 則項目B closure I 3 closure I 僅包含上述兩條規(guī)則確定的LR 0 項目 定義 轉移函數(shù) 若I是文法G的一個LR 0 項目集 X是G中的文法符號 定義go I X closure J 其中J A X A X I 稱函數(shù)go I X 為轉移函數(shù) 項目A X 稱為項目A X 后繼 二 識別句柄和活前綴的自動機 若文法G VT VN S P 則識別G的句柄的自動機為DFAM VT VN Q G的LR 0 項目集規(guī)范族 q0 closure S S F 所有含歸約項目的有效項目集組成的集合 go I X 若將所有狀態(tài)均視為終態(tài) 則識別活前綴的自動機DFAM VT VN Q G的LR 0 項目集規(guī)范族 q0 closure S S F Q go I X 定理 對于拓廣文法G 的每一個活前綴 它的有效項目集恰好是從識別G 活前綴的自動機的初態(tài)出發(fā) 經(jīng)過 路徑所到達的那個狀態(tài)所代表的項目集合 例 設拓廣文法G S 的產(chǎn)生式為 S SS aA bBA cA dB cB d A c AA cAA dI4 S a AA cAA dI2 S b BB cBB dI3 B c BB cBB dI5 S SS aAS bBI0 start S S I1 A cA I8 S aA I6 A d I10 A d d A c a b S S bB I7 B cB I6 B d I11 B d d B c c c 識別文法活前綴的DFA LR 0 分析表 三 LR分析器的結構和工作過程 LR分析器的結構如圖 它的工作過程由算法1描述 輸入 a1 ai an LR驅動程序 分析表 輸出 棧 smXmsm 1Xm 1 s0 圖4 19一個LR分析器的模型 actiongoto 算法1 LR分析算法 輸入 一個輸入串w和文法G的一張LR分析表M 輸出 若w L G 輸出w的一個自底向上的分析 否則 輸出一個出錯表示 方法 分別置放s0到棧中和w 到輸入緩沖器中 置ip指向w 的第一個符號 repeatforeverbegin令s是棧頂狀態(tài)且a是ip所指向的符號ifaction s a shifts thenbegin將a和s 先后壓入棧內(nèi) 使ip指向輸入串中的下一個符號 end 算法1 LR分析算法 elseifaction s a reduceA thenbegin從棧頂彈出2 個符號 令s 是當前棧頂狀態(tài) 把A和goto s A 先后入棧 輸出產(chǎn)生式A endelseifaction s a acceptthenreturnelseerror end 7 1 2SLR 1 分析 若有效項目集中存在沖突動作 I X b A B 設當前輸入符號為a 1 若a b 則移進 2 若a Follow A 則用A 進行歸約 3 若a Follow B 則用B 進行歸約 4 其余情況報錯 SLR分析算法 算法2 構造SLR分析表 輸入 一個拓廣文法G 輸出 對于G 的分析表的action子表和goto子表方法 1 構造G 的LR 0 項目集規(guī)范族 2 對于狀態(tài)Ii的分析動作如下 a 若A aB Ii且go Ii a Ijaction i a shiftj b 若A Ii 對于所有a Follow A action i a reduceA A S c 若S S Ii action i accept3 若go Ii A Ij A VN 則goto i A j4 分析表其余位置為error SLR SLR 1 算法 如果文法G按上述算法構造出的分析表不存在沖突動作 則稱G為SLR文法 類似地 不難定義LR 0 文法 若將上述算法的2 b 步中的a Follow A 改為a VT 則由此修改后的算法所定義的文法 稱為LR 0 文法 問題 如何定義LR 0 文法 例 設文法G E 的產(chǎn)生式為 E E T TT T F FF E id并用SLR 1 方法分析id id id L G E G的拓廣文法G E 0 E E 4 T F 1 E E T 5 F E 2 E T 6 F id 3 T T F I0 E EE E TE TT T FT FF E F idI1 I0E E E E E TI2 I0T I4T E T T T F I3 I0F I4F I6F T F I4 I0 I4 I6 I7 F E E E TE TT T FT FF E F id I5 I0id I4id I6id I7id F id I6 I1 I8 E E TT T FT FF E F id I7 I2 I9 T T FF E F idI8 I4E F E E E TI9 I6T E E T T T FI10 I7F T T F I11 I8 F E G 0 E E 4 T F 1 E E T 5 F E 2 E T 6 F id 3 T T F E E E E T E T T T F T F F E F id E E E E E T T E T T T F F E E E TE TT T FT FF E F id I0 I1 I2 I6 F T F I3 F id id I5 T I2 F I3 id I5 E E TT T FT FF E F id T T FF E F id I7 F E E E T E I8 T E E T T T F I9 F I3 id I5 F T T F I10 id I4 I4 I7 F E I6 I11 E E E E T E T T T F T F F E F id E E E E E T T E T T T F F E E E TE TT T FT FF E F id I0 I1 I2 I6 F T F I3 F id id I5 T I2 F I3 id I5 E E TT T FT FF E F id T T FF E F id I7 F E E E T E I8 T E E T T T F I9 F I3 id I5 F T T F I10 id I4 I4 I7 F E I6 I11 I0 I1 I6 I9 E T toI7 F toI3 toI4 id toI5 I2 I7 I10 T F toI4 id toI5 I3 F I4 I8 I11 E toI6 T toI4 F toI5 I5 id id 圖4 24識別文法 4 22 的活前綴的DFA I1 E E I2 E T I9 E E T E E TT T FT T FI X b A B 若 b FOLLOW A FOLLOW B 則 面對當前讀入符號a 狀態(tài)I的解決方法 1 若a b 則移進 2 若a b 且a FOLLOW A 則用A 進行歸約 3 若a b 且a FOLLOW B 則用B 進行歸約 4 此外 報錯 這種解決方法是比較簡單的 因此稱作SLR分析 由此構造的分析表 稱作SLR分析表 對于表達式文法的例子 FOLLOW集如下 I1 E E E E T I2 E T T T F I9 E E T T T F G 0 E E 4 T F 1 E E T 5 F E 2 E T 6 F id 3 T T F I1 FOLLOW E I2 FOLLOW E I9 FOLLOW E 可用SLR 1 方法實現(xiàn) 表4 11文法 4 22 的SLR分析表 Follow E 表 關于id id id的LR分析過程 7 1 3LR 1 分析 例 設文法G的產(chǎn)生式為 1 S L R 2 S R 拓廣文法G 的LR 0 項目集規(guī)范族為 I0 S S S L R S R L R L id R L I1 S S I2 S L R R L I3 S R I4 L R R L L R L id I5 L id I6 S L R R L L R L id I7 L R I8 R L I9 S L R 3 L R 4 L id 5 R L I1 I0 I3 I2 I6 I9 I8 I7 I5 I4 start S R L id id id L L R R 圖 識別文法G S 活前綴的DFA G S 0 S S 1 S L R 2 S R 3 L R 4 L id 5 R L LR 1 分析表的構造 問題分析 當識別出句柄時 活前綴中與句柄相關的非終結符號A的后繼符號集合 一般是非終結符號A的Follow集合的真子集 例如在前例中 若活前綴L是句柄 則它的后繼符號集合為 而Follow L 所以 只有在輸入符號為 時 用R L進行歸約 而輸入符號為 時 移進 可見用Follow集合來消除分析表的多重入口還是略嫌粗糙 LR 1 項目 由LR 0 項目和一個lookahead符號組成 A a LR 1 分析法的思想 用活前綴中與句柄相關的非終結符號A的后繼符號 亦稱為搜索符 集合 而不是Follow A 來避免分析表的多重入口 重新定義項目 使每個項目附帶一個向前搜索符 定義 LR 1 有效項目 LR 1 項目 A a a VT 對活前綴 是有效的 如果存在規(guī)范推導S Aw w且a First w 定理 若LR 1 項目 A B a 對活前綴 是有效的 且B 是一個產(chǎn)生式 則對任何b First a 項目 B b 也是活前綴 的有效項目 例 構造文法G S 的LR 1 分析表 LR 1 項目集規(guī)范族 I0 S S S L R S R L R L id R L I1 I0S S S I2 I0L S L R R L I3 I0R S R I4 I0 I4 L R R L L R L id I5 I0id I4id L id I6 I2 S L R R L L R L id I7 I4R L R I8 I4L R L I9 I6R S L R I10 I6L I11L R L I11 I6 I11 L R R L L R L id I12 I6id I11id L id I13 I11R L R G S 0 S S 1 S L R 2 S R 3 L R 4 L id 5 R L action goto 狀態(tài) id SLR0s4s51231acc2s6r53r24s4s5875r4r46s11s121097r3r38r5r59r110r511s11s12101312r413r3 例 構造文法S CCC cC d的LR 1 和LALR分析表 S S S CC C cC c dC d c dI0 S C C C cC C d I2 S S I1 S CC I5 S C C C c C C cC C d I6 C cC I9 C c C d I7 d c C c C c dC cC c dC d c dI3 C cC c dI8 C c C d c dI4 d c 圖 對于文法的轉移函數(shù)圖 文法的LR 1 分析表 S SS CCC cCC dI0 S C CC cCC dI2 S S I1 S CC I5 S C C C c CC cCC dI3 C cC I6 C c C d I4 d c c d 文法的LR 1 分析表 文法的LALR 1 分析表 7 1 4LALR分析表的構造 LR k 方法分析能力很強 但是也耗費大量存儲空間 在實際應用中 還須簡化 觀察圖4 27可知 1 從自動機狀態(tài)等價的角度來看 圖中彩色相同的狀態(tài)是等價的 這些等價狀態(tài)的特點是 它們的LR 0 有效項目集相同 由于判斷是否等價只須比較狀態(tài)的輸出弧 因而不難看出 LR 0 有效項目集相同的狀態(tài)必定等價 2 對于初始狀態(tài)I0 其中的有效項目均可從項目 S S 推導出來 對于非初始狀態(tài)I2 I3 I6 則其中 點在最左端 的項目均可由 點不在最左端 的項目推導出來 觀察圖也可以得到相同結果 因此在實際存儲狀態(tài)時 可以只存儲 點不在最左端 的項目 為了敘述方便 引入 同心項 和項目集的 核 的概念 定義 同心項 如果兩個LR 1 項目集去掉搜索符之后是相同的 則稱這兩個項目集具有相同的心 定義 核 對于初始狀態(tài)I0 有效項目 S S 稱為I0的核 而對于非初始狀態(tài) 則其中 點不在最左端 的有效項目稱為它的核 LALR分析法的基本思想 在LR 1 項目集規(guī)范族中 合并同心項以減少狀態(tài)的數(shù)目 在存儲LR 1 有效項目集時 僅存儲其中的核 注意 由于同心項的合并 使項目的搜索符與活前綴的對應關系不唯一 降低了分析器的識別能力 參見以下兩例 C c C c d C cC c d C d c d I36 I0 Cc c C cC c d I89 C 活前綴Cc 與搜索符 對應 而活前綴c 與搜索符c和d對應 當合并后的自動機識別出活前綴CcC時 若當前的輸入符號是c或d LR 1 分析器馬上就能發(fā)現(xiàn)出錯 而LALR分析器此時則不行 必須先歸約 得到活前綴CC后才能發(fā)現(xiàn)出錯 例 在圖中 I3和I6 I8和I9合并后得到如下部分狀態(tài)圖 問題 LALR分析器識別活前綴的能力是否比LR 1 的差 答 一樣 既然都是識別文法活前綴的自動機 它們就是等價的 例 考慮文法GS SS aAd bBd aBe bAeA cB c構造G的LR 1 項目集規(guī)范族如下 I0 S S S aAd S bBd S aBe S bAe I1 I0S S S I2 I0a S a Ad S a Be A cdB ceI3 I0b S b Bd S b Ae A ceB cd I4 I2A S aA d I5 I2B S aB e I6 I2c A c dB c eI7 I3B S bB d I8 I3A S bA e I9 I3c A c eB c dI10 I4d S aAd I11 I4e S aBe I12 I7d S bBd I13 I8e S bAe 若將同心項I6和I9合并 則得到項目集I69 A c d eB c d e該項目集含 歸約 歸約 沖突 因此 文法G是LR 1 文法 但不是LALR文法 一 LALR 1 分析表的原理性構造方法 構造LR 1 項目集族 如果它不存在沖突 就把同心集合并在一起 若合并后不存在歸約 歸約沖突 則按這個集族構造文法LALR 1 分析表 算法 LALR分析表的構造輸入 拓廣文法G 輸出 對于G 的LALR 1 分析表方法 1 構造文法的LR 1 項目集族C I0 I1 In 2 合并C中的同心集 得到C J0 J1 Jm 3 從C 出發(fā)構造action表 a 若 A a b Ji且go Ji a Jj置action i a shiftj b 若 A a Ji 置action i a rA A S c 若 S S Ji 置action i accept4 若go Ik A Jj A VN 則goto k A j5 分析表其余位置為error 二 LALR分析表的有效構造方法 前算法在構造LALR分析表時 耗費的存儲空間與LR 1 算法完全相同 代價還是太大 可以從兩個方面改進 1 存儲有效項目集時 只存儲它們的核 每當需要完整的有效項目集時 再根據(jù)核來計算 2 直接生成LALR項目集規(guī)范族的核 這是有效構造方法的關鍵 注意 LALR項目的搜索符一般是與該項目相關的非終結符號的Follow集的子集 這正是LALR分析法比SLR分析法強的原因 直接生成LALR項目集規(guī)范族的核的方法如下 1 構造LR 0 項目集規(guī)范族的核及其自動機 2 為LR 0 項目集規(guī)范簇中的每個核項目配上適當?shù)乃阉鞣?核項目的搜索符無非有兩種產(chǎn)生途徑 若搜索符從其父核傳遞下來 則稱這樣的搜索符為 傳播的 否則 稱搜索符為 自生的 下面算法確定核項目的搜索符是自生的或者是傳播的 for有效項目集I的核K中的每一項目B dobeginJ closure B forJ中的每一個項目 A X a do如果a 則有效項目集go I X 中的核項目 A X a 中的搜索符是自生的 否則就是傳播的 練習 已知文法 請構造LALR分析表 構造文法的LALR 1 項目集的核 LR 0 項目集的核 I0 S SI1 S S I2 S L RI3 S R I4 L RI5 L id I6 S L RI7 L R I8 R L I9 S L R 計算closure S S S S S L R S R L R L id R L G S 0 S S 1 S L R 2 S R 3 L R 4 L id 5 R L 表4 15搜索符的傳播 表4 16搜索符的計算 Thanks