編譯原理自底向上的語(yǔ)法分析.ppt

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

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