本笔记基于北京邮电大学出版的李文生编著的《编译程序设计原理与技术》整理

1. 字母表和符号串

字母表:符号的非空有限集合。如集合 {0, 1} 是二进制数的字母表、ASCII 字符集和 EBCDIC 字符集等。

符号串:字母表中的符号组成的有限符号序列。在语言理论中,“句子”和“字”常常作为“符号串”的同义词。

  • 空符号串:不含任何符号的符号串,用 $\epsilon$ 表示。
  • 符号串的一些相关概念:长度、前缀、后缀、子串、真前缀、真后缀、真子串
  • 符号串的一些运算:
    • 符号串的连接:符号串 x 和 y 的连接,是将符号串 y 连接在符号串 x 后面而组成的新符号串,用 xy 表示。
    • 符号串的幂运算:$x^0 = ε$ , $x^1 = x$ , $x^2 = xx$ , $\dots$ , $x^n = x \dots x(n个)$

术语语言:在某一确定字母表上的符号串的集合。

  • 语言的乘积运算:符号串集合 $A = { aa, bb } ,B = {cc, dd }$ ,则 $AB = { aacc, aadd, bbcc, bbdd }$。
  • 语言的幂运算:$A^0 = {ε},A^1 = A, \dots , A^n = AA \dots\ A(n个) = AA^{n-1}$
  • 语言的闭包:
    • A 的正闭包( 1 次或若干次连接): $A^+ = A^1 \cup\ A^2 \cup\ \dots $
    • A 的 Kleene 闭包( 0 次或若干次连接):$A^* = A^0 \cup\ A^1 \cup\ A^2 \cup\ \dots $

2. 文法

文法(Grammar):描述语言结构的形式规则。

2.1. 文法的形式定义

任何一个文法都可以表示为一个四元组 $G=(V_T, V_N, S, φ)$ ,其中:

  • $V_T$ 是一个非空的有限集合,它的每个元素称为终结符号
  • $ V_N$ 是一个非空的有限集合,它的每个元素称为非终结符号
    • $V_T∩V_N = \phi$ ,即 $Y_T$ 与 $V_T$ 的交集为空。
  • $S$ 是一个特殊的非终结符号,称为文法的开始符号
  • $φ$ 是一个非空的有限集合,它的每个元素称为产生式
  • 产生式(或规则)的形式为:$\alpha \rightarrow \beta$
    • $\alpha$ 称为产生式的左部符号
    • $\beta$ 称为产生式的右部符号
    • 其中 $\rightarrow$ 表示『定义为』或『由……组成』,$\alpha 、\beta \in ( V_T \cup V_N)^*,\alpha \neq \epsilon$ ,即 $\alpha 、\beta$ 是由终结符号和非终结符号组成的字符串。
  • 开始符号 $S$ 至少必须在某个产生式的左部出现一次。
  • 文法也可只用产生式集合表示。

2.2. 文法的分类

根据对产生式施加的限制不同,定义了四类文法和相应的四种形式语言类:

2.3. 上下文无关文法及相应的语言

所谓上下文无关文法是指它所定义的语法单位(或称语法实体)完全独立于这种语法单位可能出现的上下文环境。对于现有的程序设计语言来说,许多语法单位的构造中具有固定的递归结构,这样的结构可以用上下文无关文法来描述。

这里语言L(G)是所有包括加、减、乘、除四则运算的算术表达式的集合。

2.4. 文法书写规定

终结符号

  • 次序靠前的小写字母,如:a、b、c ;
  • 运算符号,如:+、-、*、/ ;
  • 各种标点符号,如:括号、逗号、冒号、等于号;
  • 数字1、2、…、9;
  • 黑体字符串,如:id、begin、if、then 等。

非终结符号

  • 次序靠前的大写字母,如:A、B、C;
  • 大写字母 S 常用作文法的开始符号;
  • 小写的斜体符号串,如:expr、term、factor、stmt 等。

3. 推导和短语

3.1. 推导与归约

假定 $A \rightarrow \gamma$ 是一个产生式,$\alpha$ 和 $\beta$ 是任意的文法符号串,则有:$\alpha A \beta \Rightarrow \alpha \gamma \beta$

  • $\Rightarrow$ 表示『一步推导』,即利用产生式对左边符号串中的一个非终结符号进行替换,得到右边的符号串。
  • 称 $\alpha A \beta$ 直接推导出 $\alpha \gamma \beta$ ,也可以说 $\alpha \gamma \beta$ 是 $\alpha A \beta$ 的直接推导
  • 或说 $\alpha \gamma \beta$ 直接归约到 $\alpha A \beta$

