自低而上的優(yōu)先分析法.ppt

2020 2 14 1 第六章自底向上的優(yōu)先分析法 自底向上語法分析概述簡單優(yōu)先分析算符優(yōu)先分析 課前思考 什么是自下而上語法分析的策略 什么是移進 歸約分析 移進 歸約過程和自頂向下最右推導有何關系 自下而上語法分析成功的標志是什么 什么是可歸約串 移進 歸約過程的關鍵問題是什么 如何確定可歸約串 如何決定什么時候移進 什么時候歸約 什么是算符文法 什么是算符優(yōu)先文法 算符優(yōu)先分析是如何識別可歸約串的 算符優(yōu)先分析法的優(yōu)缺點和局限性有哪些 語法分析 推導自上而下的語法分析過程預測分析程序 最左推導 注 要求文法是LL 1 文法歸約自下而上的語法分析過程簡單優(yōu)先分析法 算符優(yōu)先分析法 LR分析法 學習目標 算符優(yōu)先分析法是自下而上 自底向上 語法分析的一種 尤其適應于表達式的語法分析 由于它的算法簡單直觀易于理解 因此 也是學習其他自下而上語法分析的基礎 通過本章學習應掌握 對給定的文法能夠判斷該文法是否是算符文法 對給定的算符文法能夠判斷該文法是否是算符優(yōu)先文法 對給定的算符文法能構(gòu)造算符優(yōu)先關系表 并能利用算符優(yōu)先關系表判斷該文法是否是算符優(yōu)先文法 能應用算符優(yōu)先分析算法對給定的輸入串進行移進 歸約分析 在分析的每一步能確定當前應移進還是歸約 并能判斷所給的輸入串是否是該文法的句子 了解算符優(yōu)先分析法的優(yōu)缺點和實際應用中的局限性 學習指南 算符優(yōu)先分析法是自下而上語法分析的一種 它的算法簡單 直觀 易于理解 所以通常作為學習其它自下而上語法分析的基礎 為學好本章內(nèi)容 應復習有關語法分析的知識 如 什么是語言 文法 句子 句型 短語 簡單短語 句柄 最右推導 規(guī)范歸約基本概念 短語 直接短語 句柄 對于文法G S 如果S A 且A 則稱 是句型 相對于非終結(jié)符A的短語 若有A 則稱 是句型 相對于A或規(guī)則A 的直接短語 一個句型的最左直接短語稱為該句型的句柄 自下而上的語法分析過程 自下而上的語法分析過程思想自下而上的語法分析過程是一個最左歸約的過程 從輸入串開始 朝著文法的開始符號進行歸約 直到到達文法的開始符號為止的過程注意 輸入串在這里是指從詞法分析器送來的單詞符號組成的二元式的有限序列自底而上語法分析比自頂向下語法分析更有效率 對語法的限制更少 2020 2 14 8 工作方式 移進 歸約 方式即 自左到右把輸入串的符號一個一個移進棧 在移動過程中不斷查看棧頂符號串 一旦形成某個句型的句柄時 就將此句柄用相應的產(chǎn)生式左部替換 歸約 若再形成句柄 就繼續(xù)替換 直到棧頂不再形成句柄為止 然后繼續(xù)移進符號 重復上面的過程直到棧頂只剩下文法的開始符號 輸入串讀完為止 這樣就認為識別了一個句子 2020 2 14 9 移進 歸約 法的棧實現(xiàn) 自頂向下 初始 分析棧 S輸入串 a1a2 an 分析過程 用產(chǎn)生式的右部按反序進棧替換左部 結(jié)束 成功 自底向上 初始 分析棧 輸入串 a1a2 an 分析過程 自左至右把輸入符號串W的符號一一移進棧里 一旦發(fā)現(xiàn)棧頂?shù)囊徊糠址栃纬梢粋€可歸約串 就把棧中這個子串用相應的歸約符號替換 結(jié)束 S 成功 四類操作 移進 歸約 接受 出錯處理 移進讀入一個單詞并壓入棧內(nèi) 讀頭后移歸約檢查棧頂若干個符號能否進行歸約 若能 就以產(chǎn)生式左部替代該符號串 同時輸出產(chǎn)生式編號接受移進 歸約的結(jié)局是棧內(nèi)只剩下棧底符號和文法開始符號 讀頭也指向語句的結(jié)束符出錯處理 2020 2 14 11 文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d a b b c d e 步驟 符號棧 輸入符號串 動作 1 abbcde 移進 2 abbcde 移進 4 aAbcde 移進 6 aAcde 移進 7 aAcde 移進 9 aAcBe 移進 11 S 接受 分析符號串a(chǎn)bbcde是否G S 的句子 對輸入串a(chǎn)bbcde 的移進 歸約分析過程 2020 2 14 12 歸約過程恰好是最右推導的逆過程最右推導稱為規(guī)范推導 規(guī)范推導得到的句型稱為規(guī)范句型 規(guī)范歸約也稱最左歸約 規(guī)范歸約定義 假定 是文法G的一個句子 我們稱序列 n n 1 0是 的一個規(guī)范歸約 如果此序列滿足 1 n 2 0為開始符號 3 對任何i 0 i n i 1是從 i經(jīng)把句柄替換為相應產(chǎn)生式的左部符號而得到的 如果文法G無二義 則規(guī)范推導的逆過程一定是規(guī)范歸約 由于移進 歸約是規(guī)范推導 最右推導 的逆過程 即規(guī)范歸約 最左歸約 當一個文法無二義性時 那么它對一個句子的規(guī)范推導是唯一的 規(guī)范歸約也必然是唯一的 因而每次歸約時一定要按當前句型的句柄 也就是說 任何時候棧中的符號串和剩余的輸入串組成一個句型 當句柄出現(xiàn)在棧頂符號串中時 則可用句柄歸約 這樣一直歸約到輸入串只剩結(jié)束符 文法符號棧中只剩開始符號 這時才能認為輸入符號串是文法的句子 否則為出錯 2020 2 14 14 文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d a b b c d e 步驟 符號棧 輸入符號串 動作 1 abbcde 移進 2 abbcde 移進 4 aAbcde 移進 6 aAcde 移進 7 aAcde 移進 9 aAcBe 移進 11 S 接受 分析符號串a(chǎn)bbcde是否G S 的句子 對輸入串a(chǎn)bbcde 的移進 歸約分析過程 2020 2 14 15 簡單優(yōu)先分析法對一個文法按一定原則求出該文法所有符號即包括終結(jié)符和非終結(jié)符之間的優(yōu)先關系 按照這種關系確定歸約過程中的句柄 它的歸約過程實際上是一種規(guī)范歸約 算符優(yōu)先分析法只規(guī)定算符之間的優(yōu)先關系 也就是只考慮終結(jié)符之間的優(yōu)先關系 由于算符優(yōu)先分析不考慮非終結(jié)符之間的優(yōu)先關系 在歸約過程中只要找到可歸約串就歸約 并不考慮歸約到哪個非終結(jié)符 因此算符優(yōu)先歸約不是規(guī)范歸約 6 1自底向上優(yōu)先分析概述 2020 2 14 16 6 2簡單優(yōu)先分析法 按照文法符號 包括終結(jié)符和非終結(jié)符 的優(yōu)先關系確定句柄 相鄰文法符號之間的優(yōu)先關系在句型中 句柄內(nèi)各相鄰符號之間具有相同的優(yōu)先級 相同優(yōu)先級用 由于句柄要先歸約 所以規(guī)定句柄兩端符號的優(yōu)先級要比位于句柄之外的相鄰符號的優(yōu)先級高 優(yōu)先級低于表示為 優(yōu)先級高于表示為 某句型中 N1 Ni 1Ni NjNj 1 Nn 優(yōu)先分析法的基本思想句型中Ni Nj是句柄 語法分析程序可以通過尋找Ni 1Ni和NjNj 1這兩個關系來確定句柄的頭尾 從而確定句柄進行歸約 2020 2 14 19 簡單優(yōu)先文法的定義 滿足以下條件的文法是簡單優(yōu)先文法 1 在文法符號集V中 任意兩個符號之間最多只有一種優(yōu)先關系成立 2 在文法中任意兩個產(chǎn)生式?jīng)]有相同的右部 2020 2 14 20 優(yōu)先關系 優(yōu)先關系XY 文法G中存在產(chǎn)生式A XY XY 文法G中存在產(chǎn)生式A XB 且BY XY 文法G中存在產(chǎn)生式A BD 且B X DY 的優(yōu)先級所有符號 所有符號的優(yōu)先級 這里僅對與 相鄰的文法符號而言 簡單優(yōu)先分析的思想簡單優(yōu)先矩陣 根據(jù)優(yōu)先關系的定義 將簡單優(yōu)先文法中各文法符號之間的這種關系用一個矩陣表示 稱作簡單優(yōu)先矩陣 讀入一個單詞后 比較棧頂符號和該單詞的優(yōu)先級 若棧頂符號優(yōu)先級低于或等于該單詞 繼續(xù)讀入 若棧頂符號優(yōu)先級高于讀入符號 則找句柄進行歸約 找不到句柄就繼續(xù)讀入 直到最后棧內(nèi)只剩下開始符號 輸入串讀到 為止 此時識別正確 2020 2 14 22 文法G S 1 S bAb 2 A B a 3 B Aa 步驟 符號棧 輸入符號串 動作 1 b aa b b 移進 2 b aa b b 移進 3 b aa b a 移進 4 b aa b a a 歸約A a 5 b Aa b A a 移進 6 b Aa b a 移進 7 b Aa b b 歸約B Aa 8 b Bb B b 歸約A B 9 bAb A b 移進 10 bAb b 歸約S bAb 11 S 接受 對輸入串b aa b 的簡單優(yōu)先分析過程 簡單優(yōu)先關系矩陣 2020 2 14 23 6 2 3簡單優(yōu)先分析法的算法步驟 將輸入符號串a(chǎn)1a2 an 依次逐個存入符號棧S中 直到遇到棧頂符號ai的優(yōu)先性下一個待輸入符號aj為止 棧頂當前符號ai為句柄尾 由此向左在棧中找句柄的頭符號ak 即找到ak 1ak為止 由句柄ak ai在文法的產(chǎn)生式中查找右部為ak ai的產(chǎn)生式 若找到則用相應左部代替句柄 若找不到則為出錯 重復1 2 3步 直到棧中只剩開始符 簡單優(yōu)先分析法的優(yōu)缺點優(yōu)點 技術(shù)簡單缺點 適用范圍小 分析表尺寸太大 2020 2 14 25 6 3算符優(yōu)先分析 算符優(yōu)先分析法所謂算符優(yōu)先分析法就是仿效四則運算的計算過程而構(gòu)造的一種語法分析方法算符優(yōu)先分析法的特點 簡單直觀 特別方便于表達式分析 易于手工實現(xiàn) 是自下而上的歸約過程 但未必按照句柄歸約算符優(yōu)先分析法的關鍵規(guī)定算符 終結(jié)符 的優(yōu)先級及結(jié)合性質(zhì)例如 8 7 6的運算 2020 2 14 26 算符優(yōu)先分析的基本思想只考慮算符 廣義為終結(jié)符 之間的優(yōu)先關系 對輸入串i1 i2 i3的歸約過程可表示為 例 若有文G S 1 E E E 2 E E E 3 E i 2020 2 14 28 6 3 1直觀算符優(yōu)先分析 某些文法具有 算符 特性表達式運算符 優(yōu)先級 結(jié)合性 人為地規(guī)定其算符的優(yōu)先順序 即給出優(yōu)先級別和同一級別的結(jié)合性 算符間的優(yōu)先關系表示規(guī)定如下 ab表示a的優(yōu)先性低于b ab表示a的優(yōu)先性等于b 即與b相同 ab表示a的優(yōu)先性高于b 注意 當有關系ab時 卻不一定有關系ba 當有關系ab時 卻不一定有ba 2020 2 14 30 如何確定算符優(yōu)先關系 1 i的優(yōu)先級最高 2 優(yōu)先級次于i 右結(jié)合 3 和 優(yōu)先級次之 左結(jié)合 4 和 優(yōu)先級最低 左結(jié)合 5 括號 的優(yōu)先級大于括號外的運算符 小于括號內(nèi)的運算符 內(nèi)括號的優(yōu)先性大于外括號 6 的優(yōu)先性低于與其相鄰的算符 文法G E E E E E E E E E E E E E i 算符優(yōu)先關系表 2020 2 14 31 文法G E E E E E E E E E E E E E i 步驟 符號棧 輸入符號串 動作 1 i i i i 移進 2 i i i 歸約 3 E i i 移進 4 E i i i 移進 5 E i i 歸約 6 E E i 移進 7 E E i i 移進 8 E E i 歸約 9 E E E 歸約 10 E E 歸約 11 E 接受 對輸入串i i i的算符優(yōu)先分析過程 算符優(yōu)先關系表 歸約成功標志 棧中只剩 E 輸入符號串剩 2020 2 14 32 6 3 2算符優(yōu)先文法的定義 定義6 1如果不含空產(chǎn)生式的上下文無關文法G中沒有形如A BC 的產(chǎn)生式 其中B C VN 則稱G為算符文法 OG 例如 表達式文法E E E E E E i 性質(zhì)1 在算符文法中任何句型都不包含兩個相鄰的非終結(jié)符 數(shù)學歸納法 性質(zhì)2 如Ab或bA出現(xiàn)在算符文法的句型 中 其中A VN b VT 則 中任何含b的短語必含有A 反證法 注意 含b的短語必含A 含A的短語不一定含b 2020 2 14 34 算符優(yōu)先關系的定義6 2 在OG中定義 算符優(yōu)先關系 abG中有形如A ab 或A aBb 的產(chǎn)生式 abG中有形如A aB 的產(chǎn)生式 而Bb 或BCb abG中有形如A Bb 的產(chǎn)生式 而B a或B aC規(guī)定若Sa 或SBa 則 aS a或S aB則a 由語法樹結(jié)構(gòu)決定優(yōu)先性 2020 2 14 36 算符優(yōu)先文法的定義6 3 在一不含 產(chǎn)生式的OG文法G中 若任意兩個終結(jié)符間至多有一種算符優(yōu)先關系存在 則稱G為算符優(yōu)先文法 OPG E E E E E E i不是算符優(yōu)先文法 結(jié)論算符優(yōu)先文法是無二義的 2020 2 14 37 6 3 3算符優(yōu)先關系表的構(gòu)造 由定義直接構(gòu)造由關系圖法構(gòu)造算符優(yōu)先關系表 自學 2020 2 14 38 首先引入兩個概念FIRSTVT B b Bb 或BCb 對于非終結(jié)符B 其往下推導所可能出現(xiàn)的首個算符LASTVT B a B a或B aC 對于非終結(jié)符B 其往下推導所可能出現(xiàn)的最后一個算符 2020 2 14 39 如何計算算符優(yōu)先關系 1 關系直接看產(chǎn)生式的右部 若出現(xiàn)了A ab 或A aBb 則ab2 關系求出每個非終結(jié)符B的FIRSTVT B 若A aB 則 b FIRSTVT B ab3 關系求出每個非終結(jié)符B的LASTVT B 若A Bb 則 a LASTVT B ab 例 設文法G的產(chǎn)生式為 1 S aAcBe 2 A Ab b 3 B d計算每個非終結(jié)符的FIRSTVT與LASTVT及所有終結(jié)符之間的關系 例 構(gòu)造下面文法的算符優(yōu)先表文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F P F 6 F P 7 P E 8 P i 1 求各個非終結(jié)符的首終結(jié)符集和尾終結(jié)符集 為了考慮語句的開始和結(jié)束符號 對文法拓廣 加一個產(chǎn)生式 0 E E 2 填寫算符優(yōu)先表 2020 2 14 43 文法G E 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F P F 6 F P 7 P E 8 P i FIRSTVT E FIRSTVT E i FIRSTVT T i FIRSTVT F i FIRSTVT P i LASTVT E LASTVT E i LASTVT T i LASTVT F i LASTVT P i 1 關系由產(chǎn)生式 0 和 7 得 2 關系找形如 A aB 的產(chǎn)生式 E 則 FIRSTVT E T 則 FIRSTVT T F 則 FIRSTVT F F 則 FIRSTVT F E 則 FIRSTVT E 3 關系找形如 A Bb 的產(chǎn)生式E 則LASTVT E E 則LASTVT E T 則LASTVT T P 則LASTVT P E 則LASTVT E 優(yōu)先表構(gòu)造算法的討論構(gòu)造優(yōu)先表的算法僅僅反映文法符號間關系 并不反映附加條件 對二義性文法構(gòu)造算符優(yōu)先表 可能會出現(xiàn)多重定義項 2020 2 14 45 6 3 4算符優(yōu)先分析算法 歸約過程中 只考慮終結(jié)符之間的優(yōu)先關系來確定句柄 而與非終結(jié)符無關 這樣去掉了對非終結(jié)符的歸約 所以用算符優(yōu)先分析法的規(guī)約過程與規(guī)范歸約是不同的 為解決在算符優(yōu)先分析過程中如何尋找可歸約串 引進最左素短語的概念 2020 2 14 46 1 算符優(yōu)先分析句型的性質(zhì)算符文法的任一句型有如下形式 N1a1N2a2 NnanNn 1 若Niai NjajNj 1為句柄 則有ai 1aiai 1 aj 1ajaj 1對于算符優(yōu)先文法 如果aNb 或ab 出現(xiàn)在句型r中若ab 則在r中必含有b而不含a的短語存在若ab 則在r中必含有a而不含b的短語存在若ab 則在r中含有a的短語必含有b 反之亦然 非規(guī)范分析 a 規(guī)范歸約嚴格按照句柄進行歸約 終結(jié)符和非終結(jié)符一起考慮 只要棧頂形成句柄 不管句柄內(nèi)是否包含終結(jié)符都要進行歸約 例如 考慮非二義的表達式文法G E E E T TT T F FF E i識別語句i i的過程 a 規(guī)范歸約 b 算符優(yōu)先分析在算符優(yōu)先分析中 僅研究終結(jié)符之間的優(yōu)先關系 而不考慮非終結(jié)符之間的優(yōu)先關系 但句柄是由終結(jié)符和非終結(jié)符一起構(gòu)成的 所以算符優(yōu)先分析相對來說是非規(guī)范的分析 2020 2 14 50 2 最左素短語定義6 5設有文法G S 其句型的素短語是一個短語 它至少包含一個終結(jié)符 且除自身外不再包含其他素短語 處于句型最左邊的素短語為最左素短語 2020 2 14 51 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F P F P 6 P E 7 P i 其短語有 T T F iT T FTT Fi 最左素短語為 T F 句型 T T F i 在進行最左素短語歸約時 只要能找出產(chǎn)生式 其右部的終結(jié)符與棧頂?shù)娜舾山K結(jié)符有一一對應的關系 當名稱相同 位置也相同時即可進行歸約 由于最左素短語不考慮非終結(jié)符 所以歸約成什么符號無關緊要 句型 N N N i 的歸約過程 3 算符優(yōu)先分析歸約過程的算法 4 算符優(yōu)先分析的優(yōu)缺點算符優(yōu)先分析比規(guī)范歸約要快得多 因為它跳過了許多單非終結(jié)符的歸約 但是 由于忽略了非終結(jié)符在歸約中的作用 它可能會把錯誤的輸入串誤認為是句子算符優(yōu)先文法適用范圍比簡單優(yōu)先文法大得多 許多程序設計語言都可以用它來分析 算符優(yōu)先分析表構(gòu)造簡單 甚至可以用手工構(gòu)造缺點在于有些文法不滿足算符優(yōu)先文法 必須先改寫 有些甚至無法改寫 若終結(jié)符數(shù)目多 優(yōu)先表可能會占有太多空間 2020 2 14 55 6 3 5優(yōu)先函數(shù) 優(yōu)先函數(shù)比優(yōu)先矩陣節(jié)省空間2 n 1 n 1 2優(yōu)先函數(shù) 從終結(jié)符號映射到整數(shù)的函數(shù) 若ab 則f a g b 2020 2 14 56 構(gòu)造優(yōu)先函數(shù) 1 設a是一個終結(jié)符或 對每一個a建立兩個符號結(jié)點fa和ga 2 對任何a和b 若ab 或a b 則從fa畫一箭弧到gb 3 給每個結(jié)點賦一個數(shù) 此數(shù)等于從該點出發(fā)所能到達的結(jié)點 包括該結(jié)點自身在內(nèi) 的個數(shù) 例 優(yōu)先關系矩陣為 優(yōu)先函數(shù) 2020 2 14 58 例 f g i i i是不存在的 所以錯誤檢查能力損失 可通過檢查棧頂和輸入符號a來發(fā)現(xiàn)那些不可比較的情形 2020 2 14 59 6 3 6算符優(yōu)先分析法的局限性 很難避免把錯誤的句子得到正確的歸約例如 下述文法是一個算符優(yōu)先文法 其產(chǎn)生式為 S S D DD D T HH a S T T S S其中VN S D T H VT a S為開始符號 算符優(yōu)先關系矩陣表 用算符優(yōu)先分析法對輸入串 a a 進行分析 不難發(fā)現(xiàn)它可以完全正確地進行歸約 然而 a a 卻不是該文法能推導出的句子 本章小結(jié) 語法分析是編譯程序的核心部分 語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子 程序 目前語法分析常用的方法有自頂向下 自上而下 分析 見第5章 和自底向上 自下而上 分析兩大類 而自底向上分析又可分為算符優(yōu)先分析和LR分析 見第7章 它們的分析都是移進 歸約過程 是自頂向下最右推導的逆過程 但LR分析是規(guī)范歸約 算符優(yōu)先分析不是規(guī)范歸約 它們的區(qū)別在于識別可歸約串的原則