編譯原理第四章語法分析-自上而下分析.ppt

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

第四章語法分析 自上而下分析 4 1語法分析器的功能4 2自上而下分析面臨的問題4 3LL 1 分析法4 4遞歸下降分析程序構(gòu)造4 5預(yù)測分析程序4 6LL 1 分析中的錯誤處理 4 1語法分析器的功能 功能定義 按照文法產(chǎn)生式 識別輸入符號串是否為一個句子 技術(shù)路線 是否能從文法的開始符號出發(fā)推導(dǎo)出這個輸入串 或者 建立一顆與輸入串相匹配的語法分析樹 策略 自上而下分析法 自下而上分析法 圖4 1語法分析器在編譯程序中的地位 接收詞法分析器輸出的記號串 檢查是否合乎語法 報告語法錯誤 并恢復(fù)語法錯誤 從而可以繼續(xù)分析 輸出是分析樹的某種形式 分析時其它任務(wù) 將各種記號的信息收入符號表 類型檢查和其它語義檢查 中間代碼的生成 這些放在 前端的其它部分 完成 4 2自上而下分析面臨的問題 例4 1假定有文法 1 S xAy 2 A 對輸入串x y 構(gòu)造語法樹 構(gòu)造過程 1 把S作為根 2 用S的產(chǎn)生式構(gòu)造子樹 3 讓輸入串指示器IP指向輸入串的第一個符號 4 調(diào)整輸入串指示器IP與葉結(jié)點進(jìn)行匹配 5 如果為非終結(jié)符 用A的下一個產(chǎn)生式構(gòu)建子樹 6 如果匹配成功則結(jié)束 否則 回溯到步驟 4 自上而下分析法的缺點 是文法的左遞歸性問題 一個文法是含有左遞歸的自上而下的分析過程陷入無限循環(huán) 如P P 由于有回溯 就會產(chǎn)生一大堆麻煩事情 在上述的自上而下分析過程中 當(dāng)一個非終結(jié)符用某一候選匹配成功時 這種成功可能僅是暫時的 這種虛假現(xiàn)象 我們需要更復(fù)雜的回溯技術(shù) 一般說 要消除虛假匹配是很困難的 當(dāng)最終報告分析不成功時 我們不知道輸入串中出錯的確切位置 4 3LL 1 分析法 4 3 1左遞歸的消除4 3 2消除回溯 提左因子4 3 3LL 1 分析條件 4 3 1左遞歸的消除 一個簡單例子 已知文法 P P 是一個左遞歸文法 它的等價的非左遞歸文法為 P P P P 例2 2一般轉(zhuǎn)換規(guī)則有 P P 1 P 2 P m 1 2 n改寫成P 1P 2P nP P 1P 2P mP 其中 i都不以P開頭 I不等于 一個反例 文法 S Qc c Q Rb b R Sa a雖然不是直接左遞歸 但S Q R都是左遞歸 消除左遞歸算法 算法的思想是 首先構(gòu)造直接左遞歸 再利用一般轉(zhuǎn)換規(guī)則 消除直接左遞歸化簡文法 下面算法在不含P P 也不含 在右部產(chǎn)生式時可以消除左遞歸 消除一個文法的左遞歸算法 1 把文法G的所有非終結(jié)符按任一種順利排列成P1 Pn 按此順序執(zhí)行 2 FORi 1TOnDOBEGINFORj 1TOi 1DO把形如Pj 1 Pj 的規(guī)則改寫成Pj 1 1 1 k 其中Pj 1 1 k是關(guān)于Pj的所有規(guī)則 消除關(guān)于Pi規(guī)則的直接左遞歸性 END化簡由 所得的文法 即去除那些從開始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則 例子4 3 對4 3文法 它的非終結(jié)符排序為R Q S 把R代入Q Q代入S得到 S Sabc abc bc c消除左遞歸后得到 S abcS bcS cS S abcS Q Sab ab b 化簡消去 R Sa a 化簡后消去 對不同的排列 會有不同形式的無左遞歸文法 但它們等價 4 3 2消除回溯 提左因子 消除回溯的思路 對輸入符號a 指派一個A的候選式 1與a匹配 而再沒有其他候選式 i的字符與a匹配 通過提取公共左因子 判斷首字符集的差異 首字符集定義 對G的所有非終結(jié)符的每個候選 它的首字符集為FIRST a a a VT 若 則規(guī)定 FIRST 提取公共左因子算法 A 1 2 n 1 2 m 其中每個 不以 開頭 那么可以把這些規(guī)則改寫成 A A 1 2 mA 1 2 n例4 4上述算法的不足 當(dāng)非終結(jié)符A面臨輸入符號a 且a不屬于A的任意候選首符集 但A的某個候選首符集包 含時 就一定可以使A自動匹配 這是一種錯誤 4 3 3LL 1 分析條件 定義FOLLOW A 集合 假定S是文法G的開始符號 對于G的任何非終結(jié)符A 我們定義FOLLOW A a S Aa a VT 若S A 則規(guī)定 FOLLOW A LL 1 文法的充分必要條件 文法不含左遞歸 若 1 2 n 則FIRST i FIRST j i j 對文法中的每個非終結(jié)符A 若它存在某個候選首符集包含 則FIRST A FOLLOW A LL 1 匹配算法 對輸入符號a A的所有產(chǎn)生式為 1 2 n 1 若a FIRST i 則指派 I去執(zhí)行匹配任務(wù) 2 若a不屬于任何一個候選首符集 則 FIRST i 且a FOLLOW A 則讓A i 與 a 自動匹配 否則 a的出現(xiàn)是一種語法錯誤 例4 4 4 4遞歸下降分析程序構(gòu)造 遞歸下降分析器 這個分析程序由一組遞歸過程組成的 每個過程對應(yīng)文法的一個非終結(jié)符 E TE E TE T FT T FT F E i PROCEDUREEPROCEDURETBEGINBEGINT E F T ENDENDPROCEDUREE PROCEDURET IFSYM THENIFSYM THENBEGINBEGINADVANCE ADVANCE T E F T ENDEND PROCEDUREFIFSYM i THENADVANCEELSEIFSYM THENBEGINADVANCE E IFSYM THENADVANCEELSEERRORENDELSEERROR 擴展巴科斯范式 BackusNaurForm 用花括號 表示閉包運算 用 n0表示 可任意重復(fù) 次至n次 00 0 用方括號 表示 0 即表示 的出現(xiàn)可有可無 等價于 例4 5 文法E T E TT F T FF i E 可表示成E T T F F F F E I 4 5預(yù)測分析程序 4 5 1預(yù)測分析程序工作過程4 5 2預(yù)測分析表的構(gòu)造 預(yù)測分析器思想 棧 表4 1文法4 2的LL 1 分析表 預(yù)測分析程序的總控程序 其具體工作過程是首先把文法開始符號和 壓入棧 然后總控程序在任何時候都是按STACK棧頂符號X和當(dāng)前輸入符號a行事的 如圖所示 對于任何 X a 總控程序每次都執(zhí)行下述三種可能的動作之一 若X a 則宣布分析成功 停止分析過程 若X a 則把X從STACK棧頂逐出 讓a 指示器 指向下一個輸入符號 若X是一個非終結(jié)符 則查看分析表M 若M A a 中存放著關(guān)于X的一個產(chǎn)生式 則X出棧 把X產(chǎn)生式右部符號串按反序壓棧 如果M A a 中存放出錯標(biāo)志 則調(diào)用診斷程序 預(yù)測分析程序的總控程序描述是 BEGIN首先把 然后把文法開始符號推進(jìn)STACK棧 把第一個輸入符號讀進(jìn)a FLAG TRUE WHILEFLAGDOBEGIN把STACK棧頂符號上托出并放在X中 IFX VTTHENIFX aTHEN把下一輸入符號讀進(jìn)aELSEERRORELSEIFX THENIFX aTHENFLAG FALSEELSEERROR ELSEIFM A a X X1X2 Xk THEN把Xk Xk 1 X1一一推進(jìn)STACK棧 若X1X2 Xk 不推任何字進(jìn)棧 ELSEERRORENDOFWHILE STOP 分析成功 過程完畢 END 例4 6 輸入串為i1 i2 i3 利用分析表進(jìn)行預(yù)測分析的步驟步驟符號棧輸入串所用產(chǎn)生式0 Ei1 i2 i3 1 E Ti1 i2 i3 E TE 2 E T Fi1 i2 i3 T FT 3 E T ii1 i2 i3 F i4 E T i2 i3 5 E T F i2 i3 T FT 15 E T 16 E 4 5 2預(yù)測分析表的構(gòu)造 FIRST X 集的構(gòu)造算法 若X VT 則FIRST X X 若X Vn 且有產(chǎn)生式X a 則把a加入到FIRST X 中 若X 也是一條產(chǎn)生式 則把 也加到FIRST X 中 若X Y 是一個產(chǎn)生式 且Y Vn 則把FIRST Y 中所有非 元素都加到FIRST X 中 若X Y1 Yi 1是一個產(chǎn)生式且Y Vn 且對任何的j 1 j i 1 FIRST Yj 都含有 即Y1 Yi 1 則把FIRST Yj 中的所有非 元素都加到FIRST X 中 特別地 若FIRST Yj 都含有 把 加入FIRST X 中 重復(fù)以上操作 直到FIRST X 不再增大為止 上述算法可以推廣到FIRST X1 Xk 非終結(jié)符B的FOLLOW B 構(gòu)造算法 對于文法的開始符號S 置 于FOLLOW B 中 若A B 是一個產(chǎn)生式 則把FIRST 加至FOLLOW B 中 若A B是一個產(chǎn)生式 或A B 是一個產(chǎn)生式而 即 FIRST 則把FOLLOW A 加至FOLLOW B 中 構(gòu)造分析表M的算法 1 對文法G的每個產(chǎn)生式A 執(zhí)行第 步和第 步 2 對每個終結(jié)符a FIRST 把A 加至M A a 中 3 若 FIRST 則對任何b follow A 把 加至M A b 中 4 把所有無定義的M A a 標(biāo)上 出錯標(biāo)志 例4 7 4 8 4 6LL 1 分析中的錯誤處理 錯誤類型 棧頂?shù)慕K結(jié)符與當(dāng)前的輸入符號不匹配 非終結(jié)符A處于棧頂 面臨的輸入符號為a 但分析表M中的M A a 為空 錯誤處理方法 跳過輸入串中的一些符號直至遇到 同步符號 為止 同步符號集合的選擇方法 把FLLOWO A 加入A的同步活動集 把FIRST A 加入到A的同步活動集 直接彈出站頂元素 并發(fā)送信息告知插入下一個終結(jié)符后 繼續(xù)分析 例4 9 表4 2加入同步符號的LL 1 分析表 表4 3對 id i的語法分析與錯誤處理