编译-第02章-文法和语言的概念和表示

•
Compiler

编译-第2章-文法和语言的概念和表示

以”the big elephant are the parent”为例

形式语言基础

4. 符号串集合的乘积运算：

令A、B为符号串集合，定义

AB={xy∣x∈A,y∈B}

6. 符号串集合的闭包运算

设 A是符号串集合，定义：

  1. 正闭包**：**A+=A1∪A2∪A3∪…∪An∪…
  2. 闭包*：*A∗=A0∪A+

文法（语法）的非形式讨论

  1. 文法（语法）：从形式上描述和规定语言结构

有穷语言，无穷语言（有递归文法）

  1. 语法规则：”::=”表示”由…组成”，符号：→

    image.png

  2. 由规则推导句子，符号：⇒

    image.png

    1. $<句子> ⇒^+ the\ big\ elephant\ ate\ the\ peanut$
    2. [<形容词>]这样的可选符号
    3. 存在最左推导，最右推导（一般推导）
    4. 还可以推导出the big peanut ate the elephant，符合文法

  3. 语法树，用语法树来描述一个句子的语法结构

    image.png

    语法成分（非终结符）单词符号（终结符），所以说符号包括抽象的和具体的

文法和语言的形式定义

1. 文法的定义

一个形式文法 G是一个四元组，表示为：G=(Vn,Vt,P,Z)

  • Vn：非终结符号集（非空有限集）；P的左边的集合
  • Vt：终结符号集（非空有限集）；P的右边去掉Vn
  • P：产生式规则集合
  • Z：开始符号（识别符号），且 Z∈Vn，是推导的初始点。第一条规则的左边

无符号整数文法结构：

  • 非终结符集合 Vn={⟨无符号整数⟩,⟨数字串⟩,⟨数字⟩}
  • 终结符集合 Vt={0,1,2,3,4,5,6,7,8,9}
  • 产生式集合 P包含以下规则：

    1. ⟨无符号整数⟩→⟨数字串⟩

    2. ⟨数字串⟩→⟨数字串⟩⟨数字⟩

    3. ⟨数字串⟩→⟨数字⟩

    4. ⟨数字⟩→0

    5. ⟨数字⟩→1

      …

    6. ⟨数字⟩→9

  • 开始符号 Z=⟨无符号整数⟩

2. 推导的形式定义

直接推导（Direct Derivation）

指在文法推导过程中，仅应用一次产生式规则。若存在字符串 v=xUy（其中 U是非终结符，x,y是任意字符串），通过规则 U::=u替换 U得到 w=xuy，则称 v直接推导出 w，记作 v⇒w。

特点：单步完成，仅涉及一条规则的应用。

间接推导（Indirect Derivation）

指通过多次应用产生式规则（即多步直接推导）得到结果。若存在字符串序列 v0,v1,…,vn（n≥1），满足 v0⇒v1⇒…⇒vn，则称 v0间接推导出 vn，记作 v0⇒∗vn（其中 ⇒∗表示零步或多步推导）。

特点：多步完成，是直接推导的传递闭包（包含零步或多次推导）。

image.png

规范推导==最右推导，U为最右边的非终结

3. 语言的形式定义

定义6：文法G[Z]

(1) 句型：x是句型 ⇔ Z ⟹* x，且x ∈ V*；从识别符号开始往下推，中间结果

(2) 句子：x是句子 ⇔ Z ⟹⁺ x，且x ∈ Vt*；从识别符号推到底

(3) 语言：L(G[Z]) = {x | x ∈ Vt*，Z ⟹⁺ x}；

符号说明：

  • ⇔ 表示等价关系（当且仅当）
  • ⟹* 表示零步或多步推导（间接推导）
  • ⟹⁺ 表示一步或多步推导（至少一步）
  • V* 表示所有符号（终结符和非终结符）的闭包
  • Vt* 表示终结符的闭包
  • L(G[Z]) 表示由文法G[Z]生成的语言

语言就是句子的集合

  • 文法→语言
  • 语言→多种文法（经验）
  • 如果两个文法产生的语言相同，两个文法就是等价的

4. 递归文法

规则右边有与左边相同的符号：递归规则

  1. ⟨数字串⟩→⟨数字串⟩⟨数字⟩：左递归；同理还有右递归，一般递归

一步或者多部推导

一步或者多部推导

左递归文法：可能会死循环，why？始终在左侧添加非终结符，无法生成终结符？？？？

5. 句型的短语，简单短语和句柄

语法树分析法

  1. 为给定的句型构造语法分析树
  2. 找出所有子树对应的叶子节点序列 → 这些就是短语
  3. 找出所有深度为1的子树对应的叶子节点序列 → 这些就是简单短语

产生式分析法

  • 短语：查看句型中哪些子串可以由某个非终结符推导得到
  • 简单短语：查看句型中哪些子串直接匹配某个产生式的右部

w=xuy为G[Z]文法的句型

  • 短语：若Z⇒*xUy，且U⇒+u， 则u是巨型w相对于U的短语
  • 如果U⇒u，则是简单短语

直观理解：短语是前面句型中的某个非终结符所能推出的符号串

  • 最左简单短语称为句型的句柄

image.png

语法数与二义性文法

1. 推导与语法树

无二义性文法：句型的语法树是唯一的

子树定义：

语法树中的某个结点（子树的根）连同它向下派生的部分所组成。

定理：

某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。

最左规约和最右推导互逆

2. 文法的二义性

  • 定义：同一个句子存在不同的语法树，就是二义性文法
  • 如果某规范句型的句柄不唯一，文法具有二义性

有关文法的使用限制

  • 有害规则：U::=U，eg. U⇒a, U⇒U⇒a
  • 多余规则：
    • 始终用不到的规则，左边的非终结符不会出现在任何句型里
    • 一旦用了，推不出任何终结符号串，即该规则中含有退不出任何终结符号串的非终结符

检查多余规则：

  • 对于任何Vn，必须出现在某个句型中，即Z⇒xUy
  • 对于任何Vn，必须能推出终结符号串t
  • 如果满足以上两条，被称为压缩文法

文法的其他表示

[]：可选

{}：出现一次或多次

()：提取因子

文法和语言分类

Chomsky

G=(Vn, Vt, P, Z)

$L(G[Z])={x|x\in V_t^*, Z=>^+x}$

按照 Chomsky 层次（乔姆斯基层次），文法通常分为四类：

  1. 0型文法（短语结构文法）：没有限制，能描述所有递归可枚举语言。
    1. 左部符号序列至少含有一个非终结符
    2. 右部随便（可以为空）
    3. 图灵机接受
  2. 1型文法（上下文有关文法，CSG）：产生式一般形如 αAβ → αγβ，$A\in V_n$
    1. 上下文敏感，只有在x…y上下文，非终结符A才能继续往下推
    2. 线形界限自动机
  3. 2型文法（上下文无关文法，CFG）：产生式左部必须是单个非终结符。
    1. BNF
    2. 把1型文法x,y均为空即为2型
    3. 之所以被称为上下文无关，是因为把U重写成u时不需要考虑上下文
    4. 下推自动机接受
  4. 3型文法（正则文法，RG）：产生式左部是单个非终结符，右部最多一个非终结符且限制在最左或最右。
    1. 有穷自动机接受