如果有直接推导序列:$\alpha_1 \Rightarrow \alpha_2 \Rightarrow \dots \Rightarrow \alpha_n$ ,则说 $\alpha_1$ 推导出 $\alpha_n$,记作:

称这个序列是从 $\alpha_1$ 到 $\alpha_n$ 的长度为 n 的『推导』。

最左推导 :如果 $\alpha \stackrel{*}{\Longrightarrow} \beta$ 并且在每『一步推导』中,都替换 α 中最左边的非终结符号,则称这样的推导为『最左推导』。记作

最右推导:如果 $\alpha \stackrel{*}{\Longrightarrow} \beta$ 并且在每『一步推导』中,都替换 α 中最右边的非终结符号,则称这样的推导为『最右推导』,最右推导又被称为『规范推导』,与之对应的归约称为『规范归约』,记作

3.2. 句型

句型:对于文法 $G=(V_T, V_N, S, φ)$ ,如果$S \stackrel{*}{\Longrightarrow} \alpha$ ,则称 $\alpha$ 是当前文法的一个『句型』

  • 若 $S \stackrel{*}{\underset{lm}\Longrightarrow} \alpha$ ,则 $\alpha$ 是当前文法的一个左句型;
  • 若 $S \stackrel{*}{\underset{rm}\Longrightarrow} \alpha$ ,则 $\alpha$ 是当前文法的一个右句型。

句子:仅含有终结符号的句型是文法的一个『句子』

语言:文法 $G$ 产生的所有句子组成的集合是文法 $G$ 所定义的『语言』,记作 $L(G)$ 。

3.3. 短语

对于文法 $G=(V_T, V_N, S, φ)$ ,假定 $\alpha\beta\delta$ 是文法 $G$ 的一个句型,如果存在:

则称 $\beta$ 为句型 $\alpha \beta \delta$ 关于非终结符号 $A$ 的『短语』,如果存在:

则称 $\beta$ 为句型 $\alpha \beta \delta$ 关于非终结符号 $A$ 的『直接短语』

句柄:一个句型的最左直接短语称为该句型的『句柄』

4. 分析树及文法的二义性

4.1. 分析树(推导树)

分析树:是推导的图形表示,又称推导树。

  • 是一棵有序有向树,因此具有树的性质;
  • 有自己的特点:每一个结点都有标记。
    • 根结点由文法的开始符号标记;
    • 每个内部结点由非终结符号标记,它的子结点由这个非终结符号的这次推导所用产生式的右部各符号从左到右依次标记;
    • 叶结点由非终结符号或终结符号标记,它们从左到右排列起来,构成句型。

举例:

子树:指分析树中一个特有的结点、连同它的全部后裔结点、连接这些结点的边、以及这些结点的标记。

  • 子树的根结点的标记可能不是文法的开始符号。
  • 如果子树的根结点标记为非终结符号A,则可称该子树为『A-子树』。

子树与短语的关系:

  • 一棵子树的所有叶结点自左至右排列起来,形成此句型相对于该子树根的短语;
  • 分析树中只有父子两代的子树的所有叶结点自左至右排列起来,形成此句型相对于该子树根的直接短语;
  • 分析树中最左边的那棵只有父子两代的子树的所有叶结点自左至右排列起来,就是该句型的句柄。

4.2. 二义性

如果一个文法的某个句子有不止一棵分析树,则这个句子是二义性的,含有二义性句子的文法是『二义性的文法』。

形式语言理论可以证明两点结论:

  • 给定一个文法 $G$ ,就能从结构上唯一地确定其语言。
  • 给定语言 $L$ ,可以确定其文法,但是文法不是唯一的。

由此,从而有『等价文法』的概念,即 $G_1$ 和 $G_2$ 是两个不同的文法,如果 $L(G_1) = L(G_2)$ ,则称 $G_1$ 和 $G_2$ 为等价文法。

有时,一个二义性的文法可以变换为一个等价的、无二义性的文法。

有些语言,根本就不存在无二义性的文法,这样的语言称为『二义性的语言』。

二义性问题是不可判定的

  • 不存在一种算法,它能够在有限的步骤内确切地判定出一个文法是否是二义性的。
  • 可以找出一些充分条件(未必是必要条件),当文法满足这些条件时,就可以确信该文法是无二义性的。