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

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

第五章語法分析 自下而上分析 5 1自下而上分析基本問題5 2算符優(yōu)先分析5 3LR分析法5 4語法分析器的自動產(chǎn)生工具YACC 5 1自下而上分析基本問題 5 1 1歸約5 1 2規(guī)范歸約簡述5 1 3符號棧的使用與語法樹的表示 5 1 1歸約 移進(jìn) 歸約 法 用一個寄存符號的先進(jìn)后出棧 把輸入符號一個一個地移進(jìn)到棧里 當(dāng)棧頂形成某個產(chǎn)生式的一個候選式時 即把棧頂?shù)倪@一部分替換成 歸約為 該產(chǎn)生式的左部符號 例子 假定文法GS aAcBeA bA AbB d輸入串a(chǎn)bbcde歸約到S過程 圖5 1規(guī)約中符號棧的變遷 問題 如果步驟5用規(guī)則 2 而不是用規(guī)則 3 則會有不同的結(jié)果 這就是 可規(guī)約串 問題 對可規(guī)約串的刻畫不同 分析的方法也不同 本課程討論 最左素短語 和 句柄 兩種可規(guī)約串刻畫方法 5 1 2規(guī)范歸約簡述 短語 直接短語和句柄定義 令G是一個文法 S是文法的開始符號 假定 是文法的一個句型 如果有S A 且A 則 稱是句型 相對于非終結(jié)符A的短語 特別是 如果有A 則稱 是句型 相對于規(guī)則A 的直接短語一個句型的最左直接短語稱為該句型的句柄 利用句柄規(guī)約的例子 句型歸約規(guī)則abbcde 2 A baAbcde 3 A AbaAcde 4 B daAcBe 1 S aAcBeS 規(guī)范規(guī)約的一般定義 假設(shè) 是文法G的一個句子 我們稱序列 n n 1 0是 的一個規(guī)范規(guī)約 如果此序列滿足 1 n 2 0 S 3 對任意的i i 1是從 i經(jīng)句柄替換的結(jié)果 規(guī)范推導(dǎo) 最右推導(dǎo)常被稱為規(guī)范推導(dǎo)規(guī)范句型 最右推導(dǎo)的句型稱為規(guī)范句型規(guī)范歸約 規(guī)范推導(dǎo)的逆過程 最左規(guī)約 稱為規(guī)范歸約 5 1 3符號棧的使用與語法樹的表示 規(guī)范規(guī)約的數(shù)據(jù)結(jié)構(gòu)和動作 采用棧作為語法分析的基本數(shù)據(jù)結(jié)構(gòu) 符號棧輸入串 w S 語法分析對符號棧的使用有四類操作 移進(jìn) 歸約 接受 和 出錯處理 任何可規(guī)約串的出現(xiàn)必須在棧頂 例5 3 輸入串i1 i2 i3的分析步驟 步驟符號棧輸入串所用產(chǎn)生式0 i1 i2 i3 預(yù)備1 i1 i2 i3 進(jìn)2 F i2 i3 歸 用F i3 T i2 i3 歸 用T F4 T i2 i3 進(jìn)5 T i2 i3 進(jìn) 13 E 歸 用E E T14 E 接受 5 2算符優(yōu)先分析 5 2 1算符優(yōu)先文法及優(yōu)先表構(gòu)造5 2 2算符優(yōu)先分析算法5 2 3優(yōu)先函數(shù)5 2 4算符優(yōu)先分析中的出錯處理 算符優(yōu)先分析法的主要思想 是自下而上的歸約過程 但這種歸約未必是嚴(yán)格的最左歸約 而是借助于兩個終結(jié)符之間的優(yōu)先關(guān)系來尋找 可歸約串 進(jìn)行歸約 算符優(yōu)先關(guān)系定義 1 a b a的優(yōu)先性低于b 當(dāng)且僅當(dāng)G中含有形如P aR 的產(chǎn)生式 而R b 或R Qb 但并不意味b高于a 2 a b a的優(yōu)先性等于b 當(dāng)且僅當(dāng)G中含有形如P ab 的產(chǎn)生式或P aQb 的產(chǎn)生式 但并不意味b等于a 3 a b a的優(yōu)先性高于b 當(dāng)且僅當(dāng)G中含有形如P Rb 的產(chǎn)生式 而R a或R aQ a的優(yōu)先性高于b 5 2 1算符優(yōu)先文法及優(yōu)先表構(gòu)造 算符文法定義 一個文法 如果它的任一產(chǎn)生式的右部都不含兩個相繼 并列 的非終結(jié)符 即不含如下形式的產(chǎn)生式右部 QR 算符優(yōu)先文法定義 如果一個算符文法G中的任何終結(jié)符對 a b 至多只滿足下述三關(guān)系之一 a b a b a b 例5 4構(gòu)造下面算法優(yōu)先文法的優(yōu)先表 1 E E T T 2 T T F F 5 3 3 F P F P 4 P E i解 由 4 可得 由 2 3 可得 最后可得表5 1所示優(yōu)先表 算符優(yōu)先文法G構(gòu)造優(yōu)先關(guān)系表的算法 FIRSTVT P 和LASTVT P 定義 FIRSTVT P a P a 或P Qa a VT而Q VN LASTVT P a P a或P aQ a VT而Q VN FIRSTVT P 構(gòu)造 若有產(chǎn)生式P a 或P Qa 則a FIRSTVT P 若a FIRSTVT Q 且產(chǎn)生式P Q 則a FIRSTVT P 算法程序運算如下 PROCEDUREINSERT P a IFNOTF P a THENBEGINF P a TRUE 把 P a 下推進(jìn)STACK棧END 主程序 BEGINFOR每個非終結(jié)符P和終結(jié)符aDOF P a FALSE FOR每個形如P a 或P Qa 的產(chǎn)生式DOINSERT P a WHILESTACK非空DOBEGIN把STACK的棧頂記為 Q a 上托出去 FOR每條形如P Q 的產(chǎn)生式DOINSERT P a ENDOFWHILE END 構(gòu)造優(yōu)先表的算法 FOR每條產(chǎn)生式P X1X2 XnDOFORi 1TOn 1DOBEGINIFXi和Xi 1均為終結(jié)符THEN置Xi Xi 1IFi n 2且Xi都為終結(jié)符 但Xi 1為非終結(jié)符THEN置Xi Xi 2 IFXi為終結(jié)符 而Xi 1為非終結(jié)符THENFORFIRSTVT Xi 1 中的每個aDO置Xi a IFXi為非終結(jié)符而Xi 1為終結(jié)符THENFORLASTVT Xi 中的每個aDO置a Xi 1END 5 2 2算符優(yōu)先分析算法 素短語 是一個短語 它至少含有一個終結(jié)符 并且 除它自身之外不再含任何更小的素短語 最左素短語 最左邊的素短語是最左素短語 例子 對文法 5 3 p p和i是句型p p i的素短語 而p p i本身也是素短語 算符優(yōu)先文法 算符優(yōu)先文法 我們把句型 括在兩個 之間 的一般形式寫成 N1a1N2a2 NnanNn 1 其中 每個ai都是終結(jié)符 Ni是可有可無的非終結(jié)符 文法G的任何短語是滿足如下條件的最左子串Njaj NiaiNi 1aj 1 ajaj aj 1 aj 1 aiai ai 1 算符優(yōu)先分析算法 k 1S k REPEAT把下一個輸入符號讀進(jìn)a中 IFS k VTTHENj kELSEj k 1 WHILES j aDOBEGINREPEATQ S j IFS j 1 VTTHENj j 1ELSEj j 2UNTILS j Q 把S j 1 S k 歸約為某個N k j 1 S k NENDOFWHILE IFS j aORS j aTHENBEGINk k 1 S k aENDELSEERROR 調(diào)用出錯診察程序 UNTILa 算法分析 沒有定義非終結(jié)符的優(yōu)先級 它無法發(fā)現(xiàn)單個非終結(jié)符組成的 可規(guī)約串 所以算符優(yōu)先分析不是規(guī)范規(guī)約 優(yōu)點 速度快 缺點 忽略了非終結(jié)符的規(guī)約過程 存在一定的危險 5 2 3優(yōu)先函數(shù) 入棧優(yōu)先函數(shù)f和比較優(yōu)先函數(shù)g定義 若Q1 Q2則f Q1 g Q2 采用優(yōu)先函數(shù)的優(yōu)缺點 便于比較運算 節(jié)省空間 由任何兩個非終結(jié)符都可以進(jìn)行比較 所以可能掩蓋一些問題 從優(yōu)先表構(gòu)造優(yōu)先函數(shù)的方法是 對于每個終結(jié)符a 包括 令其對應(yīng)兩個符號fa和ga 畫一張以fa和ga所有符號為結(jié)點的方向圖 如果a b 那么 就從fa畫一箭弧至gb 如果a b 就畫一條從gb到fa的箭弧 對每個結(jié)點都賦予一個數(shù) 此數(shù)等于從該結(jié)點能到達(dá)結(jié)點 包括出發(fā)結(jié)點自身在內(nèi) 的個數(shù) 賦給fa的數(shù)作為f a 賦給gb的數(shù)作為g b 檢查所構(gòu)造出來的函數(shù)f和g 看它們同原來的關(guān)系表是否有矛盾 如果沒有矛盾 則f和g就是所要的優(yōu)先函數(shù) 如果有矛盾 那么 就不存在優(yōu)先函數(shù) 5 2 4算符優(yōu)先分析中的出錯處理 錯誤類型 若找到某一 句柄 此處 句柄 指素短語 但不存在任一產(chǎn)生式 其右部為此 句柄 若在棧頂終結(jié)符號與下一輸入符號之間不存在任何優(yōu)先關(guān)系 算法5 2 1 對規(guī)約中發(fā)現(xiàn)的問題 1 找出相近的素短語 2 分析差異 3 給出可能的錯誤信息 對算符優(yōu)先分析中的問題 1 如 或 被規(guī)約 則檢查其兩端是否出現(xiàn)非終結(jié)符 否則 打印錯誤信息 缺表達(dá)式 2 如i被規(guī)約 則檢查其左端或右端是否有非終結(jié)符 如果有 則給出信息 表達(dá)式無運算符連接 3 如果 被規(guī)約 則檢查是否在括號間有一非終結(jié)符 如果沒有 則給出信息 括號無表達(dá)式 算法5 2 1 采用對輸入串進(jìn)行 改變 插入和刪除 等方法 如 當(dāng) 結(jié)束 將 從站頂移去 并給出錯誤信息 非法左括號 當(dāng)I或 后跟I或 時 在輸入端插入 并給出錯誤信息 缺少運算符 當(dāng)表達(dá)式以右括號開始 從輸入串中刪除 并給出錯誤信息 非法右括號 若站頂有非終結(jié)符E 則表達(dá)式分析完畢 若為空 則在輸入端插入I 給出錯誤信息 缺少表達(dá)式 5 3LR分析法 5 4語法分析器的自動產(chǎn)生工具YACC YACC LALR 1 分析程序的生成器工作方式 Yacc程序的構(gòu)成 3個部分 中間以 分割聲明 變量 常量的聲明 正規(guī)定義翻譯規(guī)則 形式如下 其中pi是正規(guī)式p1 動作1 p2 動作2 用C語言編寫的支持例程 include include tokenNUMBER 此處聲明了允許的記號 command exp printf d n 1 command為開始符號 allowsprintingoftheresult exp exp term 1 3 記號可以直接出現(xiàn)在語法規(guī)則中 exp term 1 3 term 1 term term factor 1 3 factor 1 factor NUMBER 1 expr 2 main returnyyparse intyylex void intc while c getchar eliminatesblanks if isdigit c ungetc c stdin scanf d allowsforprintingofanerrormessages Yacc分析沖突與消除二義性的規(guī)則 在y output中報告調(diào)查的分析沖突二義性消除的規(guī)則Yacc可以為分析沖突發(fā)生產(chǎn)生一個分析程序 并消除二義性指明有二義性的文法相分割開得算符優(yōu)先及結(jié)合性的機(jī)制 使得文法描述更簡單 left left 表明 有相同的優(yōu)先權(quán)且是左結(jié)合的 而 具有更高的優(yōu)先權(quán) 且是左結(jié)合的Yacc嵌入的動作 Yacc分析的錯誤糾正 采用錯誤產(chǎn)生式的方式 錯誤產(chǎn)生式 以偽記號error為它的右邊唯一符號 糾錯步驟 若分析程序檢測到錯誤 從分析棧中彈出狀態(tài)直至到達(dá)一個其中的error是合法的向前看符號的狀態(tài) 對該狀態(tài)和偽記號error進(jìn)行正常的移進(jìn)和歸約 若在一個錯誤發(fā)生后 發(fā)現(xiàn)了更多的錯誤 則直到將3個成功的記號合法的移進(jìn)分析棧中后為止 再丟棄引起錯誤的輸入符號 避免了因為錯誤而丟掉大量的輸入符號