資源描述：
《編譯原理實用教程教學課件楊德芳第5章 自底向上優(yōu)先分析技術.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第5章自底向上優(yōu)先分析技術本章學習目標自頂向下分析法是從文法的識別符開始，試圖推導出輸入符號串；自底向上分析方法與自頂向下的分析方法完全相反，它從輸入符號串出發(fā)，試圖歸約到文法的識別符。本章要點：自頂向下分析法的基本原理簡單優(yōu)先分析技術算符優(yōu)先分析法優(yōu)先函數(shù)5.1自底向上分析方法從語法分析的角度考慮，自底向上的語法分析過程就是以輸入符號串為語法樹的末端結(jié)點符號串，試圖向著根結(jié)點方向向上構造語法樹，使識別符號正是語法樹的根結(jié)點。5.1.1自底向上分析的基本思想基本思想是：對輸入符號串自左向右進行掃描，并將輸入符逐個移進一個后進先出的棧中，邊移進邊分析，一旦棧頂符號串形成某個句型的句
2、柄或可歸約串，就用該產(chǎn)生式的左部非終結(jié)符代替相應右部的文法符號串，稱這一步為歸約。重復這一過程直到歸約到棧中只剩文法的開始符號則為分析成功，就確認該輸入串為文法的句子。例5.1給出文法A?aBbB?Bb
3、b給定某個符號串“abbb”，判定該輸入串是否合法。步驟分析棧句柄輸入串動作1#abbb#移進2#abbb#移進3#abbbb#用B?b歸約4#aBbb#移進5#aBbBbb#用B?Bb歸約6#aBb#移進7#aBbaBb#用A?aBb歸約8#A#接受abB（a）abBbB（b）AabBbBb（c）圖5-1語法樹的構造在上例中的移進—歸約過程中的第7步中，棧頂中出現(xiàn)的符號可以認為
4、是Bb或aBb,在歸約時是用Bb還是aBb，就要作出選擇，如果選擇Bb，則歸約的結(jié)果是aA，aA就不能再歸約，必須退回重新選擇，選擇aBb作為可歸約串。由此可見，在“移進—歸約”過程中，選擇哪一個符號串進行歸約是至關重要的。對于這個可歸約串，在不同的語法分析過程中有不同的稱呼，在簡單優(yōu)先分析中稱為“句柄”，在算符優(yōu)先分析中稱為“素短語”。5.1.2移進—歸約方法一個移進—歸約分析器設置一個符號棧和一個輸入緩沖區(qū)。當輸入符號串為?，分析開始時，棧和輸入緩沖區(qū)的格式為：符號棧的棧底為#，輸入符號串為?#，其中#作為輸入串的結(jié)束符。對?進行分析時，將?的符號從左到右逐個移進符號棧，一旦
5、棧頂符號串與某一個產(chǎn)生式右部相匹配成為一個可歸約串時，則將此符號串歸約為一個非終結(jié)符，這個非終結(jié)符是該產(chǎn)生式的左部符號，當棧頂又形成一個可歸約串時，則又可將此符號串歸約為某個產(chǎn)生式左部非終結(jié)符，?的符號繼續(xù)逐個移進符號棧。重復這個過程，將出現(xiàn)如下格式：符號棧的棧底為#Z，輸入符號串為#。例5.2設文法為Z?ABA?aAb
6、abB?bB
7、c對于輸入符號串a(chǎn)abbcc的分析過程如表5-2所示的移進歸約過程，移進—歸約過程用算法實現(xiàn)的流程圖見圖5-2所示。：步驟符號棧輸入符號棧操作1#aabbc#2#aabbbc#移進3#aabbbc#移進4#aabbbc#移進5#aAbbc#歸約6#
8、aAbbc#移進7#Abc#歸約8#Abc#移進9#Abc#移進10#AbB#歸約11#AB#歸約12#Z#歸約順序掃描輸入符號并依次移進棧棧頂部的符號串是否構成一句柄？YN進行一次歸約輸入串掃描完否？noY棧中僅有開始符號？noerror輸入串合法，報告分析報告出口圖5-2移進-歸約過程5.2簡單優(yōu)先分析技術自底向上優(yōu)先分析分為簡單優(yōu)先分析法和算符優(yōu)先分析法兩大類。簡單優(yōu)先分析法的基本思想是對一個文法按一定的規(guī)則求出該文法所有的符號包括終結(jié)符和非終結(jié)符之間的優(yōu)先關系，按照這種關系確定歸約過程中的句柄，它的歸約實際上是一種規(guī)范歸約。而算符優(yōu)先分析的基本思想則是只規(guī)定算符之間的優(yōu)先
9、關系，也就是只考慮終結(jié)符之間的優(yōu)先關系，由于算符優(yōu)先分析不考慮非終結(jié)符之間優(yōu)先關系，在歸約過程中只要找到可歸約串就歸約，并不考慮歸約到哪個非終結(jié)符名，因而算符優(yōu)先歸約不是規(guī)范歸約。說明>代表優(yōu)先級高于<代表優(yōu)先級低于=代表優(yōu)先級低于簡單優(yōu)先分析準確、規(guī)范，但分析效率較低，實際價值不大，而算符優(yōu)先分析則相反，它不是規(guī)范歸約，但分析速度快，適應于表達式的分析。下面我們重點講述簡單算符優(yōu)先分析技術，在下一節(jié)介紹算符優(yōu)先分析法。簡單優(yōu)先分析法是按照文法符號的優(yōu)先關系確定句柄，包括任意兩個文法符號之間的優(yōu)先關系、如何構造優(yōu)先關系表，如何進行語法判斷和編寫語法分析程序。5.2.1優(yōu)先關系在講
10、述算符優(yōu)先分析之前，先介紹一種關系，稱之為優(yōu)先關系。設X和Y為文法G中的符號，可以是終結(jié)符或非終結(jié)符。在簡單優(yōu)先分析方法中，可以定義三種簡單優(yōu)先關系。（1）優(yōu)先性等于X＝Y(jié)表示X和Y的優(yōu)先關系相等。滿足優(yōu)先關系等于的定義為：當且僅當G存在產(chǎn)生式規(guī)則即A??XY?。（2）優(yōu)先性低于X+Y?。（3）優(yōu)先性高于X>Y表示X的優(yōu)先性比Y的優(yōu)先性高。當且僅當在G中存在產(chǎn)生式規(guī)則即A??BD?，且B=>+?
