第2章高級語言及其語法描述(編輯修改稿)
2024-11-29 15:20 本頁面
【文章內(nèi)容簡介】 主語 ::=冠詞 形容詞 名詞 冠詞 ::=the 形容詞 ::=big 名詞 ::=elephant | peanut 謂語 ::=動詞 賓語 動詞 ::=ate 賓語 ::=冠詞 名詞 上述推導(dǎo)可寫成 句子 = the big elephant ate the peanut + 說明： (1) 有若干語法成分同時存在時，我們總是從最左的語法成 分進行推導(dǎo)，這稱之為 最左推導(dǎo) ，類似的有 最右推導(dǎo) （一般推 導(dǎo)）。 (2) 從一組產(chǎn)生式可推出不同的句子，如以上產(chǎn)生式還可推 出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它們 在語法上都正確，但在語義上都不正確。 所謂 文法 是在 形式上 對句子結(jié)構(gòu)的定義與描述，而未 涉及 語義 問題。 ：我們用語法樹來描述一個句子的語法結(jié)構(gòu)。 句子 主語 謂語 冠詞 形容詞 名詞 動詞 賓語 冠詞 名詞 The big elephant ate the peanut 語法成分（在形式 語言中又稱“非終 結(jié)符”） 單詞符號（在形 式語言中又稱 “終結(jié)符號” ) 文法和語言的形式定義 定義 1: 文法 G=（ VN， VT， P， Z） VN ：非終結(jié)符號集 VT ：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合 Z：開始符號（識別符號） Z∈ VN V＝ VN∪ VT 稱為文法的字匯表 產(chǎn)生式： U ::? x U ∈ VN, x∈ V* 其中 : ： 產(chǎn)生式是一個有序?qū)?(U, x), 通常寫為 : U ::? x 或 U ? x； | U| = 1 |x| ? 0 ： 出現(xiàn)在產(chǎn)生式的左部 ,且能推出符號或符號串的 那些符號。其全體構(gòu)成非終結(jié)符號集，記為 VN 。 ： 不出現(xiàn)在產(chǎn)生式的左部 ,且不能推出符號或符號串 的那些符號。其全體構(gòu)成終結(jié)符號集，記為 VT 。 P = {無符號整數(shù) → 數(shù)字串 ； 數(shù)字串 → 數(shù)字串 數(shù)字 ； 數(shù)字串 → 數(shù)字 ； 數(shù)字 →0 ； 數(shù)字 →1 ； ………… 數(shù)字 →9 ； } Z = 無符號整數(shù) ； 例：無符號整數(shù)的文法： G[無符號整數(shù) ]=（ VN， VT， P， E） VN＝ {無符號整數(shù) ,數(shù)字串 , 數(shù)字 } VT = {0,1,2,3,……9} 幾點說明 ： 產(chǎn)生式左邊符號構(gòu)成集合 VN，且 Z ∈ VN 有些產(chǎn)生式具有相同的左部，可以合在一起 例、 無符號整數(shù) → 數(shù)字串 ； 數(shù)字串 → 數(shù)字串 數(shù)字 | 數(shù)字 ； 數(shù)字 →0 | 1 | 2 | 3 | …… | 9 文法的 BNF表示 給定一個 文法，實際只需給出產(chǎn)生式集合，并指定識別符號 例、 G[無符號整數(shù) ] 無符號整數(shù) → 數(shù)字串 ； 數(shù)字串 → 數(shù)字串 數(shù)字 | 數(shù)字 ； 數(shù)字 →0 | 1 | 2 | 3 | …… | 9 推導(dǎo)與歸約 定義 2： 直接推導(dǎo)：文法 G： v＝ x Uy， w＝ xuy, 其中 x、 y ∈ V* ， U∈ VN, u ∈ V*, 若 U ::? u∈ P，則 v ?w。 若 x＝ y＝ ε，有 U ::? u，則 U ? u 換句話說， x和 y是符號串，若使用一次產(chǎn)生式可以從 x變換出 y，則稱 x直接推導(dǎo)出 y(或者說 y是 x的直接推導(dǎo)），記為 x? y。 當符號串已沒有非終結(jié)符號時，推導(dǎo)就必須終止。因為 終結(jié)符不可能出現(xiàn)在產(chǎn)生式左部，所以將在產(chǎn)生式左部出現(xiàn)的 符號稱為非終結(jié)符號。 例如： G[N]： N → ND | D D → 0| 1| 2| 3| 4| 5| 6| 7| 8| 9 N ND NDD ND9 N09 D09 109 (6) == == (1) == (3) (4) == == (2) (5) == ＋ N==109 定義 3： +推導(dǎo)： x和 y是符號串，若使用若干次產(chǎn)生式可以從 x變換出 y，則稱 x推導(dǎo)出 y(或者說 y是 x的推導(dǎo)），記為 x? y。 ＋ N ND NDD ND9 N09 D09 109 (6) == == (1) == (3) (4) == == (2) (5) == 例： 則： 定義 4： *推導(dǎo)： x和 y是符號串，若使用 0次或若干次產(chǎn)生式可以從 x變換出 y，則稱 x*推導(dǎo)出 y(或者說 y是 x的 *推導(dǎo)），記為 x? y。 * * N==109 則： * N==N 或者說 ：若有直接推導(dǎo)序列：x=U0==U1==U2==……==U n=y,則 x==y 。 + 直觀意義：規(guī)范推導(dǎo)＝最右推導(dǎo) 定義 5： 最 右 推導(dǎo)：若符號串 α 中有兩個以上的非終結(jié)符時，對推導(dǎo)的每一步堅持把 α 中的最右 非終結(jié)符進行替換，稱為最 右 推導(dǎo)。 最 左 推導(dǎo)：若符號串 α 中有兩個以上的非終結(jié)符時，對推導(dǎo)的每一步堅持把 α 中的最左 非終結(jié)符進行替換，稱為最 左 推導(dǎo)。 定義 6： 推導(dǎo)的逆過程稱之為歸約。 例： x ==y,可稱為 x直接推導(dǎo)出 y，也可稱為 y直接歸約出 x。 ＋ x ==y ,可稱為 x推導(dǎo)出 y，也可稱為 y歸約出 x。 語言的形式定義
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1