Chomsky文法分类

亦凉 2022-03-26 10:12 203阅读 0赞

# Chomsky文法分类体系 #

### 文章目录 ###

*  Chomsky文法分类体系
 *   *  0型文法(Type-0 Grammar)
     *  1型文法(Type-1 Grammar)
     *  2型文法(Type-2 Grammar)
     *  3型文法(Type-3 Grammar)
 *  四种文法之间的关系

## 0型文法(Type-0 Grammar) ##

α → β \\alpha \\rightarrow\{\\beta\} α→β  
**无限制文法**/**短语结构文法**

∀ α → β ∈ P \\forall \\alpha \\rightarrow \\beta \\in P ∀α→β∈P， α \\alpha α中至少包含1个非终结符。

由**0型文法**生成的语言称为**0型语言**。

## 1型文法(Type-1 Grammar) ##

α → β \\alpha \\rightarrow\{\\beta\} α→β

**上下文有关文法(Context-Sensitive Grammar)**：  
7

*   ∀ α → β ∈ P , ∣ α ∣ ≤ ∣ β ∣ \\forall \\alpha \\rightarrow\{\\beta\} \\in P,|\\alpha| \\le |\\beta| ∀α→β∈P,∣α∣≤∣β∣
 *  产生式的一般形式： α 1 A α 2 → α 1 β α 2 ( β ≠ ϵ ) \\alpha\_1 A\\alpha\_2 \\rightarrow\{\\alpha\_1\\beta \\alpha\_2\} (\\beta \\ne \\epsilon) α1Aα2→α1βα2(β̸=ϵ)
 *  **由上下文有关文法（1型文法）G产生的语言L(G)，称为1型语言（上下文有关语言**）。

## 2型文法(Type-2 Grammar) ##

α → β \\alpha \\rightarrow\{\\beta\} α→β

**上下文无关文法（Context-Free Grammar）**：

*   ∀ α → β ∈ P , a ∈ V N \\forall \\alpha \\rightarrow\{\\beta\} \\in P, a \\in V\_N ∀α→β∈P,a∈VN(产生式的左部一定要是非终结符)
 *  产生式的一般形式： A → β A \\rightarrow\{\\beta\} A→β

例如：

1.   S → L ∣ L T S \\rightarrow\{L | LT\} S→L∣LT
2.   T → L ∣ D ∣ T L ∣ T D T \\rightarrow\{L | D | TL | TD\} T→L∣D∣TL∣TD
3.   L → a ∣ b ∣ c ∣ . . . ∣ z L \\rightarrow\{a|b|c|...|z\} L→a∣b∣c∣...∣z
4.   D → 0 ∣ 1 ∣ 2 ∣ . . ∣ 9 D \\rightarrow\{0|1|2|..|9\} D→0∣1∣2∣..∣9

**由上下文无关文法生成的语言称为上下文无关语言（2型语言）**

## 3型文法(Type-3 Grammar) ##

3型文法又称**正则文法(Regular Grammar)**:

*  **右线性文法**： A → ω B A \\rightarrow\{\\omega B\} A→ωB或 A → ω A \\rightarrow\{\\omega\} A→ω
 *  **左线性文法**： A → B ω A \\rightarrow\{B \\omega\} A→Bω或 A → ω A \\rightarrow\{\\omega\} A→ω

左线性文法和右线性文法都称为正则文法。

由于左部一定是非终结符，**所以3型文法满足2型文法**。

**正则文法能描述程序设计语言的多数单词**。

# 四种文法之间的关系 #

*  逐级限制
    
     *  0型文法： α \\alpha α中至少包含1个非终结符
     *  1型文法： ∣ α ∣ ≤ ∣ β ∣ |\\alpha| \\le |\\beta| ∣α∣≤∣β∣
     *  2型文法： α ∈ V N \\alpha \\in V\_N α∈VN
     *  3型文法： A → ω B A \\rightarrow\{\\omega B\} A→ωB或 A → ω A \\rightarrow\{\\omega\} A→ω(右线性)。 A → B ω A \\rightarrow\{B \\omega\} A→Bω或 A → ω A \\rightarrow\{\\omega\} A→ω（左线性）