第三章文法和語言(編輯修改稿)
2025-08-28 12:51 本頁面
【文章內容簡介】 ：專業(yè)的計算機學習網(wǎng)站 ?定義 ： 若有 S x，則稱 x是文法 G[S]的 句型 ，若 x僅 由終結符組成，則稱 x為 G[S]的 句子 * 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?定義 ： 文法 G所產生的語言定義為集合 L(G)=｛ x|S x，其中 S為文法識別符號，且 x∈ VT*｝ ?文法描述的語言是該文法一切句子的集合 ?例： G： S 0S1， S 01 L(G)={0n1n|n≥1} * 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 例 文法文法 G[S]： （ 1） S aSBE （ 2） S aBE （ 3） EB BE （ 4） aB ab （ 5） bB bb （ 6） bE be （ 7） eE ee L（ G） ={ anbnen | n≥1 } 思考： a4b4e4怎么推導？ 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?定義 ： 若 L(G1)＝ L(G2)，則稱文法 G1和 G2是等價的 ?例如文法 G[A]： ?A 0R ?A 01 ?R A1 和文法 G[S]： ? S 0S1 ? S 01 ?等價 L(G)={0n1n|n≥1} 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 167。 文法的類型 ?喬姆斯基 (Chomsky)于 1956年建立形式語言的描述 ?他把文法分成： 0型、 1型、 2型、 3型 ?四個文法類的定義是逐漸增加限制的 0型 1型 2型 3型 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?設 G＝（ VN， VT， P， S），如果它的 每個 產生式 α β是這樣一種結構： α∈ (VN∪ VT)*且 α至少包 含一個 非終結符， β∈ (VN∪ VT)*，則 G是一個 0型文法 （ 短語文法、無限制文法 ） 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?思考：這樣定義可以嗎？ 設 G＝（ VN， VT， P， S），如果它的 每個 產生式 α β是這樣一種結構： α∈ (VN∪ VT)+， β∈ (VN∪ VT)*， 則 G是一個 0型文法 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?重要的理論結果： ?0型文法的能力相當于圖靈機（ Turing） ?或者說，任何 0型語言都是遞歸可枚舉的 ?反之，遞歸可枚舉集必定是一個 0型語言 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?設 G＝（ VN， VT， P， S），如果它的 每個 產生式 α β均滿足： |β| ≥ |α|，僅僅 S ε除外， 則 文法 G是 1型文法 （ 上下文有關文法 ） ?例 、 、 盛威網(wǎng)：專業(yè)的計算機學習網(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è)的計算機學習網(wǎng)站 ?有些定義中，將上下文有關文法的產生式的形式描述為 α1Aα2 α1βα2，其中 α α2和 β都在 V*中， β≠ε， A在 VN中 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?設 G＝（ VN， VT， P， S），如果它的 每個 產生式 α β均滿足： α是 一個 非終結符， β∈ V*，則文法 G是 2型文法 （ 上下文無關文法 ） 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?有時將 2型文法的產生式表示為 A β的形式，其中 A∈ VN，也就是用 β取代非終結符 A時，與 A所在的上下 文無關，因此取名為 上下文無關 ?例 、 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 ： 文法 G[S]： S aB|bA A a|aS|bAA B b|bS|aBB 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?設 G＝（ VN， VT， P， S），如果它的 每個 產生式 A αB或 A α，其中 A和 B都是非終結符， α∈ VT*，則文法 G是 3型文法 （ 正規(guī)文法 ） ?例 ：文法 G[S]： S 0A|1B|0 A 0A|1B|0S B 1B|1|0 你會忘記我嗎？ 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?4個文法類的定義是 逐漸增加限制 的，因此，每一種正規(guī) 文法都是上下文無關的，每一種上下文無關文法都是上 下文有關的，而每一種上下文有關文法都是 0型文法 ?稱 0型文法產生的語言為 0型語言，上下文有關文法、上 下文無關文法和正規(guī)文法產生的語言分別稱為上下文有 關語言、上下文無關語言和正規(guī)語言 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 167。 上下文無關文法及其語法樹 ?上下文無關文法有足夠的能力描述現(xiàn)今程序設計語言的 語法結構，比如描述算術表達式、描述各種語句等 ?例 ： 文法 G=({E},{+,*,i,(,)},P,E)其中 P為： E i E E+E E E*E E (E) ?條件語句 if條件 then語句 | if條件 then語句 else 語句 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?給定文法 G=（ VN， VT， P， S），對于 G的任何句型都 能構造與之關聯(lián)的語法樹（推導樹、語法分析樹、分 析樹）。 這棵樹滿足下列 4個條件： （ 1）每個結點都有一個 V中的符號作標記 （ 2）根的標記是開始符號 S （ 3）若一結點 n至少有一個它自己除外的子孫，并且有標記
環(huán)評公示相關推薦
鄂ICP備17016276號-1