[理學]第四章2 自下而上語法分析-全文預覽
【正文】 .aQb... (在同一產(chǎn)生式中 ) ② a b,G中有 P...aR...的產(chǎn)生式 ,且 R=b...或R=Qb... (注意 ab相鄰 ) ③ a b,G中有 P...Rb...的產(chǎn)生式 ,且 R=...a或R=...aQ (注意 ab相鄰 ) 算符優(yōu)先文法的定義 + + + + 例： E→E+E | E*E | (E) | i 證明不是算符優(yōu)先文法 。 (3) a優(yōu)先性低于 b ，記作 a b。 ? 各種分析方法中處理沖突的技術不同 算符優(yōu)先分析 ? 算符優(yōu)先分析法的思想源于表達式的分析，即利用相鄰終結符號之間的關系來尋找可歸約串。 在規(guī)范歸約中， 關鍵問題就轉化為 如何識別句柄 ? 回到上例用 句柄 對句子 abbcde進行歸約有： ? 用句柄對句子進行歸約的過程與用移進 歸約過程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。 – 由于總是將句型的最左邊的可歸約串替換成非終結符，該方法通常得到是最右推導。 ? ―移進 —歸約”語法分析小結： – 從輸入串的開始依次讀入單詞 (移進 棧中 ) 。 ? 2) 歸約 ： 當棧頂符號串形成一個可歸約的串（如： 句柄 ）時，直接進行歸約，即用產(chǎn)生式左側的非終結符替換棧頂?shù)木浔?。} while (在棧里符號串中找到一個可歸約串 )； 歸約可歸約串 while （文法開始符號出現(xiàn)在棧頂或者發(fā)現(xiàn)錯誤）； ? 分析成功的條件 ：棧頂為文法符號，輸入串為空。 – 與最左歸約 (規(guī)范歸約 )對應，得規(guī)范句型。 是推導 的逆過程 。第四章 (2) 自下向上語法分析 本章要求 : 1. 掌握自下向上語法分析的基本思想和基本概念 2. 了解算符優(yōu)先語法分析；求 FIRSTVT集和LASTVT集，構造算符優(yōu)先關系表；能運用算符優(yōu)先分析方法進行表達式分析（選學） 3. 掌握句柄的定義與判定 4. 理解規(guī)范歸約的過程和 LR分析過程中的實現(xiàn) 5. 掌握 LR語法分析的實現(xiàn)過程 回顧 : 歸約和推導的概念 例 S ? aABe A ? Abc | b B ? d 用歸約的方法對句子 abbcde進行語法分析 。 – 從 語法樹的角度 看：從語法樹的 樹葉 開始 ， 逐步向上歸約 構造分析樹 ， 直到形成根結點 。 ? 最右推導 (Rightmost Derive) – 每次推導都替換當前句型的最右邊的非終結符。 a b a A a b A a c b A a A a d A a B A a e B A a S 1 移進a 2 移進b 3 歸約2 4 移進b 5 移進c 6 歸約3 7 移進d 8 歸約4 9 移進e 10 歸約1 ―移進 歸約”分析法中棧的使用 ? 移進 歸約分析器使用了一個符號棧和一個輸入緩沖區(qū) ? 句型表示 a1 a2 a3 …… … X1 X2 X3 ―移進 歸約” 分析程序 輸出 棧(存放句型前綴) 輸入串 符號棧內(nèi)容 + 輸入緩沖區(qū)內(nèi)容 ＝ 當前句型 一般形式： 符號棧的內(nèi)容 剩余輸入串 初態(tài)： 輸入串 終態(tài)： S ? 分析器結構 ? 3. 過程描述： do{ do { 將輸入串最左邊的符號移入棧內(nèi) 。 分析器的四種動作 ? 1) 移進 ： 讀入下一個輸入符號并把它下推進棧。 ? 注意：決定移進和歸約的依據(jù)是什么？ 棧頂是否出現(xiàn)了可歸約的符號串。 – 若最終能歸約成文法的開始符號，則分析成功（ 接受 ）；否則 出錯 。 規(guī)范歸約：使用 句柄 來定義可歸約串 算符優(yōu)先：使用 最左素短語 來定義可歸約串 ? 自下而上語法分析主要有以下三種方法： ① 簡單優(yōu)先分析法 (規(guī)范歸約 )—— 文法按 一定原則規(guī)定文法符號的優(yōu)先關系 ②算符優(yōu)先分析法 (不規(guī)范歸約 )—— 規(guī)定 算符 之間的優(yōu)先關系 ③ LR分析法（規(guī)范歸約） —— LR(0)、LR(1)、 SLR(1)和 LALR(1) 語法分析樹的生成演示 a b b c d e A A B S A→b A→Abc B→d S→aABe (1)S ? aABe (2)A ? b (3)A ? Abc (4)B ? d S ? aABe ? aAde ? aAbcde ? abbcde 規(guī)范歸約相關概念復習 ? 有文法 G，開始符號為 S, 如果有 S=xβ y,則 xβ y是文法 G的 句型 ， x,y是任意的符
教學課件相關推薦
鄂ICP備17016276號-1