编译原理之文法的分类和判别

1.文法的分类

Chomsky文法分类将文法分为四种，逐渐对产生式施加限制形成一个层次：

• 0型：G = (V_T , V_N , S , P)
  规则形式：α → β ，α,β∈(V_T , V_N) ^*,α ≠ ε
  推导：γαδ ⇒ γβδ

• 1型（上下文有关）：规则α → β 有|α|≤|β|
  规则形式：ξAη→ξγη，A ∈ V_N，ξ , γ , η ∈(V_T , V_N) ^* , γ ≠ ε

• 2型（上下文无关）
  规则形式：A → β , A∈V_N , β ∈(V_T , V_N) ^*

• 3型（右线性/左线性/正规文法）
  A → aB或者A → a（右线性）
  A → Ba或者A → a（左线性）
  a∈ V_T∪{ε}

2.文法的判别

判别小技巧：

从上图我们可以看出，四种文法中，从0型到3型，其规则和约定越来越多，限制条件也越来越多，所以，我们可以从最复杂的3型进行判断，如果不符合3型的，那再看是不是2型的，不是2型的，再看是不是1型的，依次向下判断，最后答案取其最高的符合规则。

• 3型文法遵循的规范是：

  1. 判别式的左边必须只有一个字符，且必须是非终结符；
  2. 判别式的右边最多只能有两个字符，且当判别式的右边有两个字符时必须有一个为终结符而另一个为非终结符。当判别式的右边只有一个字符时，此字符必须为终结符；
  3. 对于3型文法中的所有产生式，其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须前面是终结符而后面是非终结符，这是右线性文法。要么就全是：非终结符＋终结符的形式，称为左线性文法。

• 2型文法遵循的规范是：

  1. 与3型文法的第一点相同，即：左边必须有且仅有一个非终结符。
  2. 2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。

• 1型文法遵循的规范是：

  1. 1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。
  2. 与2型文法第二点相同。

• 0型文法遵循的规范是：
  我们能描述出来的，都属于这个类型，即0型。

最后答案取其最高的符合规则。

抛出一个小栗子

1. 给出下面语言的相应文法，并指明其类型
   L₁ = {aⁿbⁿ | n ≥ 1}

   解析：
   S → a….ab….b 两边分别加上a和b得到：S → a(a….ab….b)b 即S → aSb ；
   又因为 n ≥ 1,得出S → ab，所以，文法为S → aSb|ab，为2型上下文无关文法

2. 给出下面语言的相应文法，并指明其类型
   L₂ = {aⁿbⁿ cⁱ | n ≥ 1,i ≥ 0}

   解析：
   S → a…ab…bc…c , 记A → a…ab…b , B→ c…c
   S → AB
   由A → a(a…ab…b)b 得 A → aAb
   又因为 n ≥ 1,得出A → ab
   A → aAb | ab
   由B → c(c…c)可得B→ cB
   又因为 i ≥ 0,得出B → ε
   B→ cB | ε
   所以，文法为：
   S → AB
   A → aAb | ab
   B→ cB | ε
   2型上下文无关文法

3. 给出下面语言的相应文法，并指明其类型
   L₃ = {aⁱ b^j c^k | i , j , k ≥ 1}

   此处思考三分钟哦~

   
   解析：
   S → a…ab…bc…c ,得S → a(a…ab…bc…c)
   S → aS
   由i ≥ 1可得 S → a(b…bc…c)，记A→ b…bc…c 得 S → aA
   又因为 A→ b(b…bc…c),得出A → bA
   又因为 j ≥ 1,得出 A→ b(c…c)，记B → c…c 得 A → bB
   由B → c(c…c)可得B→ cB
   有因为k ≥ 1,可得B→ c
   所以，文法为：
   S → aS | aA
   A → bA | bB
   B→ cB | c
   3型右线性文法

PS:还有不清楚的小伙伴们可以留言哦，我尽量讲的更细一点~喜欢就点赞和关注哦o(￣▽￣)ブ