上下文无关文法

目录

• 上下文无关文法
  • 目录
  • 1. 背景
  • 2. 上下文无关文法
    • 2.1. 文法
    • 2.2. 语法描述的几个基本概念
    • 2.3. 上下文无关文法
    • 2.4. 最左、最右推导
  • 3. 语法树
  • 4. 二义性
    • 4.1. 文法的二义性
    • 4.2. 语言的二义性
  • 5. 乔姆斯基形式语言体系
    • 5.1. 零型文法
    • 5.2. 一型文法
    • 5.3. 二型文法
    • 5.4. 三型文法
    • 5.5. 四种类型文法描述能力比较

1. 背景

这学期选了《编译原理》这门课，发现高级程序设计语言的语法描述这部分中，上下文无关文法和四种不同类型的文法这些内容比较复杂。于是我参考中国大学MOOC-国防科技大学《编译原理》的PPT，整理了这一章的内容，希望能够理解这部分的知识。

2. 上下文无关文法

2.1. 文法

• 文法
  • 定义：描述语言的语法结构的形式规则（即语法规则）
  • 举例：<句子> → <主语><谓语><间接宾语><直接宾语> 推导出He gave me a book.

2.2. 语法描述的几个基本概念

1. 字母表：一个有穷字符集，记为$\Sigma$
2. 字符：字母表中每个元素称为字符
3. 字（字符串）：由$\Sigma$中的字符所构成的一个有穷序列
4. 空字：不包含任何字符的序列称为空字，记为$\epsilon$
5. 字的全体： 用$\Sigma^*$表示$\Sigma$上的所有字的全体，包含空字$\epsilon$
6. 连接（积）：$\Sigma^*$的子集$U$和$V$的连接（积）定义为

$$UV ＝ \{ \alpha \beta | \alpha \in U \& \beta \in V\} \tag{1}$$

1. 闭包：$V^*$是$V$的闭包

$$V^* = V^0 \bigcup V^1 \bigcup V^2 \bigcup V^3 \bigcup \cdots \tag{2}$$

闭包包含$V^0 = \epsilon$

1. 正规闭包：$V^+$是$V$的正规闭包：

$$V^+＝V V^* \tag{3}$$

正规闭包不含$\epsilon$

2.3. 上下文无关文法

上下文无关文法G是一个四元组

$$G=(V_T，V_N，S，P) \tag{4}$$

其中

• $V_T$：终结符（Terminal）集合(非空)
• $V_N$：非终结符（Noterminal）集合（非空），且$V_T \bigcap V_N = \varnothing$
• $S$：文法的开始符号，$S \in V_N$
• $P$：产生式集合(有限)，每个产生式形式为

$$P \to \alpha {\hspace*{0.5cm}} P \in V_N {\hspace*{0.5cm}} \alpha \in (V_T \bigcup V_N)^* \tag{5}$$

开始符$S$至少必须在某个产生式的左部出现一次。

2.4. 最左、最右推导

• 最左推导

  • 定义：任何一步$\alpha \Rightarrow \beta$都是对$\alpha$中的最左非终结符进行替换

• 最右推导

  • 定义：任何一步$\alpha \Rightarrow \beta$都是对$\alpha$中的最右非终结符进行替换

3. 语法树

• 语法树：用一张图表示一个句型的推导,称为语法树。

一棵语法树是不同推导过程的共性抽象，一棵语法树可以对应多个不同的推导过程。

4. 二义性

4.1. 文法的二义性

• 文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的

4.2. 语言的二义性

• 语言的二义性：一个语言是二义的，如果对它不存在无二义的文法

5. 乔姆斯基形式语言体系

四种类型的文法也都由四部分组成

$$G=(V_T，V_N，S，P) \tag{6}$$

其中

• $V_T$：终结符（Terminal）集合(非空)
• $V_N$：非终结符（Noterminal）集合（非空），且$V_T \bigcap V_N = \varnothing$
• $S$：文法的开始符号，$S \in V_N$
• $P$：产生式集合(有限)，每个产生式形式为

$$P \to \alpha {\hspace*{0.5cm}} P \in V_N {\hspace*{0.5cm}} \alpha \in (V_T \bigcup V_N)^* \tag{7}$$

5.1. 零型文法

• 0型文法（短语文法，图灵机）

  • 产生式形如： $\alpha \to \beta$
  • 其中：$\alpha \in (V_T \bigcup V_N)^*$且至少含有一个非终结符
  • $\beta \in (V_T \bigcup V_N)^*$

• 说明：对$\alpha$和$\beta$范围基本没有限制，要求$\alpha$（即产生式左边）至少有一个非终结符

5.2. 一型文法

• 1型文法(上下文有关文法，线性界限自动机)

  • 产生式形如： $\alpha \to \beta$
  • 其中：$|\alpha| ≤ |\beta|$，仅$S \to \epsilon$ 例外

• 说明：要求$\alpha$（产生式左边）长度小于右边，除开始符号直接推导出空字以外

5.3. 二型文法

• 2型文法(上下文无关文法，非确定下推自动机)

  • 产生式形如： $A \to B$
  • 其中：$A \in V_N$
  • $\beta \in (V_T \bigcup V_N)^*$

• 说明：要求$A$（即产生式左边）一定都是非终结符

5.4. 三型文法

• 3型文法(正规文法，有限自动机)

  • 右线性文法
    • 产生式形如： $A \to \alpha B$ 或$A \to \alpha$
    • 其中：$\alpha \in V_T^*$
    • $A, B \in V_N$
  • 左线性文法
    • 产生式形如： $A \to B\alpha$ 或$A \to \alpha$
    • 其中：$\alpha \in V_T^*$
    • $A, B \in V_N$

• 说明：

  • 右线性文法：产生式为推导停止或向右扩展，对右端进行递归，保证左侧始终为终结符。
  • 左线性文法：产生式为推导停止或向左扩展，对左端进行递归，保证右侧始终为终结符。

5.5. 四种类型文法描述能力比较

0型 > 1型 > 2型 > 3型

注：部分内容整理自中国大学MOOC-国防科技大学《编译原理》PPT

---

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。