編譯原理自底向上的語法分析.ppt

《編譯原理自底向上的語法分析.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理自底向上的語法分析.ppt（20頁珍藏版）》請在裝配圖網(wǎng)上搜索。

語法分析部分知識關(guān)系圖 開發(fā)語法分析程序 語法定義 基于 上下文無關(guān)文法 使用 實現(xiàn) 自頂向下 自底向上 第五章自底向上的語法分析 5 1自底向上的語法分析方法概述5 2LR 0 分析的有限自動機5 3LR 0 分析5 4SLR 1 分析5 5LR 1 分析5 6LALR 1 分析5 7LALR 1 語法分析器的自動生成器 YACC 5 1自底向上語法分析概述 自頂向下語法分析回顧自底向上語法分析的例子自底向上語法分析的主要思想自底向上語法分析的關(guān)鍵問題一些相關(guān)概念 自頂向下分析例 P 1 Z aBeA 2 A Bc 3 B d 4 B bB 5 B abec 自頂向下分析過程是從文法開始符出發(fā) 為所給輸入串構(gòu)造最左推導(dǎo)的過程 句型 輸入 動作 Z abec 推導(dǎo) 1 abec aBeA 匹配 a bec BeA 推導(dǎo) 4 bec bBeA 匹配 b ec BeA 推導(dǎo) 5 ec eA 匹配 e c A 推導(dǎo) 2 c Bc 推導(dǎo) 5 匹配 c c c 成功 自底向上語法分析的例子 P Z ABb 2 A a 3 A b 4 B b 5 B c 6 B bB abcb 輸入 符號棧 動作 abcb 移入 a bcb 歸約 2 A bcb 移入 Ab cb 移入 Abc b 歸約 5 AbB b 歸約 6 AB b 移入 歸約 1 ABb Z 成功 自底向上分析過程是從所給輸入串出發(fā) 對其進行最左歸約的過程 自底向上歸約的過程也是自底向上構(gòu)建語法樹的過程 abcb B B Z 歸約過程 Z rmABb rmAbBb rmAbcb rmabcb A abcb Abcb AbBb ABb Z 自底向上分析中歸約過程的逆過程就是該句子的最右推導(dǎo) 5 1自底向上語法分析方法概述 主要思想 從輸入串出發(fā) 盡可能地找到可歸約子串并將其歸約成一個非終極符 直到歸約成文法的開始符或發(fā)現(xiàn)語法錯誤 分析動作 移入 shift 歸約 reduce 包含以下方法 LR類的方法 簡單優(yōu)先法 算符優(yōu)先法關(guān)鍵問題 什么時候進行歸約 按照哪條產(chǎn)生式進行歸約 一些相關(guān)概念 短語一個句型形如 如果存在一個句型 A 而且A 則稱 為句型 的短語 例如句型AbBb 則bB AbBb是它的短語 因為存在句型ABb ABb AbBb A b 存在句型Z Z ABb AbBb 簡單短語一個句型形如 如果存在一個句型 A 而且A 則稱 為句型 的簡單短語 例如句型AbBb bB是它的簡單短語 AbBb不是它的簡單短語 1 Z ABb 2 A a 3 A b 4 B d 5 B c 6 B bB 一些相關(guān)概念 句柄 一個句型的簡單短語可能有多個 稱最左簡單短語為句柄 handler 例如 句型abBb 簡單短語有兩個 a bBZ ABb aBb abBb最左簡單短語a是句柄句柄的唯一性 如果一個CFG無二義性 則它的任意一個句型都有唯一的句柄 短語 簡單短語 句柄的例子 P 1 E T 2 E E T 3 T F 4 T T F 5 F E 6 F i 7 F n 句型 T E T i 簡單短語 T E T i 句柄 T 通過為所給句型建立語法分析樹 可以很容易地識別出該句型的所有短語 簡單短語和句柄 句型的一個推導(dǎo) 該句型沒有最右推導(dǎo) E E T E T F E T i E F i E E i E E T i T E T i 短語 T E T i T E T i E T E T i 由語法分析樹識別短語 簡單短語和句柄 E E T T T F F E E T i 語法分析樹的葉子節(jié)點構(gòu)成句型 T E T i 每棵子樹的葉子節(jié)點構(gòu)成短語 T E T i T E T i E T E T i 每棵簡單子樹 只有一層的子樹 的葉子節(jié)點構(gòu)成簡單短語 T E T i 最左簡單子樹的葉子節(jié)點構(gòu)成句柄 T 一些相關(guān)概念 自頂向下的語法分析方法中曾介紹過 推導(dǎo) 對句型中的非終極符用產(chǎn)生式右部替換規(guī)范推導(dǎo) 一個句型的最右推導(dǎo)稱為該句型的規(guī)范推導(dǎo) 規(guī)范句型 右句型 從開始符通過規(guī)范推導(dǎo)得到的句型 推導(dǎo)的逆過程稱為歸約 規(guī)范推導(dǎo)的逆過程稱為規(guī)范歸約 最左歸約 規(guī)范歸約過程中產(chǎn)生的句型仍是規(guī)范句型 規(guī)范歸約的過程也是對規(guī)范句型的最左簡單短語 句柄 進行歸約的過程 一些相關(guān)概念 Z ABb規(guī)范前綴為AB ABdZ Acb規(guī)范前綴為A Ac Acb 規(guī)范前綴 一個規(guī)范句型的一個前綴稱為規(guī)范前綴 如果該前綴后面的符號串不包含非終極符 規(guī)范句型 規(guī)范前綴 或者終極符串 一些相關(guān)概念 Z ABb規(guī)范前綴為AB ABb規(guī)范活前綴 AB 不包含簡單短語 ABb 包含一個簡單短語且在最后 規(guī)范活前綴 滿足如下條件之一的規(guī)范前綴稱為規(guī)范活前綴 該規(guī)范前綴不包含簡單短語 該規(guī)范前綴只包含一個簡單短語 而且是在該規(guī)范前綴的最后 這個簡單短語就是句柄 Z abcb規(guī)范前綴為a ab abc abcb規(guī)范活前綴 a 包含一個簡單短語且在最后 abc是不是規(guī)范活前綴 不是 包含兩個簡單短語a和c 自底向上語法分析的例子 P Z ABb 2 A a 3 A b 4 B b 5 B c 6 B bB abcb 輸入 符號棧 動作 abcb 移入 a bcb 歸約 2 A bcb 移入 Ab cb 移入 Abc b 歸約 5 AbB b 歸約 6 AB b 移入 歸約 1 ABb Z 成功 自底向上分析過程是從所給輸入串出發(fā) 對其進行最左歸約的過程 規(guī)范活前綴 或者終極符串 規(guī)范句型 一些相關(guān)概念 規(guī)范活前綴決定分析動作移入 規(guī)范活前綴不包含簡單短語 移入型規(guī)范活前綴歸約 規(guī)范活前綴只包含一個簡單短語 而且是在該規(guī)范活前綴的最后 可歸約規(guī)范活前綴 歸約規(guī)范活前綴 Z ABb規(guī)范前綴為AB ABb規(guī)范活前綴 AB 不包含簡單短語 移入型規(guī)范活前綴ABb 包含一個簡單短語 歸約規(guī)范活前綴 自底向上分析知識關(guān)系圖 規(guī)范歸約 推導(dǎo) 最右推導(dǎo) 句型 S 短語 A 簡單短語 A 句柄 最左 規(guī)范推導(dǎo) 規(guī)范句型 S rm 特例 特例 規(guī)范前綴 規(guī)范活前綴 包含0或1個 歸約規(guī)范活前綴 應(yīng)用 互逆 最右包含1個 自底向上分析 5 1自底向上語法分析方法概述 LR方法主要思想L表示從左至右讀入輸入串 R表示構(gòu)造一個最右推導(dǎo)的逆過程 即每次找到句柄 歸約規(guī)范活前綴 來進行歸約 歸約直到得到開始符或報告語法錯誤 關(guān)鍵問題 對于一個CFG 如何判定歸約規(guī)范活前綴 構(gòu)造一個判定歸約規(guī)范活前綴的自動機 LR自動機由LR自動機構(gòu)造LR分析表指導(dǎo)LR分析 LR分析機制 分析棧 輸入 a LR驅(qū)動程序 shift 移入 移入型規(guī)范活前綴 reduce 歸約 可歸約規(guī)范活前綴 LR分析表 規(guī)范活前綴 5 1自底向上語法分析方法概述 LR方法不同的LR方法LR 0 SLR 1 LR 1 LALR 1 不同的LR方法對CFG的要求不一樣 能夠分析的CFG多少也不一樣 LR 0 SLR 1 LALR 1 LR 1