《編譯原理-LR分析法.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理-LR分析法.ppt（54頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

7自底向上分析 Bottom upParsing LR分析器 7 1LR分析器 自底向上分析 Bottom upParsing L left to rightscanning自左向右掃描 R rightmostderivationinreverse最右推導(dǎo)的逆 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識(shí)別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ù)上述例子 可以總結(jié)如下 一 概念產(chǎn)生式右部符號(hào)被識(shí)別的多少 在產(chǎn)生式右部加上 指示位置 項(xiàng)目 在文法產(chǎn)生式右部某個(gè)位置標(biāo)有 的產(chǎn)生式 稱為文法的一個(gè)LR 0 項(xiàng)目 為了敘述方便 形如A 的項(xiàng)目稱為歸約項(xiàng)目 形如A B 的項(xiàng)目稱為待約項(xiàng)目 基本項(xiàng)目 形如A a 的項(xiàng)目稱為移進(jìn)項(xiàng)目 定義 有效項(xiàng)目 項(xiàng)目A 1 2對(duì)活前綴 1是有效的 如果存在規(guī)范推導(dǎo)S Aw 1 2w 若項(xiàng)目A 1 B 2對(duì)活前綴 1是有效的 且B 是產(chǎn)生式 則項(xiàng)目B 對(duì)活前綴 1也是有效的 據(jù)假設(shè) 存在一個(gè)規(guī)范推導(dǎo)S Aw 1B 2w設(shè) 2w xw 則對(duì)任何B 有規(guī)范推導(dǎo)rmS Aw 1B 2w 1Bxw 1 xw所以B 對(duì)活前綴 1也是有效的 伽馬 艾塔 定義 有效項(xiàng)目集 項(xiàng)目集規(guī)范族 文法G的某個(gè)活前綴 的所有有效項(xiàng)目組成的集合 稱為活前綴 的LR 0 有效項(xiàng)目集 文法G的所有有效項(xiàng)目集組成的集合 稱為G的LR 0 項(xiàng)目集規(guī)范族 定義 項(xiàng)目閉包 設(shè)I是文法G的一個(gè)LR 0 項(xiàng)目集合 I的項(xiàng)目閉包c(diǎn)losure I 定義如下 1 I closure I 2 若項(xiàng)目A B closure I 且B 是G的產(chǎn)生式 則項(xiàng)目B closure I 3 closure I 僅包含上述兩條規(guī)則確定的LR 0 項(xiàng)目 定義 轉(zhuǎn)移函數(shù) 若I是文法G的一個(gè)LR 0 項(xiàng)目集 X是G中的文法符號(hào) 定義go I X closure J 其中J A X A X I 稱函數(shù)go I X 為轉(zhuǎn)移函數(shù) 項(xiàng)目A X 稱為項(xiàng)目A X 后繼 二 識(shí)別句柄和活前綴的自動(dòng)機(jī) 若文法G VT VN S P 則識(shí)別G的句柄的自動(dòng)機(jī)為DFAM VT VN Q G的LR 0 項(xiàng)目集規(guī)范族 q0 closure S S F 所有含歸約項(xiàng)目的有效項(xiàng)目集組成的集合 go I X 若將所有狀態(tài)均視為終態(tài) 則識(shí)別活前綴的自動(dòng)機(jī)DFAM VT VN Q G的LR 0 項(xiàng)目集規(guī)范族 q0 closure S S F Q go I X 定理 對(duì)于拓廣文法G 的每一個(gè)活前綴 它的有效項(xiàng)目集恰好是從識(shí)別G 活前綴的自動(dòng)機(jī)的初態(tài)出發(fā) 經(jīng)過 路徑所到達(dá)的那個(gè)狀態(tài)所代表的項(xiàng)目集合 例 設(shè)拓廣文法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 識(shí)別文法活前綴的DFA LR 0 分析表 三 LR分析器的結(jié)構(gòu)和工作過程 LR分析器的結(jié)構(gòu)如圖 它的工作過程由算法1描述 輸入 a1 ai an LR驅(qū)動(dòng)程序 分析表 輸出 棧 smXmsm 1Xm 1 s0 圖4 19一個(gè)LR分析器的模型 actiongoto 算法1 LR分析算法 輸入 一個(gè)輸入串w和文法G的一張LR分析表M 輸出 若w L G 輸出w的一個(gè)自底向上的分析 否則 輸出一個(gè)出錯(cuò)表示 方法 分別置放s0到棧中和w 到輸入緩沖器中 置ip指向w 的第一個(gè)符號(hào) repeatforeverbegin令s是棧頂狀態(tài)且a是ip所指向的符號(hào)ifaction s a shifts thenbegin將a和s 先后壓入棧內(nèi) 使ip指向輸入串中的下一個(gè)符號(hào) end 算法1 LR分析算法 elseifaction s a reduceA thenbegin從棧頂彈出2 個(gè)符號(hào) 令s 是當(dāng)前棧頂狀態(tài) 把A和goto s A 先后入棧 輸出產(chǎn)生式A endelseifaction s a acceptthenreturnelseerror end 7 1 2SLR 1 分析 若有效項(xiàng)目集中存在沖突動(dòng)作 I X b A B 設(shè)當(dāng)前輸入符號(hào)為a 1 若a b 則移進(jìn) 2 若a Follow A 則用A 進(jìn)行歸約 3 若a Follow B 則用B 進(jìn)行歸約 4 其余情況報(bào)錯(cuò) SLR分析算法 算法2 構(gòu)造SLR分析表 輸入 一個(gè)拓廣文法G 輸出 對(duì)于G 的分析表的action子表和goto子表方法 1 構(gòu)造G 的LR 0 項(xiàng)目集規(guī)范族 2 對(duì)于狀態(tài)Ii的分析動(dòng)作如下 a 若A aB Ii且go Ii a Ijaction i a shiftj b 若A Ii 對(duì)于所有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òu)造出的分析表不存在沖突動(dòng)作 則稱G為SLR文法 類似地 不難定義LR 0 文法 若將上述算法的2 b 步中的a Follow A 改為a VT 則由此修改后的算法所定義的文法 稱為L(zhǎng)R 0 文法 問題 如何定義LR 0 文法 例 設(shè)文法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識(shí)別文法 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 則 面對(duì)當(dāng)前讀入符號(hào)a 狀態(tài)I的解決方法 1 若a b 則移進(jìn) 2 若a b 且a FOLLOW A 則用A 進(jìn)行歸約 3 若a b 且a FOLLOW B 則用B 進(jìn)行歸約 4 此外 報(bào)錯(cuò) 這種解決方法是比較簡(jiǎn)單的 因此稱作SLR分析 由此構(gòu)造的分析表 稱作SLR分析表 對(duì)于表達(dá)式文法的例子 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 方法實(shí)現(xiàn) 表4 11文法 4 22 的SLR分析表 Follow E 表 關(guān)于id id id的LR分析過程 7 1 3LR 1 分析 例 設(shè)文法G的產(chǎn)生式為 1 S L R 2 S R 拓廣文法G 的LR 0 項(xiàng)目集規(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 圖 識(shí)別文法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 分析表的構(gòu)造 問題分析 當(dāng)識(shí)別出句柄時(shí) 活前綴中與句柄相關(guān)的非終結(jié)符號(hào)A的后繼符號(hào)集合 一般是非終結(jié)符號(hào)A的Follow集合的真子集 例如在前例中 若活前綴L是句柄 則它的后繼符號(hào)集合為 而Follow L 所以 只有在輸入符號(hào)為 時(shí) 用R L進(jìn)行歸約 而輸入符號(hào)為 時(shí) 移進(jìn) 可見用Follow集合來消除分析表的多重入口還是略嫌粗糙 LR 1 項(xiàng)目 由LR 0 項(xiàng)目和一個(gè)lookahead符號(hào)組成 A a LR 1 分析法的思想 用活前綴中與句柄相關(guān)的非終結(jié)符號(hào)A的后繼符號(hào) 亦稱為搜索符 集合 而不是Follow A 來避免分析表的多重入口 重新定義項(xiàng)目 使每個(gè)項(xiàng)目附帶一個(gè)向前搜索符 定義 LR 1 有效項(xiàng)目 LR 1 項(xiàng)目 A a a VT 對(duì)活前綴 是有效的 如果存在規(guī)范推導(dǎo)S Aw w且a First w 定理 若LR 1 項(xiàng)目 A B a 對(duì)活前綴 是有效的 且B 是一個(gè)產(chǎn)生式 則對(duì)任何b First a 項(xiàng)目 B b 也是活前綴 的有效項(xiàng)目 例 構(gòu)造文法G S 的LR 1 分析表 LR 1 項(xiàng)目集規(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 例 構(gòu)造文法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 圖 對(duì)于文法的轉(zhuǎn)移函數(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分析表的構(gòu)造 LR k 方法分析能力很強(qiáng) 但是也耗費(fèi)大量存儲(chǔ)空間 在實(shí)際應(yīng)用中 還須簡(jiǎn)化 觀察圖4 27可知 1 從自動(dòng)機(jī)狀態(tài)等價(jià)的角度來看 圖中彩色相同的狀態(tài)是等價(jià)的 這些等價(jià)狀態(tài)的特點(diǎn)是 它們的LR 0 有效項(xiàng)目集相同 由于判斷是否等價(jià)只須比較狀態(tài)的輸出弧 因而不難看出 LR 0 有效項(xiàng)目集相同的狀態(tài)必定等價(jià) 2 對(duì)于初始狀態(tài)I0 其中的有效項(xiàng)目均可從項(xiàng)目 S S 推導(dǎo)出來 對(duì)于非初始狀態(tài)I2 I3 I6 則其中 點(diǎn)在最左端 的項(xiàng)目均可由 點(diǎn)不在最左端 的項(xiàng)目推導(dǎo)出來 觀察圖也可以得到相同結(jié)果 因此在實(shí)際存儲(chǔ)狀態(tài)時(shí) 可以只存儲(chǔ) 點(diǎn)不在最左端 的項(xiàng)目 為了敘述方便 引入 同心項(xiàng) 和項(xiàng)目集的 核 的概念 定義 同心項(xiàng) 如果兩個(gè)LR 1 項(xiàng)目集去掉搜索符之后是相同的 則稱這兩個(gè)項(xiàng)目集具有相同的心 定義 核 對(duì)于初始狀態(tài)I0 有效項(xiàng)目 S S 稱為I0的核 而對(duì)于非初始狀態(tài) 則其中 點(diǎn)不在最左端 的有效項(xiàng)目稱為它的核 LALR分析法的基本思想 在LR 1 項(xiàng)目集規(guī)范族中 合并同心項(xiàng)以減少狀態(tài)的數(shù)目 在存儲(chǔ)LR 1 有效項(xiàng)目集時(shí) 僅存儲(chǔ)其中的核 注意 由于同心項(xiàng)的合并 使項(xiàng)目的搜索符與活前綴的對(duì)應(yīng)關(guān)系不唯一 降低了分析器的識(shí)別能力 參見以下兩例 C c C c d C cC c d C d c d I36 I0 Cc c C cC c d I89 C 活前綴Cc 與搜索符 對(duì)應(yīng) 而活前綴c 與搜索符c和d對(duì)應(yīng) 當(dāng)合并后的自動(dòng)機(jī)識(shí)別出活前綴CcC時(shí) 若當(dāng)前的輸入符號(hào)是c或d LR 1 分析器馬上就能發(fā)現(xiàn)出錯(cuò) 而LALR分析器此時(shí)則不行 必須先歸約 得到活前綴CC后才能發(fā)現(xiàn)出錯(cuò) 例 在圖中 I3和I6 I8和I9合并后得到如下部分狀態(tài)圖 問題 LALR分析器識(shí)別活前綴的能力是否比LR 1 的差 答 一樣 既然都是識(shí)別文法活前綴的自動(dòng)機(jī) 它們就是等價(jià)的 例 考慮文法GS SS aAd bBd aBe bAeA cB c構(gòu)造G的LR 1 項(xiàng)目集規(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 若將同心項(xiàng)I6和I9合并 則得到項(xiàng)目集I69 A c d eB c d e該項(xiàng)目集含 歸約 歸約 沖突 因此 文法G是LR 1 文法 但不是LALR文法 一 LALR 1 分析表的原理性構(gòu)造方法 構(gòu)造LR 1 項(xiàng)目集族 如果它不存在沖突 就把同心集合并在一起 若合并后不存在歸約 歸約沖突 則按這個(gè)集族構(gòu)造文法LALR 1 分析表 算法 LALR分析表的構(gòu)造輸入 拓廣文法G 輸出 對(duì)于G 的LALR 1 分析表方法 1 構(gòu)造文法的LR 1 項(xiàng)目集族C I0 I1 In 2 合并C中的同心集 得到C J0 J1 Jm 3 從C 出發(fā)構(gòu)造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分析表的有效構(gòu)造方法 前算法在構(gòu)造LALR分析表時(shí) 耗費(fèi)的存儲(chǔ)空間與LR 1 算法完全相同 代價(jià)還是太大 可以從兩個(gè)方面改進(jìn) 1 存儲(chǔ)有效項(xiàng)目集時(shí) 只存儲(chǔ)它們的核 每當(dāng)需要完整的有效項(xiàng)目集時(shí) 再根據(jù)核來計(jì)算 2 直接生成LALR項(xiàng)目集規(guī)范族的核 這是有效構(gòu)造方法的關(guān)鍵 注意 LALR項(xiàng)目的搜索符一般是與該項(xiàng)目相關(guān)的非終結(jié)符號(hào)的Follow集的子集 這正是LALR分析法比SLR分析法強(qiáng)的原因 直接生成LALR項(xiàng)目集規(guī)范族的核的方法如下 1 構(gòu)造LR 0 項(xiàng)目集規(guī)范族的核及其自動(dòng)機(jī) 2 為L(zhǎng)R 0 項(xiàng)目集規(guī)范簇中的每個(gè)核項(xiàng)目配上適當(dāng)?shù)乃阉鞣?核項(xiàng)目的搜索符無非有兩種產(chǎn)生途徑 若搜索符從其父核傳遞下來 則稱這樣的搜索符為 傳播的 否則 稱搜索符為 自生的 下面算法確定核項(xiàng)目的搜索符是自生的或者是傳播的 for有效項(xiàng)目集I的核K中的每一項(xiàng)目B dobeginJ closure B forJ中的每一個(gè)項(xiàng)目 A X a do如果a 則有效項(xiàng)目集go I X 中的核項(xiàng)目 A X a 中的搜索符是自生的 否則就是傳播的 練習(xí) 已知文法 請(qǐng)構(gòu)造LALR分析表 構(gòu)造文法的LALR 1 項(xiàng)目集的核 LR 0 項(xiàng)目集的核 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 計(jì)算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搜索符的計(jì)算 Thanks