文章轉自：https://zh.wikipedia.org/wiki/喬姆斯基譜系

文章目錄

• • • • 喬姆斯基體系的四個層次
      • 四種語言類的包含關系
      • 主要特點

---

喬姆斯基體系的四個層次

喬姆斯基體系是計算機科學中刻畫形式文法表達能力的一個分類譜系，是由語言學家諾姆·喬姆斯基于1956年提出的。它包括四個層次：

---

0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言?？杀粓D靈機識別的語言是指能夠使圖靈機停機的字符串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，后者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。

---

1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這里的A 是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字符串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。

---

2-型文法（上下文無關文法）生成上下文無關語言。這種文法的產生式規則取如 A -> γ 一樣的形式。這里的A 是非終結符號，γ 是包含非終結符號與終結符號的字符串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程序設計語言的語法提供了理論基礎。

---

3-型文法（正規文法）生成正則語言。這種文法要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個終結符號后隨一個非終結符號；如果所有產生式的右側都不含初始符號 S ，規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受，也可以通過正則表達式來獲得。正則語言通常用來定義檢索模式或者程序設計語言中的詞法結構。

---

四種語言類的包含關系

正則語言類包含于上下文無關語言類，

上下文無關語言類包含于上下文相關語言類，

上下文相關語言類包含于遞歸可枚舉語言類。
.
這里的包含都是集合的真包含關系，也就是說：存在遞歸可枚舉語言不屬于上下文相關語言類，存在上下文相關語言不屬于上下文無關語言類，存在上下文無關語言不屬于正則語言類。

主要特點

下表總結了上述四種類型的文法的主要特點：

文法語言自動機產生式規則中文解釋

0-型	遞歸可枚舉語言	圖靈機	α -> β（無限制）	a->b 產生式左邊a至少含有一個非終結符
1-型	上下文相關語言	線性有界非確定圖靈機	αAβ -> αγβ	在0型基礎上，a->b 產生式右側的長度越來越長。
2-型	上下文無關語言	非確定下推自動機	A -> γ	在1型基礎上，a->b左側為一個非終結符。
3-型	正則語言	有限狀態自動機	A -> aB A -> a	在2型基礎上，a->b 右側的形式為：A->cB 或A->c （僅此兩種形式）AB為非終結符

總結

以上是生活随笔為你收集整理的编译原理笔记 - 文法知识的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。