4-第四章_自上而下語法分析.ppt

第4章自上而下語法分析 4 1引言4 2LL 1 分析法4 3遞歸下降分析程序4 4預測分析程序4 5構造預測分析表4 6LL 1 分析中的錯誤處理 4 1引言 1 任務 給定一個上下文無關文法 判定一個單詞符號串能否構成該文法的一個合法的語法單位 句子 即 給定一個串 判定 是否是句子 自上而下語法分析 從樹根開始構造語法樹 即尋找推導序列S 因為推導過程中可以參考當前輸入符號 所以一般采用最左推導 E T 語法樹 FT FT FT aT aF aa 例 G E E TE TT FT FF F a輸入串 aa最左推導 遞歸下降分析 采用程序語言的遞歸功能 為每一個非終結符寫一個分析子程序 預測分析 分析表 棧 分析算法 預測分析法 LL 1 分析 自下向上 遞歸下降分析法 無回溯 語法分析 帶回溯 自上而下 2 語法分析程序 左遞歸 若存在形如 PP 的推導 稱文法是左遞歸的 左遞歸文法中 若存在形如 P P 的產生式 稱此產生式是左遞歸的 稱此文法是直接左遞歸的 否則稱文法是間接左遞歸的 3 自上而下語法分析的主要問題 例 G1 E E E T TT T F FF E i 有產生式 E E T G1是直接左遞歸文法 G2 S S Qc cQ Rb bR Sa a沒有左遞歸產生式 但有 S Qc Rbc Sabc G2 S 是間接左遞歸文法 例 G E E E T TT T F FF E i輸入串 i i iE E T T T F T i T 回溯 對左遞歸文法 分析過程會出現無限循環(huán) 自上而下語法分析要求 文法不能是左遞歸的 E T T F T F F T i F T i i T i E T T T F T F F F F F i F F i i F i i i 例 G S S xAyA 輸入串 x yS xAy x y發(fā)現錯誤 回溯 x y 回溯 若推導時發(fā)現錯誤 可后退若干步 回到某一個中間狀態(tài) 重新選擇其他侯選式 為了回溯 必須紀錄當時推導所作的選擇 以及每一步有多項選擇時的狀態(tài) 代價大 可能要將所有可能都試一遍 效率低 只討論不帶回溯的自上而下語法分析法 因此 要檢查文法是否符合此要求符合要求 LL 1 文法不符合要求 改造文法 若還不行 重寫文法 例 G S S xAyA G S S xAyA BB 輸入串 x yS xAy x By x y 提取公共左因子 例 G E E E T TT T F FF E i 輸入串 i i iE TE FT E iT E i FT E i iT E i i FT E i i iT E i i iE i i i G E E TE E TE T FT T FT F E i 消除左遞歸 4 2LL 1 分析法 LL 1 分析法的含義 LL 1 自上而下分析是從左向右掃描輸入串 LL 1 分析過程中將采用最左推導 LL 1 只需查看一個 當前 符號便可決定如何推導 即選擇哪個產生式進行推導 的語法分析法 LL 1 文法 可采用LL 1 分析法進行分析的文法 LL K 文法 可采用LL K 分析法 需向前查看K個符號才可確定選用哪個產生式 進行分析的文法 1 消除左遞歸 消除直接左遞歸若有產生式 A A 且 A VN V 所能產生的語言L n n 0 改成等價形式 A A A A 一般方法 A A 1 A 2 A m 1 2 n其中 i j不以A開頭改為 A 1A 2A nA A 1A 2A mA 例 G E E E T TT T F FF E i G E E TE E TE T FT T FT F E i 例 G A A Axt Ayy ac b q G A A acA bA qA A xtA yyA 輸入串 acxtA acA acxtA acxt 消除間接左遞歸通過替換 將間接左遞歸文法變?yōu)橹苯幼筮f歸文法 消除直接左遞歸 例 G S S Qc cQ Rb bR Sa aR的產生式代入Q Q Sab ab bQ的產生式代入S S Sabc abc bc c得G1 S S Sabc abc bc cQ Rb bR Sa a 消除其中關于S的直接左遞歸 得G2 S S abcS bcS cS S abcS Q Rb bR Sa a Q R是不可達非終結符 不出現在句型中的非終結符 刪去 G3 S S abcS bcS cS S abcS 例 G S S Qc cQ Rb bR Sa aS代入R R Qca ca aR代入Q Q Qcab cab ab b得G1 S S Qc cQ Qcab cab ab bR Sa a 消除間接左遞歸時 代入非終結符的順序不同 產生的文法可能不同 但是是等價的 消除G1 S 關于Q的直接左遞歸 得G2 S S Qc cQ cabQ abQ bQ Q cabQ R Sa a R是不可達非終結符 刪去 得 G3 S S Qc cQ cabQ abQ bQ Q cabQ 例 輸入串cabc 2 提取左公共因子 A 1 2 n即 有公共左因子 推導至A時 不僅需要關心當前輸入符號 的首符 還要關心 之后是什么 否則可能要回溯變換為 A A A 1 2 n 例 S ifEthenSelseS ifEthenS變換為 S ifEthenSS S elseS 例 G A A V E 賦值語句 著重左部 V i elist i 公共左因子elist elist i E 直接左遞歸E i 解 A V EV iV 提取公共左因子V elist 輸入串 i i i iA V E iV E i elist E i Eelist E i ielist E i i ielist E i i i E i i i i elist Eelist 消除左遞歸elist ielist E i 是句子 某些情況下 無左遞歸 無公共左因子 但分析句子時 仍有困難 例1 G S S Ax ByA yB x輸入串 xyS 難以確定S選擇哪個候選式例2 G A A Ba dB abc 輸入串 aS Ba abca 回溯 a 對VT a a FIRST a a FIRST x x FIRST y y 對VN A y FIRST A y B x FIRST B x S Ax yx S By xy FIRST S y x 例 G S S Ax ByA yB x則 VN S A B VT x y 3 定義集合 VT FIRST x x FIRST y y VN FIRST A y FIRST B x FIRST S y x VT VN Ax yx FIRST Ax y By xy FIRST By x 輸入串 yxS Ax yx 例 G S S Ax ByA yB x則 VN S A B VT x y FIRST a a a VT V 若 則 FIRST 3 定義集合 文法G S A VN 隨符集FOLLOW定義為 FOLLOW A a S Aa a VT 若S A 則 FOLLOW A FOLLOW A 是所有句型中出現在A之后的終結符 或 S S FOLLOW S 例 G A A Ba dB abc A A FOLLOW A A Ba FOLLOW B a 定義 一個上下文無關文法是LL 1 文法的充要條件是 1 文法中每個非終結符A的候選式的終結首符集兩兩不相交 即 若 A 1 2 n則 FIRST i FIRST j 1 i j n i j2 對于文法中每個非終結符A A 1 2 n若 FIRST i 1 i n則 FIRST A FOLLOW A 4 判定文法是否為LL 1 的充分必要條件 5 LL 1 語法分析方法 若當前要匹配的非終結符為A 當前輸入符號為a A的產生式定義 A 1 2 n若 a FIRST i 則用 i替換A 若 a不屬于任何一個候選式的終結首符集 則 若 某個FIRST i 且a FOLLOW A 則讓A與 匹配 否則 報 語法錯誤 說明 通過FIRST FOLLOW集合 作上述檢查比較麻煩 后面引入 預測分析表 LL 1 分析表 方便此工作 例 G S S At BA y B xCtC z FIRST S y t x FIRST A y FIRST B x FIRST C z FIRST At y t FIRST xCt x FOLLOW S FOLLOW A t FOLLOW B FOLLOW C t 判定LL 1 FIRST At FIRST B FIRST y FIRST FIRST z FIRST A FIRST A FOLLOW A C FIRST C FOLLOW C 文法是LL 1 的 輸入串 tS Att FIRST At t t不屬于First y First 但A 且t FL A 輸入串 xytS Bx FIRST B xCt y不屬于First z First C 但y不屬于FL C 4 3遞歸下降分析程序 1 工作原理 對文法中的每一個非終結符A 編寫一個遞歸子程序 根據A的候選式來編寫 若候選式中當前符號為終結符a 則檢查輸入串 若當前輸入符號亦為a 則接受此符號 讀入下一個輸入符號 否則報錯 若候選式中當前符號為非終結符P 則調用關于P的分析子程序 這一組子程序 稱為 遞歸下降分析器 語法分析主程序 調用文法開始符號S的子程序 S的子程序執(zhí)行完 則分析正常結束 若分析過程中發(fā)現錯誤 報 語法錯 遞歸下降語法分析器的性能評價優(yōu)點 很方便的構造語法分析程序 限制 編寫 編譯程序的語言 必須有遞歸功能 且遞歸的內部實現效率較低 速度慢 占用空間多 2 輔助內容 SYM 變量 存放輸入串中的當前單詞符號 詞法分析的結果 ADVANCE 過程 接受當前符號 并從輸入串中讀入一個新的符號 放入SYM ERROR 過程 錯誤處理子程序 例 S E ProcedureSBeginIfSYM ThenBeginADVANCE E IFSYM ThenADVANCEElseERROREndElseERROREnd 3 編寫遞歸下降分析程序 SYM 存放輸入串中的當前單詞符號 ADVANCE 接受當前符號 并從輸入串中讀入一個新符號放入SYM ERROR 錯誤處理程序 例 E TE E TE ProcedureEBeginT E End ProcedureE BeginIfSYM ThenBeginADVANCE T E EndEnd SYM 存放輸入串中的當前單詞符號 ADVANCE 接受當前符號 并從輸入串中讀入一個新符號放入SYM ERROR 錯誤處理程序 例 G S 遞歸下降語法分析程序 S E E TE E TE T FT T FT F E i ProcedureEBeginT E End ProcedureE BeginIfSYM ThenBeginADVANCE T E EndEnd ProcedureSBeginIfSYM ThenBeginADVANCE E IFSYM ThenADVANCEElseERROREndElseREEOREnd ProcedureTBeginF T End ProcedureT beginIfSYM ThenBeginADVANCE F T endEnd ProcedureFBeginIfSYM i ThenADVANCEElseIfSYM ThenBeginADVANCE E IfSYM ThenADVANCEElseERROREndElseERROREnd 這一組程序統(tǒng)稱為 遞歸下降分析器 例 G S S E E TE E TE T FT T FT F E i 4 遞歸下降分析過程 例 輸入串 i i 輸入串 i i 續(xù) S結束 輸入串為空 分析結束 是句子 5 擴充的BNF范式及相應的遞歸下降程序 增加元符號 原來已經有 a 表示a可重復0 n次 a 表示a的出現可有可無 例 G S S E E E T TT T F FF E i G S S E E T T T F F F E i G S S E E T T T F F F E i S F的產生式不變 與前面的遞歸下降程序相同 ProcedureEBeginT WhileSYM doBeginADVANCE T End End 遞歸下降分析程序 ProcedureTBeginF WhileSYM doBeginADVANCE F End End 6 細化的遞歸下降程序 做法 用First Follow集合細化遞歸下降程序 優(yōu)點 改進后的遞歸下降程序執(zhí)行效率高 某些文法必須使用細化的遞歸下降程序 普通 ProcedureABegin End 細化 ProcedureABeginIfSYMINFirst then ElseERROREnd 細化方式一 若A 引入FIRST集進行檢查 細化方式二 A 1 2 n且 FIRST A 檢查a FOLLOW A 若不屬于 則報錯 ProcedureABeginIfSYMINFirst 1 then 1 ElseIfSYMINFirst n then nEnd 普通遞歸下降程序 細化 ProcedureABeginIfSYMINFirst 1 then 1 ElseIfSYMINFirst n then nElseIfsymINFollow A ThenElseERROREnd 例 G S S E E TE E TE T FT T FT F E i ProcedureEBeginIfSYM i ORSYM ThenBeginT E EndElseERROREnd ProcedureEBeginT E End 細化方式1 E TE ProcedureE BeginIfSYM ThenBeginADVANCE T E EndEnd ProcedureE BeginIfSYM ThenBeginADVANCE T E EndElseIfsymINFollow E ThenElseERROREnd 等價 細化方式2 Ifsym orsym ThenElseERROR Ifsym andsym ThenERROR 輸入串 ii ProcedureEBeginT E End ProcedureFBeginIfSYM i ThenADVANCEElseIfSYM ThenBegin EndElseERROREnd ProcedureTBeginF T End 執(zhí)行 S E T F報錯 ProcedureEBeginIfSYM i ORSYM ThenBeginT E EndElseERROREnd 執(zhí)行 S E報錯 運行效率高 細化方式 普通遞歸程序 4 4預測分析程序 預測分析表 棧 標準分析算法進行語法分析 1 預測分析表 LL 1 分析表 矩陣M A a 其中 A VN a VT或為結束符 M A a 一條產生式 表示 當前要推導的非終結符A 遇到輸入符號為a時 應選用的產生式 M A a 出錯標志 空 則A不該遇到輸入符號a 2 分析算法 棧中放入 及文法開始符號S 設棧頂符號為X 當前輸入符號為a 重復以下工作 若X a 分析結束 識別出句子 若X VT 且X a 則 將X出棧 輸入符號前移 接收一個符號 若X VT 且X a 出錯處理 若X VN 且M X a X X1X2 Xk 則 將X出棧 產生式右部反序入棧 入棧順序為 Xk X2X1 若X VN 且M X a 為報錯標識 出錯處理 例 輸入串 i i 例 輸入串 i i 4 5構造預測分析表 First a a VTFirst a a 特別 First 1 計算FIRST集 FIRST a a a VT V 若 則 FIRST 分三步計算First a a VTFirst X X VNFirst VN VT 符號串 FIRST X X VN若有 X a a VT 則 a FIRST X 若有 X 則 FIRST X 若有 X Y 且Y VN 則 FIRST X FIRST X FIRST Y 若有 X Y1Y2 Yi 1Yi YK Yj VN FIRST Yj 1 j i 1則 FIRST X FIRST X FIRST Yi 若有 X Y1Y2 YK Yj VN FIRST Yj 1 j k則 FIRST X FIRST X 重復以上步驟 直至每個FIRST集不再增大為止 G A A BCD iB i C i D i VT i VN A B C D a VTFirst i i First First First First X VNFirst B First C First D First A First i First B First C First D i FIRST VN VT 只需計算某些 1 是產生式的候選式 2 是產生式的候選式中 某一VN之后的串 設 X1X2 XNFIRST FIRST X1 若 FIRST Xj 1 j i 1則 FIRST FIRST FIRST Xi 若 FIRST Xj 1 j N則 FIRST FIRST G A A BCD iB i C i D i a VT X VN VN VT First BCD First B First C First D First CD First C First D First i First i First i First D First i First 已知 2 計算FOLLOW集 定義 G S A VNFOLLOW A a S Aa a VT 求法 FOLLOW S S為文法的開始符號 若有產生式A B 則 FOLLOW B FOLLOW B FIRST 若有產生式A B 或A B 且 FIRST FOLLOW B FOLLOW B FOLLOW A 重復以上步驟 直至每個FOLLOW集合不再增大為止 G A A BCD iB i C i D i X VN V FOLLOW S 若A B FL B FL B First A BCDA BCD 若A B 或A B 且 First FL B FL B FL A A BCDA BCDA BCD 3 構造預測分析表 基本思想設 棧頂符號為A 當前輸入符號為a 若A 是一個產生式 且a First 那么選擇 取代A匹配成功的希望最大 故 M A a 元素為 A 若A 且 First a Follow A 則棧頂的A應被 匹配 此時輸入符號不前進 讓A的隨符與輸入符號進行匹配 這樣輸入串匹配成功的可能最大 故M A a 元素為A 構造算法對文法中的每一條產生式A 執(zhí)行 對 a First 在M A a 中加入A 若 First 對每個a Follow A 在M A a 中加入A 把所有無定義的M A a 都填上 出錯標志 說明 用此算法可以為任意文法G構造其分析表M 若M不包含有多重入口 也稱 重定義項 即 某個表項中填有一個以上的產生式 則文法是LL 1 文法 對非LL 1 文法 如 二義文法 或沒有消除左遞歸和提取左因子的文法 構造出的M包含有多重入口 G A A BCD iB i C i D i 沒有多重入口 是LL 1 文法 輸入串 i i A BCD CD iD i i 例 判斷文法G S 是否為LL 1 文法 S ifCthenSelseS ifCthenS otherC b 為方便描述 更名 令 if ithen telse eother a文法簡化為G1 S S iCtSeS iCtS aC b 改造文法 提取公共左因子 將文法改寫成 G2 S S iCtSS aS eS C b 求首符集和隨符集 G2 S S iCtSS aS eS C b 判定方法1 根據定義 First iCtSS First a i a First eS First e 對 S First S Follow S e e e 此文法不是LL 1 文法 G2 S S iCtSS aS eS C b 判定方法2 構造預測分析表 其中M S e 是二重的 此文法不是LL 1 文法 如果令M S e 只含S eS 則意味著堅持把else和最近的then相結合 此時 是LL 1 文法 例 高級語言控制語句的遞歸下降分析程序 G2 S S iCtSS aS eS C b 預測分析表 else和最近的then相結合 其中 if ithen telse eother a ProcedureCBeginIfSYM b ThenADVANCEElseERROREnd 細化的遞歸下降程序 ProcedureS BeginIfSYM else ThenBeginADVANCE SEndElseIfsym ThenERROREnd ProcedureSBeginIfSYM if ThenBeginADVANCE C IfSYM then ThenBeginADVANCE S S EndElseERRORENDELSEIfsym a ThenADVANCEElseERROREnd G2 S S iCtSS aS eS C b if ithen telse eother a 4 6LL 1 分析中的錯誤處理 在編譯過程中系統(tǒng)發(fā)現的錯誤主要有兩類 語法錯誤 語義錯誤語法錯誤 指語法結構錯誤 主要有 1 錯誤種類 預測分析算法 出錯情況 棧中放入 及文法開始符號S 設棧頂符號為X 當前輸入符號為a 重復以下工作 若 X VT 且X a 分析結束 識別出句子 若 X VT 且X a 將X出棧 輸入符號前移 接收一個符號 若 X VT 且X a 出錯處理 若X VN 且M X a X X1X2 Xk 則 將X出棧 產生式右部反序入棧 入棧順序為 Xk X2X1 若X VN 且M X a 為報錯標識 出錯處理 2 發(fā)現錯誤的時機 出錯情況 設 棧頂符號為X 當前輸入符號為aX VT 但 X aX VN 但 M X a 中為空但同一個錯誤形式 可以被理解成不同的錯誤原因 例 G E E TE E TE T FT T FT F