[理學(xué)]第四章2自下而上語法分析(已修改)
2024-10-28 22:57 本頁面
【正文】 第四章 (2) 自下向上語法分析 本章要求 : 1. 掌握自下向上語法分析的基本思想和基本概念 2. 了解算符優(yōu)先語法分析；求 FIRSTVT集和LASTVT集，構(gòu)造算符優(yōu)先關(guān)系表；能運用算符優(yōu)先分析方法進行表達式分析（選學(xué)） 3. 掌握句柄的定義與判定 4. 理解規(guī)范歸約的過程和 LR分析過程中的實現(xiàn) 5. 掌握 LR語法分析的實現(xiàn)過程 回顧 : 歸約和推導(dǎo)的概念 例 S ? aABe A ? Abc | b B ? d 用歸約的方法對句子 abbcde進行語法分析 。 例 S ? aABe A ? Abc | b B ? d abbcde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAbcde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe S 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe S S ?rm aABe ?rm aAde ?rm aAbcde ?rm abbcde 自下而上的語法分析的一般過程 ? 實現(xiàn)思想 – 從輸入符號串開始 ， 從左到右進行掃描 ， 將輸入符號逐個移入一個棧中 ， 邊移入邊分析 ， 一旦棧頂符號串形成某個產(chǎn)生式的右部時 ， 就用該產(chǎn)生式的左部非終結(jié)符代替 ， 稱為 歸約 。 重復(fù)這一過程 ， 直到歸約到棧中只剩下文法的開始符號時 ， 則分析成功 ， 稱為 “ 移進 歸約 ”方法 。 – 從 語法樹的角度 看：從語法樹的 樹葉 開始 ， 逐步向上歸約 構(gòu)造分析樹 ， 直到形成根結(jié)點 。 是推導(dǎo) 的逆過程 。 ? 最左推導(dǎo) (Leftmost Derive) – 每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符。 – 與最右歸約對應(yīng)。 ? 最右推導(dǎo) (Rightmost Derive) – 每次推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符。 – 與最左歸約 (規(guī)范歸約 )對應(yīng)，得規(guī)范句型。 例： 設(shè)有文法 G[S]： (1) S ? aABe (2) A ? b (3) A ? Abc (4) B ? d 使用最右推導(dǎo)： 因為 S aABe aAde aAbcde abbcde，所以 abbcde是文法 G的句子。 )1(rm?)2(rm? )3(rm?)4(rm? 步驟 動作 (1)S ?aABe (2)A ?b (3)A ?Abc (4)B ?d 最左歸約過程是最右推導(dǎo)的逆過程， 對輸入串 abbcde的移進 —歸約過程如下： 該分析過程反復(fù)執(zhí)行“移進”和“歸約”兩個動作，直到棧中只有開始符號為止。 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)容 ＝ 當(dāng)前句型 一般形式： 符號棧的內(nèi)容 剩余輸入串 初態(tài)： 輸入串 終態(tài)： S ? 分析器結(jié)構(gòu) ? 3. 過程描述： do{ do { 將輸入串最左邊的符號移入棧內(nèi) 。}
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1