編譯原理自上而下語法分析.ppt

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

第四章自上向下語法分析 語法分析的任務(wù)本章要點(diǎn) 自上而下語法分析的思想LL 1 方法遞歸下降分析預(yù)測分析 基本思想 主旨對任何輸入串 試圖用一切可能 從文法的開始符號出發(fā) 自上而下地為輸入串建立一棵語法樹 或者為輸入串尋找一個最左推導(dǎo) 本質(zhì)上是一種試探過程 要解決的基本問題 例 G S S xAyA 考慮輸入串x y對于特定的非終結(jié)符號 使用哪個產(chǎn)生式來替換 帶回溯的自上而下語法分析存在的困難和缺點(diǎn) 文法的遞歸性虛假匹配錯誤的位置難以確定效率低 代價(jià)高 無回溯的自上向下分析技術(shù) 先決條件 無左遞歸既沒有直接左遞歸 也沒有間接左遞歸 無回溯性對于任一非終結(jié)符號U的產(chǎn)生式右部x1 x2 xn 各xi的首終結(jié)符號兩兩不相交 文法的左遞歸性 定義 文法的左遞歸性是指文法具有以下形式的直接左遞歸 U Ux y或間接左遞歸 U Ux 具有左遞歸性的文法舉例 E E T TT T F FF E i 消除文法的直接左遞歸 P P 1 P n 1 m改寫為 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 消除文法的左遞歸 前提 如果一個文法不含回路 形如P P的推導(dǎo) 也不含以 為右部的產(chǎn)生式 那么可以通過執(zhí)行消除文法左遞歸的算法消除文法的一切左遞歸 改寫后的文法可能含有以 為右部的產(chǎn)生式 消除文法的一切左遞歸的算法 1 把文法的所有非終結(jié)符按任一順序排序2 FORi 1TOnDO 1 FORj 1TOi 1DO把形如Pi Pj 的規(guī)則改寫成Pi 1 k 其中Pj 1 k是關(guān)于Pj的所有規(guī)則 2 消除關(guān)于規(guī)則的直接左遞歸3 化簡由2所得的文法 例子 A BcdB Ce fC Ab c 消除回溯的基本思想 必須保證對文法的任何非終結(jié)符 當(dāng)要它去匹配輸入串時 能夠根據(jù)它所面臨的輸入符號 指派它的一個候選 右部 去執(zhí)行任務(wù) 并且此候選的工作結(jié)果應(yīng)是確定無疑的 即要么匹配成功 要么不可能獲得匹配 消除回溯對文法的要求 1 首先 文法不得含有左遞歸 2 設(shè)文法G不含左遞歸 對G的所有非終結(jié)符的每個候選 定義其終結(jié)首符集FIRST 為FIRST a a a VT 特別是 若 則規(guī)定 FIRST 如果非終結(jié)符A的所有候選首符集兩兩不相交 那么 當(dāng)要求A匹配輸入串時 A就能根據(jù)它所面臨的第一個輸入符號a 準(zhǔn)確地指派某一個候選去執(zhí)行任務(wù) 這個候選就是那個終結(jié)首符集含a的 消除回溯方法 提取公共左因子 假設(shè)關(guān)于A的產(chǎn)生式是A 1 2 n n 1那么 可以將其改寫為A A n 1A 1 2 n經(jīng)過反復(fù)提取左因子 就能夠把每個非終結(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的任一個非終結(jié)符 其產(chǎn)生式為U x1 x2 xn如果FIRST xi FIRST xj i j i j 1 2 n 當(dāng) FIRST xi 時 有FIRST xi FOLLOW U 則文法G為LL 1 文法 LL 1 方法 基本思想 從S出發(fā) 生成句子的最左推導(dǎo) 選擇合適產(chǎn)生式 從左到右掃描源程序 每次通過向前查看1個字符 選擇合適的產(chǎn)生式 適用范圍 僅對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對應(yīng)的字的所有可能的首終結(jié)符號 FOLLOW U 表示了句型中可能緊跟再U后面的終結(jié)符號 FIRST 構(gòu)造算法 對于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)]有哪個非終結(jié)符號的FOLLOW集合增長為止 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)思想 識別程序由一組子程序組成 每個子程序?qū)?yīng)于一個非終結(jié)符號 每一個子程序的功能是 選擇正確的右部 掃描完相應(yīng)的字 在右部中有非終結(jié)符號時 調(diào)用該非終結(jié)符號對應(yīng)的子程序來完成 基本架構(gòu) 1 變量 sym 當(dāng)前符號函數(shù) advance 讀輸入串下一符號對于每個非終結(jié)符號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 對于無回溯的文法保證選擇是唯一的 基本架構(gòu) 2 對于每個右部 x1x2 xn的處理架構(gòu)如下 P P x1 處理x1的程序P x2 處理x2的程序 P xn 處理xn的程序 說明 如果右部為空 則不處理 基本架構(gòu) 3 對于右部中的每個符號xi如果xi為終結(jié)符號 if sym a sym 下一輸入符號 對于終結(jié)符 直接將指針前調(diào)elseerror如果xi為非終結(jié)符號 直接調(diào)用相應(yīng)的過程 P xi 擴(kuò)展的BNF表示法 花括號 x 表示符號串x出現(xiàn)0次或多次 即x x nm m表示符號串x能出現(xiàn)的最大次數(shù) n表示符號串x能出現(xiàn)的最小次數(shù)方括號 表示 x 01 圓括號 利用圓括號可以提出非終結(jié)符的多個產(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)識符產(chǎn)生式含有左遞歸 可以改寫為 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ù)測分析程序的結(jié)構(gòu) 使用一個二維分析表和棧聯(lián)合進(jìn)行控制來實(shí)現(xiàn)語法分析 總控程序大同小異 而LL 1 分析表卻千差萬別 LL 1 分析表是進(jìn)行LL 1 分析的核心 輸入符號串 分析棧 LL 1 總控程序 分析表 輸出流 預(yù)測分析表的結(jié)構(gòu) 分析表實(shí)際上是一個從VN VT 到產(chǎn)生式的映射 通常以矩陣表示 其元素M U a 中可能存放一條非終結(jié)符U的產(chǎn)生式 說明當(dāng)符號棧S的棧頂元素非終結(jié)符U遇到當(dāng)前輸入字符a時 所應(yīng)選擇的產(chǎn)生式 元素M U a 也可存放一個出錯標(biāo)志 說明符號棧S的棧頂元素非終結(jié)符U不應(yīng)遇到當(dāng)前輸入符號a 預(yù)測分析器的總控原理 在任何時候 總控程序都是按照棧頂符號X和當(dāng)前輸入符號a工作的 對于任何 X a 總控程序每次都執(zhí)行下述三種可能的動作之一 1 若X a 則宣布分析成功 停止分析過程 2 若X a 則把X從棧頂逐出 讓a指向下一輸入符號 3 若X是一個非終結(jié)符 則查看分析表M 若M中存放著一條關(guān)于X的產(chǎn)生式 那么 首先把X逐出棧頂 然后 把產(chǎn)生式的右部符號按反序一一推進(jìn)棧 同時做這個產(chǎn)生式相應(yīng)的語義動作 目前不管 若M X a 中存放著一條出錯標(biāo)志 則調(diào)用出錯診查程序Error 例子 文法G E E TE E TE T FT T FT F E i 例子 預(yù)測分析表的生成 從前面的論述我們看到 預(yù)測分析法的總控程序是固定的 對于某個文法 分析表是分析過程的核心 表中M U a U X1X2 Xn 表示對應(yīng)于X1X2 Xn字的首符號可以是a 就是說X1X2 Xn a 我們可以通過這個方式來確定分析表中的值 預(yù)測分析表的生成 一般來講 對于一個符號串X1X2 Xn的字的第一個終結(jié)符號就是X1對應(yīng)的字的第一個終結(jié)符號 但是空產(chǎn)生式的存在使情況有一點(diǎn)復(fù)雜 對于U1U2 Un 如果U1 那么符號串對應(yīng)的字的首符號也可以是U2對應(yīng)的字的首符號 計(jì)算一個符號串對應(yīng)的字的首符號的算法也需要考慮到這些 預(yù)測分析表的構(gòu)造 基本思想 當(dāng)我們需要將U選擇某個產(chǎn)生式展開時 如果當(dāng)前的輸入為a 表示我們要將U展開為以a為首符號的字 如果有產(chǎn)生式U u 且a FIRST u 那么表示這個產(chǎn)生式是個好的選擇 分析表構(gòu)造算法 對于每個產(chǎn)生式U 執(zhí)行一下步驟對于每個終結(jié)符號a FIRST M U a U 如果 FIRST 對于每個終結(jié)符號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ù)測分析表中沒有多重定義的元素 則該文法被稱為LL 1 文法 LL 1 文法是無二義性的