編譯原理自上而下語(yǔ)法分析.ppt
《編譯原理自上而下語(yǔ)法分析.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《編譯原理自上而下語(yǔ)法分析.ppt(48頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第四章自上向下語(yǔ)法分析 語(yǔ)法分析的任務(wù)本章要點(diǎn) 自上而下語(yǔ)法分析的思想LL 1 方法遞歸下降分析預(yù)測(cè)分析 基本思想 主旨對(duì)任何輸入串 試圖用一切可能 從文法的開(kāi)始符號(hào)出發(fā) 自上而下地為輸入串建立一棵語(yǔ)法樹(shù) 或者為輸入串尋找一個(gè)最左推導(dǎo) 本質(zhì)上是一種試探過(guò)程 要解決的基本問(wèn)題 例 G S S xAyA 考慮輸入串x y對(duì)于特定的非終結(jié)符號(hào) 使用哪個(gè)產(chǎn)生式來(lái)替換 帶回溯的自上而下語(yǔ)法分析存在的困難和缺點(diǎn) 文法的遞歸性虛假匹配錯(cuò)誤的位置難以確定效率低 代價(jià)高 無(wú)回溯的自上向下分析技術(shù) 先決條件 無(wú)左遞歸既沒(méi)有直接左遞歸 也沒(méi)有間接左遞歸 無(wú)回溯性對(duì)于任一非終結(jié)符號(hào)U的產(chǎn)生式右部x1 x2 xn 各xi的首終結(jié)符號(hào)兩兩不相交 文法的左遞歸性 定義 文法的左遞歸性是指文法具有以下形式的直接左遞歸 U Ux y或間接左遞歸 U Ux 具有左遞歸性的文法舉例 E E T TT T F FF E i 消除文法的直接左遞歸 P P 1 P n 1 m改寫(xiě)為 P 1P mP P 1P nP 例子 消除左遞歸前E E T TT T F FF E i 消除左遞歸后E TE E TE T FT T FT F E i 間接左遞歸舉例 S Qc cQ Rb bR Sa a以上文法不含直接左遞歸 但S Q R都是左遞歸的 因?yàn)?S Qc Rbc SabcQ Rb Sab QabcR Sa Qca Rbca 消除文法的左遞歸 前提 如果一個(gè)文法不含回路 形如P P的推導(dǎo) 也不含以 為右部的產(chǎn)生式 那么可以通過(guò)執(zhí)行消除文法左遞歸的算法消除文法的一切左遞歸 改寫(xiě)后的文法可能含有以 為右部的產(chǎn)生式 消除文法的一切左遞歸的算法 1 把文法的所有非終結(jié)符按任一順序排序2 FORi 1TOnDO 1 FORj 1TOi 1DO把形如Pi Pj 的規(guī)則改寫(xiě)成Pi 1 k 其中Pj 1 k是關(guān)于Pj的所有規(guī)則 2 消除關(guān)于規(guī)則的直接左遞歸3 化簡(jiǎn)由2所得的文法 例子 A BcdB Ce fC Ab c 消除回溯的基本思想 必須保證對(duì)文法的任何非終結(jié)符 當(dāng)要它去匹配輸入串時(shí) 能夠根據(jù)它所面臨的輸入符號(hào) 指派它的一個(gè)候選 右部 去執(zhí)行任務(wù) 并且此候選的工作結(jié)果應(yīng)是確定無(wú)疑的 即要么匹配成功 要么不可能獲得匹配 消除回溯對(duì)文法的要求 1 首先 文法不得含有左遞歸 2 設(shè)文法G不含左遞歸 對(duì)G的所有非終結(jié)符的每個(gè)候選 定義其終結(jié)首符集FIRST 為FIRST a a a VT 特別是 若 則規(guī)定 FIRST 如果非終結(jié)符A的所有候選首符集兩兩不相交 那么 當(dāng)要求A匹配輸入串時(shí) A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a 準(zhǔn)確地指派某一個(gè)候選去執(zhí)行任務(wù) 這個(gè)候選就是那個(gè)終結(jié)首符集含a的 消除回溯方法 提取公共左因子 假設(shè)關(guān)于A的產(chǎn)生式是A 1 2 n n 1那么 可以將其改寫(xiě)為A A n 1A 1 2 n經(jīng)過(guò)反復(fù)提取左因子 就能夠把每個(gè)非終結(jié)符 包括新引進(jìn)者 的多有候選首符集變成為兩兩不相交 代價(jià) 引入大量新的非終結(jié)符和空產(chǎn)生式 G S S BxB x 考慮輸入串xFOLLOW U b S xUby b VT x y VN VT 特別地 FOLLOW S LL 1 分析條件 文法不含左遞歸設(shè)U是文法G的任一個(gè)非終結(jié)符 其產(chǎn)生式為U x1 x2 xn如果FIRST xi FIRST xj i j i j 1 2 n 當(dāng) FIRST xi 時(shí) 有FIRST xi FOLLOW U 則文法G為L(zhǎng)L 1 文法 LL 1 方法 基本思想 從S出發(fā) 生成句子的最左推導(dǎo) 選擇合適產(chǎn)生式 從左到右掃描源程序 每次通過(guò)向前查看1個(gè)字符 選擇合適的產(chǎn)生式 適用范圍 僅對(duì)LL 1 文法適用 FIRST 和FOLLOW U 定義 1 FIRST a a a VT VN VT 特別地 如果 那么 我們規(guī)定 FIRST 2 FOLLOW U b S xUby b VT x y VN VT 特別地 FOLLOW S 直觀地講 FIRST u 包含了u對(duì)應(yīng)的字的所有可能的首終結(jié)符號(hào) FOLLOW U 表示了句型中可能緊跟再U后面的終結(jié)符號(hào) FIRST 構(gòu)造算法 對(duì)于X VN VT FIRST X 的構(gòu)造1 若X VT 則FIRST X X 2 若X VN 且有產(chǎn)生式X a a VT 則a FIRST X 如果X 那么 FIRST X 3 若有產(chǎn)生式X Y Y VN 則FIRST Y FIRST X 如果有產(chǎn)生式X Y1Y2 YK 其中Y1 Y2 Yi 1 VN且Y1Y2 Yi 1 則FIRST Yi FIRST X 若Y1Y2 YK 則 FIRST X FIRST 構(gòu)造算法 續(xù) 設(shè) VN VT X1X2 Xn FIRST 的構(gòu)造1 若 則FIRST 2 若 則FIRST X1 FIRST 3 若X1X2 Xi 1 則FIRST Xi FIRST 若X1X2 Xn 則 FIRST FOLLOW U 的構(gòu)造算法 1 FOLLOW S 2 如果有產(chǎn)生式A xUy 那么FIRST y FOLLOW U 3 如果有產(chǎn)生式A xU或則A xUy且y 那么FOLLOW A FOLLOW U 注意 步驟3需要重復(fù)執(zhí)行 直到?jīng)]有哪個(gè)非終結(jié)符號(hào)的FOLLOW集合增長(zhǎng)為止 FIRST的例子 文法G E E TE E TE T FT T FT F E iFIRST F i FIRST T FIRST F i FIRST E FIRST T FOLLOW例子 文法G E E TE E TE T FT T FT F E iFOLLOW E FOLLOW E FOLLOW E FOLLOW T FIRST E FOLLOW E FOLLOW T FOLLOW T FOLLOW F FIRST T FOLLOW T 例子 求FIRST集與FOLLOW舉例 文法G A A BB X B B AB X aX bX X aX bX 遞歸下降分析程序 實(shí)現(xiàn)思想 實(shí)現(xiàn)思想 識(shí)別程序由一組子程序組成 每個(gè)子程序?qū)?yīng)于一個(gè)非終結(jié)符號(hào) 每一個(gè)子程序的功能是 選擇正確的右部 掃描完相應(yīng)的字 在右部中有非終結(jié)符號(hào)時(shí) 調(diào)用該非終結(jié)符號(hào)對(duì)應(yīng)的子程序來(lái)完成 基本架構(gòu) 1 變量 sym 當(dāng)前符號(hào)函數(shù) advance 讀輸入串下一符號(hào)對(duì)于每個(gè)非終結(jié)符號(hào)U 1 2 n處理的方法如下 P U ifsym FIRST 1 thenP 1 處理 1的程序部分elseifsym FIRST 2 thenP 2 處理 2的程序部分 elseifsym FIRST n thenP n elseifsym FOLLOW U thenreturn 處理空產(chǎn)生式情況elseerror 對(duì)于無(wú)回溯的文法保證選擇是唯一的 基本架構(gòu) 2 對(duì)于每個(gè)右部 x1x2 xn的處理架構(gòu)如下 P P x1 處理x1的程序P x2 處理x2的程序 P xn 處理xn的程序 說(shuō)明 如果右部為空 則不處理 基本架構(gòu) 3 對(duì)于右部中的每個(gè)符號(hào)xi如果xi為終結(jié)符號(hào) if sym a sym 下一輸入符號(hào) 對(duì)于終結(jié)符 直接將指針前調(diào)elseerror如果xi為非終結(jié)符號(hào) 直接調(diào)用相應(yīng)的過(guò)程 P xi 擴(kuò)展的BNF表示法 花括號(hào) x 表示符號(hào)串x出現(xiàn)0次或多次 即x x nm m表示符號(hào)串x能出現(xiàn)的最大次數(shù) n表示符號(hào)串x能出現(xiàn)的最小次數(shù)方括號(hào) 表示 x 01 圓括號(hào) 利用圓括號(hào)可以提出非終結(jié)符的多個(gè)產(chǎn)生式右部的公共因子 E E T E T T可改成E T T T T T F T F F可改成T F F F 用擴(kuò)展的BNF表示法消除左遞歸 例子 以上標(biāo)識(shí)符產(chǎn)生式含有左遞歸 可以改寫(xiě)為 Z U aUb E T E T E TE T T T T F T F T FT F F F 有文法G Z Z AcB BdA AaB cB aA a設(shè)計(jì)遞歸下降分析程序 思考題 預(yù)測(cè)分析程序的結(jié)構(gòu) 使用一個(gè)二維分析表和棧聯(lián)合進(jìn)行控制來(lái)實(shí)現(xiàn)語(yǔ)法分析 總控程序大同小異 而LL 1 分析表卻千差萬(wàn)別 LL 1 分析表是進(jìn)行LL 1 分析的核心 輸入符號(hào)串 分析棧 LL 1 總控程序 分析表 輸出流 預(yù)測(cè)分析表的結(jié)構(gòu) 分析表實(shí)際上是一個(gè)從VN VT 到產(chǎn)生式的映射 通常以矩陣表示 其元素M U a 中可能存放一條非終結(jié)符U的產(chǎn)生式 說(shuō)明當(dāng)符號(hào)棧S的棧頂元素非終結(jié)符U遇到當(dāng)前輸入字符a時(shí) 所應(yīng)選擇的產(chǎn)生式 元素M U a 也可存放一個(gè)出錯(cuò)標(biāo)志 說(shuō)明符號(hào)棧S的棧頂元素非終結(jié)符U不應(yīng)遇到當(dāng)前輸入符號(hào)a 預(yù)測(cè)分析器的總控原理 在任何時(shí)候 總控程序都是按照棧頂符號(hào)X和當(dāng)前輸入符號(hào)a工作的 對(duì)于任何 X a 總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一 1 若X a 則宣布分析成功 停止分析過(guò)程 2 若X a 則把X從棧頂逐出 讓a指向下一輸入符號(hào) 3 若X是一個(gè)非終結(jié)符 則查看分析表M 若M中存放著一條關(guān)于X的產(chǎn)生式 那么 首先把X逐出棧頂 然后 把產(chǎn)生式的右部符號(hào)按反序一一推進(jìn)棧 同時(shí)做這個(gè)產(chǎn)生式相應(yīng)的語(yǔ)義動(dòng)作 目前不管 若M X a 中存放著一條出錯(cuò)標(biāo)志 則調(diào)用出錯(cuò)診查程序Error 例子 文法G E E TE E TE T FT T FT F E i 例子 預(yù)測(cè)分析表的生成 從前面的論述我們看到 預(yù)測(cè)分析法的總控程序是固定的 對(duì)于某個(gè)文法 分析表是分析過(guò)程的核心 表中M U a U X1X2 Xn 表示對(duì)應(yīng)于X1X2 Xn字的首符號(hào)可以是a 就是說(shuō)X1X2 Xn a 我們可以通過(guò)這個(gè)方式來(lái)確定分析表中的值 預(yù)測(cè)分析表的生成 一般來(lái)講 對(duì)于一個(gè)符號(hào)串X1X2 Xn的字的第一個(gè)終結(jié)符號(hào)就是X1對(duì)應(yīng)的字的第一個(gè)終結(jié)符號(hào) 但是空產(chǎn)生式的存在使情況有一點(diǎn)復(fù)雜 對(duì)于U1U2 Un 如果U1 那么符號(hào)串對(duì)應(yīng)的字的首符號(hào)也可以是U2對(duì)應(yīng)的字的首符號(hào) 計(jì)算一個(gè)符號(hào)串對(duì)應(yīng)的字的首符號(hào)的算法也需要考慮到這些 預(yù)測(cè)分析表的構(gòu)造 基本思想 當(dāng)我們需要將U選擇某個(gè)產(chǎn)生式展開(kāi)時(shí) 如果當(dāng)前的輸入為a 表示我們要將U展開(kāi)為以a為首符號(hào)的字 如果有產(chǎn)生式U u 且a FIRST u 那么表示這個(gè)產(chǎn)生式是個(gè)好的選擇 分析表構(gòu)造算法 對(duì)于每個(gè)產(chǎn)生式U 執(zhí)行一下步驟對(duì)于每個(gè)終結(jié)符號(hào)a FIRST M U a U 如果 FIRST 對(duì)于每個(gè)終結(jié)符號(hào)b FOLLOW U M U b U 將其它未定義的分析表元素置為ERROR 分析表的例子 文法G E E TE E TE T FT T FT F E i 分析表的沖突 文法G S S iCtSS aS eS C bFIRST iCtSS i FIRST eS e FIRST S i a FIRST C b FIRST S e FOLLOW S FOLLOW S e LL 1 文法 LL 1 文法 其預(yù)測(cè)分析表中沒(méi)有多重定義的元素 則該文法被稱為L(zhǎng)L 1 文法 LL 1 文法是無(wú)二義性的- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 編譯 原理 自上而下 語(yǔ)法分析
鏈接地址:http://www.hcyjhs8.com/p-7284219.html