上下文无关文法

文章目录

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 U U和 V V V的连接（积）定义为

U V ＝ { α β ∣ α ∈ U & β ∈ V } UV ＝ \{ \alpha \beta | \alpha \in U \& \beta \in V\} UV＝{αβ∣α∈U&β∈V}

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

V ∗ = V 0 ⋃ V 1 ⋃ V 2 ⋃ V 3 ⋃ ⋯ V^* = V^0 \bigcup V^1 \bigcup V^2 \bigcup V^3 \bigcup \cdots V∗=V0⋃V1⋃V2⋃V3⋃⋯

闭包包含 V 0 = ϵ V^0 = \epsilon V0=ϵ

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

V + ＝ V V ∗ V^+＝V V^* V+＝VV∗

正规闭包不含 ϵ \epsilon ϵ

2.3. 上下文无关文法

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

G = ( V T ， V N ， S ， P ) G=(V_T，V_N，S，P) G=(VT​，VN​，S，P)

其中

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

P → α <mpadded height="&#43;0em" voffset="0em"> </mpadded> P ∈ V N <mpadded height="&#43;0em" voffset="0em"> </mpadded> α ∈ ( V T ⋃ V N ) ∗ P \to \alpha {\hspace*{0.5cm}} P \in V_N {\hspace*{0.5cm}} \alpha \in (V_T \bigcup V_N)^* P→αP∈VN​α∈(VT​⋃VN​)∗

开始符 S S 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 ) G=(V_T，V_N，S，P) G=(VT​，VN​，S，P)

其中

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

P → α <mpadded height="&#43;0em" voffset="0em"> </mpadded> P ∈ V N <mpadded height="&#43;0em" voffset="0em"> </mpadded> α ∈ ( V T ⋃ V N ) ∗ P \to \alpha {\hspace*{0.5cm}} P \in V_N {\hspace*{0.5cm}} \alpha \in (V_T \bigcup V_N)^* P→αP∈VN​α∈(VT​⋃VN​)∗

5.1. 零型文法

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

    • 产生式形如： α → β \alpha \to \beta α→β
    • 其中： α ∈ ( V T ⋃ V N ) ∗ \alpha \in (V_T \bigcup V_N)^* α∈(VT​⋃VN​)∗且至少含有一个非终结符
    • β ∈ ( V T ⋃ V N ) ∗ \beta \in (V_T \bigcup V_N)^* β∈(VT​⋃VN​)∗

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

5.2. 一型文法

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

    • 产生式形如： α → β \alpha \to \beta α→β
    • 其中： ∣ α ∣ ≤ ∣ β ∣ |\alpha| ≤ |\beta| ∣α∣≤∣β∣，仅 S → ϵ S \to \epsilon S→ϵ 例外

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

5.3. 二型文法

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

    • 产生式形如： A → B A \to B A→B
    • 其中： A ∈ V N A \in V_N A∈VN​
    • β ∈ ( V T ⋃ V N ) ∗ \beta \in (V_T \bigcup V_N)^* β∈(VT​⋃VN​)∗

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

5.4. 三型文法

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

    • 右线性文法
      • 产生式形如： A → α B A \to \alpha B A→αB 或 A → α A \to \alpha A→α
      • 其中： α ∈ V T ∗ \alpha \in V_T^* α∈VT∗​
      • A , B ∈ V N A, B \in V_N A,B∈VN​
    • 左线性文法
      • 产生式形如： $A \to B\alpha $ 或 A → α A \to \alpha A→α
      • 其中： α ∈ V T ∗ \alpha \in V_T^* α∈VT∗​
      • A , B ∈ V N A, B \in V_N A,B∈VN​

  • 说明：

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

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

0型 > 1型 > 2型 > 3型

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

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

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