形式語(yǔ)言概論ppt課件(編輯修改稿)
2024-11-30 21:14 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 【 例 1】 設(shè)有文法 G[E]： E→E+T ∣ ET∣ T T→T*F ∣ T/F∣ F F→ （ E） ∣ i 給出句型 (T+i2)*i1F的語(yǔ)法樹(shù) 文法和語(yǔ)言的一些特性 無(wú)用非終結(jié)符號(hào) 如果文法的某個(gè)非終結(jié)符不出現(xiàn)在文法的任何一個(gè)句型中，并且不能從它推導(dǎo)出終結(jié)符號(hào)串，則稱(chēng)該非終結(jié)符為無(wú)用非終結(jié)符號(hào)。 (P30例 ) 不可達(dá)文法符號(hào) 如果一個(gè)非終結(jié)符（非識(shí)別符號(hào)）不出現(xiàn)在文法的任何一條產(chǎn)生式的右部，則稱(chēng)該非終結(jié)符為不可達(dá)文法符號(hào)。 文法中的任意非終結(jié)符 A應(yīng)滿(mǎn)足如下兩個(gè)條件 : (1)A必須在文法的某個(gè)句型中出現(xiàn)。 (2)必須能從 A推導(dǎo)出終結(jié)符號(hào)串。 可空非終結(jié)符 2型文法的產(chǎn)生式要求以下形式： A→ ? 其中 ， A?VN， ??(VN∪V T)+。 對(duì) 2型文法可進(jìn)行擴(kuò)充 ， 令 ??(VN∪V T)*， 允許有以下形式的產(chǎn)生式： A→ ? 此產(chǎn)生式稱(chēng)為空產(chǎn)生式， A稱(chēng)為可空非終結(jié)符。 最左、最右推導(dǎo)和規(guī)范推導(dǎo)（ 1） 定義 在 xUy?xuy直接推導(dǎo)中，若 x?VT*， U?VN 即 U是符號(hào)串 xUy中最左非終結(jié)符，則稱(chēng)此直接推導(dǎo)為 最左直接推導(dǎo)。若一個(gè)推導(dǎo)的每一步直接推導(dǎo)都是最左直接推導(dǎo)，那么此推導(dǎo)稱(chēng)為最左推導(dǎo)。 定義 在 xUy::=xuy直接推導(dǎo)中， y?VT*,U?VN，即 U是符號(hào)串 xUy中最右非終結(jié)符，則稱(chēng)此直接推導(dǎo)為最右直接推導(dǎo)。若一個(gè)推導(dǎo)的每一步直接推導(dǎo)都是最右直接推導(dǎo)，則稱(chēng)此推導(dǎo)為最右推導(dǎo)。 最右直接推導(dǎo)又稱(chēng)為規(guī)范直接推導(dǎo)，最右推導(dǎo)又稱(chēng)為規(guī)范推導(dǎo)。 最左、最右推導(dǎo)和規(guī)范推導(dǎo)（ 2） 定義 假定 x1?x2?… ?xn是一個(gè)最左推導(dǎo)，我們稱(chēng)序列 Xn ， Xn1， … X1 是一個(gè)最右歸約。 定義 假定 x1?x2?… ?xn是一個(gè)最右推導(dǎo)，我們稱(chēng)序列 Xn ， Xn1， … X1 是一個(gè)最 左歸約 。 最左推導(dǎo)的逆過(guò)程是最右歸約，最右推導(dǎo)的逆過(guò)程是最左歸約。 二義性（ 1） 定義 一個(gè)文法，如果它的一個(gè)句子有兩棵或兩棵以上的語(yǔ)法樹(shù)，則稱(chēng)此句子具有二義性。如果一個(gè)文法含有二義性的句子，則該文法具有二義性。 例如：表達(dá)式的文法 。 二義性的文法將給編譯程序的執(zhí)行帶來(lái)問(wèn)題。對(duì)于二義性文法的句子，當(dāng)編譯程序?qū)λ慕Y(jié)構(gòu)進(jìn)行語(yǔ)法分析時(shí)，就會(huì)產(chǎn)生兩種甚至更多種不同的解釋。由于語(yǔ)法結(jié)構(gòu)上的不確定性，將必然會(huì)導(dǎo)致語(yǔ)義處理上的不確定性。對(duì)于二義性的文法我們可以利用文法的等價(jià)性來(lái)消除文法的二義性，以利于語(yǔ)法分析的進(jìn)行。 二義性（ 2） 例：定義某種程序設(shè)計(jì)語(yǔ)言語(yǔ)句的文法，證明是否有二義性并消除之。 S→if b S ∣ if b S else S∣ A( 其他語(yǔ)句 ) 分析 該文法的句子 if b if b A else A 對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)。 改寫(xiě)文法： （ 1）不改變現(xiàn)有的規(guī)則，加進(jìn)一項(xiàng)語(yǔ)法規(guī)定。 else與前面最近的不帶 else的 if相對(duì)應(yīng)。 （ 2）改寫(xiě)文法 G 為 G′： S→S1 ∣ S2 S1→if b S1 else S2 ∣ A S2→if b S ∣ if b S1 else S2 規(guī)定 if 和 else之間只能是 ifelse語(yǔ)句或其他語(yǔ)句。 二義性（ 3） 文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。 文法的二義性不能用算法來(lái)判定。 分析方法簡(jiǎn)介 一個(gè)分析器或分析自動(dòng)機(jī)是這樣一種系統(tǒng)，它能夠根據(jù)給定的文法 G，構(gòu)造語(yǔ)言 L(G)的任意推導(dǎo)。分析也可看作是語(yǔ)法樹(shù)的構(gòu)造過(guò)程。 分析的方法很多，可歸納為兩類(lèi)，一類(lèi)是自上而下分析方法，另一類(lèi)是自下而上分析方法。 自上而下分析方法的基本思想是從文法的開(kāi)始符號(hào)出發(fā)，利用其中的產(chǎn)生式，逐步推導(dǎo)出待分析的符號(hào)串。如果能推導(dǎo)出這個(gè)符號(hào)串，則表明此符號(hào)串是該文法的一個(gè)句型或句子，否則便不是。 確定的自上而下分析方法（ 1） 當(dāng)文法的某一個(gè)非終結(jié)符有幾條產(chǎn)生式 、 而且每條產(chǎn)生式右部首符號(hào)都是終結(jié)符時(shí) ， 應(yīng)保證它們是互不相同的終結(jié)符 。 例 設(shè)文法 G18[S]： S→aBc ?bCd B→eB ?f C→dC ?c 試檢查符號(hào)串 aefc是不是該文法的句子。 確定的自上而下分析方法（ 2） 上例推導(dǎo)過(guò)程： S→aBc ， S?aBc ； B→eB ， S?aBc?aeBc ； B→f ， S?aBc?aeBc?aefc ； 該例屬確定的自上而下分析方法。 自下而上分析方法 自下而上分析方法的基本思想是從待檢查的符號(hào)串出發(fā)，看最終是否能歸約（推導(dǎo)的逆過(guò)程）到文法的識(shí)別符號(hào)。如果能歸約到文法的識(shí)別符號(hào)，則表明此待檢查的符號(hào)串是該文法的一個(gè)句型或句子，否則便不是。 文法在內(nèi)存中的表示 用語(yǔ)法圖的表格結(jié)構(gòu)表示文法。一個(gè)文法的語(yǔ)法圖由該文法所有非終結(jié)符號(hào)的定義圖組成。每個(gè)非終結(jié)符號(hào)的定義圖是一個(gè)結(jié)構(gòu)型數(shù)據(jù)。 在自上而下分析方法中，用這種語(yǔ)法圖表示文法有利于消除左遞歸，也有助于提取左因子。 aI 7F4C0z) vamp。s!pXmUjRf OcK9H6E2B+y( u%rZoWlThQeNbJ8G4D1Aw*t$qYnVjSgPdLaI 7F
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1