上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)(ppt28)-經(jīng)營(yíng)管理(編輯修改稿)
2024-09-20 21:38 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 (1) 12 軟件教研室 徐慧英 呂振洪 來(lái)自 中國(guó)最大的資料庫(kù)下載 文法和語(yǔ)言 自上而下分析法的缺陷 關(guān)鍵： 回溯問(wèn)題 ；（ ∵ 其分析過(guò)程是一種試探過(guò)程） 回溯問(wèn)題 是從各種可能的候選式中任選一個(gè)，進(jìn)行推導(dǎo)后發(fā)現(xiàn)該候選式是錯(cuò)誤的，則退回去重新選擇候選式的方式。例如上例中的 (3)。 S x A y (3) — 選用第 1個(gè)候選式 * 回溯的產(chǎn)生使算法代價(jià)極低，效率很低。關(guān)于解決回溯問(wèn)題將在第 5章中介紹。 * 13 軟件教研室 徐慧英 呂振洪 來(lái)自 中國(guó)最大的資料庫(kù)下載 自下而上的分析法 文法和語(yǔ)言 基本思想：從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直至歸約到文法的開(kāi)始符號(hào)。即從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約”，直到根結(jié)。 歸約：若 V= γαδ， W=γβδ， α → β是文法的產(chǎn)生式，如有V=W，則 W直接歸約到 V。 例： 文法 G[S]： (1)S→ aAcBe (2) A→ b (3)A→ Ab (4) B→ d 識(shí)別 abbcde是否為文法 S的一個(gè)句子。 解題思想：掃描 abbcde，從中找出一個(gè)子串，該子串與某一產(chǎn)生式的右部相匹配。 14 軟件教研室 徐慧英 呂振洪 來(lái)自 中國(guó)最大的資料庫(kù)下載 自下而上分析法舉例 文法和語(yǔ)言 解： a b b c d e (1) a b b c d e A (2) a b b c d e A A (3) a b b c d e A A (4) B a b b c d e A A (5) B S 15 軟件教研室 徐慧英 呂振洪 來(lái)自 中國(guó)最大的資料庫(kù)下載 自下而上分析法存在的問(wèn)題 文法和語(yǔ)言 可歸約串的問(wèn)題 ；（ ∵ 該分析的每一步就是從當(dāng)前串中找一個(gè)子串（稱“可歸約串”），將它歸約到某個(gè)非終結(jié)符號(hào)） 自下而上分析法的 關(guān)鍵 就是找哪個(gè)子串是“可歸約串”，哪個(gè)不是“可歸約串”。例如上例中的 (3) a b b c d e A A (3) — 用產(chǎn)生式 (2)而非 (3)，則不能歸約到 S 因此必須精確定義“可歸約串”，事實(shí)上存在著種種不同的方法刻畫(huà)“可歸約串”，對(duì)這個(gè)概念的不同定義，形成了不同的自下而上的分析法。在“規(guī)范歸約”的分析中，用“句柄”來(lái)刻畫(huà)“可歸約串”。 來(lái)自 中國(guó)最大的資料庫(kù)下載 16 軟件教研室 徐慧英 呂振洪 來(lái)自 中國(guó)最大的資料庫(kù)下載 短語(yǔ)、直接短語(yǔ)、句柄 文法和語(yǔ)言 短語(yǔ)： 令文法 G， 開(kāi)始符號(hào)為 S， αβδ是 G的句型 （即 S αβδ），如果 S αAδ且 A β，則稱 β是句型 αβδ相對(duì)于非終結(jié)符 A的短語(yǔ)。 直接短語(yǔ) 如短語(yǔ)中有 A=β，則稱 β是句型相對(duì)于規(guī)則 A→ β的直接短語(yǔ)。 句柄 一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1