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