前言

参考东南大学廖力老师的编译原理教程和课上PPT内容。 该学习笔记目前仅打算个人使用。
后续会进一步整理，包括添加笔记内容，标明参考资料。

更新中。。。

跳过目录

一、概念回顾

形式语言

  用文法和自动机所描述的没有语义的语言。

形式语言使用文法和自动机来描述的。文法用于生成语言，自动机用于识别语言。

语言定义

某一文法的语言是指能由 Z 出发，利用 P 中规则推导出来的所有终结符号串所组成的集合。即：
L(G[Z]) = { x | x ∈ V_t^*，Z x }

Chomsky对文法的定义

乔姆斯基将所有文法都定义为一个四元组：

  G = ( V_n，V_t，P，Z)

• V_n：非终结符号集
• V_t：终结符号集
• P：产生式或规则的集合
• Z：开始符号（识别符号） Z∈ Vn

二、文法和语言的分类

根据对产规则 P 施加的限制，可分为：

• 0型文法
• 1型文法
• 2型文法
• 3型文法

这几类文法的差别在于对产生式施加不同的限制。

1、0型文法（短语结构文法、无限制文法）

  P中任一规则都有一般形式 α → β，其中 α ∈ V⁺ 并至少含有一个非终结符，β ∈ V^*。

注：

• β 可以为 ε
• 0型文法又称短语结构文法、无限制文法
• 0型文法是对产生式限制最少的文法
• 对0型文法产生式的形式作某些限制，可得到其他类型文法的定义

0型语言

-有0型文法所确定的语言，记为L0

• 识别0型语言的自动机称为图灵机（TM）
• 任何0型语言都是递归可枚举的

2、1型文法（上下文敏感文法、上下文有关文法）

定义一：

  对任一P中规则 α → β ，除可能有S → ε 外均有|β| ≥ |α|；若有 S → ε ，规定S不得出现在产生式右部

定义二：

  P中规则 α → β ，除可能有S → ε 外均有 αAβ → αγβ，其中 α，β∈ V^*，A ∈ V_n，γ ∈ V⁺。
（理解：非终结符A在前面有 α，后面有 β 的条件下，可以变成γ）

P： xUy → xuy，其中 U ∈ V_n，x、y、u ∈ V^*

注：

• 1型文法又称为长度增加文法、上下文敏感文法、上下文有关文法，也即只有在x、 y这样的上下文中才能把U改写为u

• 1型文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成 ε ，除非是开始符号产生 ε

例：

设文法G = (V_n，V_t，P，S)，V_n = {S，B，E}，V_t = {a，b，e}

其中P为：

  S → aSBE
  S → aBE
  EB → BE
  aB → ab
  bB→ bb
  bE → be
  еЕ → eе

判断是否为0型或1型：主要看长度是不是增加的

1型语言

• L1
• 识别1型语言的自动机称为线性界限自动机（LBA）

3、2型文法（上下文无关文法）

  P中规则具有形式 A → β，其中A ∈ V_n，β ∈ V^*

P：U → u，其中 U ∈ V_n，u ∈ V^*

注：

• 2型文法也称为上下文无关文法
• 2型文法对产生式的要求是：产生式左部一定是非终结符，产生式右部可以是V_N、V_T或 ε ；非终结符的替换不必考虑上下文
• 注意： 2型文法与BNF表示相等价。

例：

设文法G = (V_N，V_T，P，S)，V_N = {S，A，B}，V_T = {a，b}

其中P为：

  S → aB
  S → bA
  A → a
  A → aS | bAA
  B→ b

对产生式左边开始有限制：只有一个非终结符存在

2型语言

• L2
• 识别2型语言的自动机称为下推自动机（PDA）

4、3型文法（正规文法、正则文法）

P中产生式具有形式A → αB | α（右线性文法），或者A → Bα | α（左线性文法），其中A，B ∈ V_N，α ∈ V_T^*

（左线性）：
P：U → T 或 U → wT，其中 U、w ∈ V_n，T ∈ V_t

（右线性）：
P：U → T 或 U → Tw，其中 U、w ∈ V_n，T ∈ V_t

注：

• 3型文法也称为正规文法RG、右线性文法或左线性文法
• 3型文法中的产生式要么均是右线性产生式（非终结符在最右边），要么是左线性产生式，不能既有左线性产生式，又有右线性产生式
• 若所有产生式均是左线性，则称为左线性文法；若所有产生式均是右线性，则称为右线性文法

3型语言

• L3
• 3型语言又称正则语言、正则集合
• 识别3型语言的自动机称为有限状态自动机（有穷自动机）。

举例：

设文法G = (V_N，V_T，P，S)，V_N = {S，A，B}，V_T = {0，1}

其中P为：

0. S → 0A | 1B | 0
1. A → 0A | 1B | 0S
2. B → 1B | 1 | 0

3、4种文法之间的关系

四种文法之间的关系是将产生式作进一步限制而定义的，他们呈逐级包含关系。

即：如果文法P属于 n+1 型文法，那么肯定属于 n 型文法。
根据上述讨论， L0 ⊇ L1 ⊇ L2 ⊇ L3

0型文法可以产生L0、 L1、 L2、 L3，但 2 型文法只能产生L2，不能产生L1。