第三章文法和語言-文庫吧資料
2025-08-07 12:51本頁面
【正文】 可以嗎？ 設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 α β是這樣一種結(jié)構(gòu)： α∈ (VN∪ VT)+， β∈ (VN∪ VT)*， 則 G是一個(gè) 0型文法 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?重要的理論結(jié)果： ?0型文法的能力相當(dāng)于圖靈機(jī)（ Turing） ?或者說，任何 0型語言都是遞歸可枚舉的 ?反之，遞歸可枚舉集必定是一個(gè) 0型語言 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 α β均滿足： |β| ≥ |α|，僅僅 S ε除外， 則 文法 G是 1型文法 （ 上下文有關(guān)文法 ） ?例 、 、 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例： 文法 G[S]： S CD Ab bA C aCA Ba aB C bCB Bb bB AD aD C ε BD bD D ε Aa bD L(G)={w|w∈ {a,b}*} 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?有些定義中，將上下文有關(guān)文法的產(chǎn)生式的形式描述為 α1Aα2 α1βα2，其中 α α2和 β都在 V*中， β≠ε， A在 VN中 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 α β均滿足： α是 一個(gè) 非終結(jié)符， β∈ V*，則文法 G是 2型文法 （ 上下文無關(guān)文法 ） 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?有時(shí)將 2型文法的產(chǎn)生式表示為 A β的形式，其中 A∈ VN，也就是用 β取代非終結(jié)符 A時(shí)，與 A所在的上下 文無關(guān)，因此取名為 上下文無關(guān) ?例 、 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 ： 文法 G[S]： S aB|bA A a|aS|bAA B b|bS|aBB 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 A αB或 A α，其中 A和 B都是非終結(jié)符， α∈ VT*，則文法 G是 3型文法 （ 正規(guī)文法 ） ?例 ：文法 G[S]： S 0A|1B|0 A 0A|1B|0S B 1B|1|0 你會忘記我嗎？ 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?4個(gè)文法類的定義是 逐漸增加限制 的，因此，每一種正規(guī) 文法都是上下文無關(guān)的，每一種上下文無關(guān)文法都是上 下文有關(guān)的，而每一種上下文有關(guān)文法都是 0型文法 ?稱 0型文法產(chǎn)生的語言為 0型語言，上下文有關(guān)文法、上 下文無關(guān)文法和正規(guī)文法產(chǎn)生的語言分別稱為上下文有 關(guān)語言、上下文無關(guān)語言和正規(guī)語言 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 文法和語言的形式定義 ?規(guī)則 （重寫規(guī)則、產(chǎn)生式、生成式）： 一個(gè)規(guī)則是一個(gè)二元組 ,通常寫作 α::= β 或 α β ?α稱為規(guī)則的 左部 ， β稱為規(guī)則的 右部 ， (::=)讀作 “ 定義為 ”，這是一條關(guān)于 α的規(guī)則（產(chǎn)生式） 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義 ： 文法 G定義為四元組（ VN， VT， P， S） ?VN ： 非終結(jié)符（語法實(shí)體、變量）集 ?VT ： 終結(jié)符集 ?P： 規(guī)則 （ α β）集合， α∈ (VN∪ VT)*且至少包含 一個(gè)非終結(jié)符， β ∈ (VN∪ VT)* ?VN、 VT、 P是非空有窮集 ?S： 開始符 （識別符），它是一個(gè)非終結(jié)符，至少要在一 條規(guī)則中作為左部出現(xiàn) ?VN∩VT= 216。 (2). ? ? 216。 = 216。 注意 : (1). 216。 (2). | a x | = | x a | = | x | + 1 ( a ∈ ∑ ) 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 3. 符號串的連結(jié)： 設(shè) x 與 y 是字母表 ? 上的兩個(gè)符號串， 把 y 的所有符號相繼寫在 x 的符號之后所得到的符號串 稱為 x 與 y 的連結(jié)，用 x y 表示 注意 : ? | x y | = | x | + | y | ? ? x = x ? = x ? x y ≠ y x ( 一般說來 ) 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 4 .符號串的逆： 設(shè) x 是字母表 ? 上的符號串，其逆為符號串 x 的倒置， 記為 。 符號和符號串 一 .字母表和符號串 可以看成在一個(gè)基本符號集上定義的，按一定規(guī)則 構(gòu)成的一切基本符號串組成的 集合 （符號集）：是一個(gè) 非空 有窮集合 （字符）：字母表中的元素 ：符號的有窮 序列 。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第三章 文法和語言 ?第一節(jié) 文法的直觀概念 ?第二節(jié) 符號和符號串 ?第三節(jié) 文法和語言的形式定義 ?第四節(jié) 文法的類型 ?第五節(jié) 上下文無關(guān)文法及其語法樹 ?第六節(jié) 句型分析 ?第八節(jié) 典型例題及解答 ?第七節(jié) 有關(guān)文法實(shí)用中的一些說明 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 知識結(jié)構(gòu) 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 文法的直觀概念 第三章 方法和語言 ?所謂一個(gè)語言的 語法 是指一組 規(guī)則 ，用它可以形成和產(chǎn)生 一個(gè)合適的程序 ?目前廣泛使用的手段是 上下文無關(guān)文法 ，即用上下文無關(guān)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1