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

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

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