Chapter 2 文法和语言的基础知识

2.1 概述

语法：对语言结构的定义，即这条语句是由什么构成的
语义：描述语言的含义，即这条语句是干什么的
语用：从使用的角度去描述语言，即这个语句对应的一类语句有什么用

2.2 字母表和符号串的基本概念

文法：描述语言的语法结构的形式规则
字母表：元素的非空有穷集合，记为 $\Sigma$
符号（字符）：字母表中每个元素称为字符
字符串（字）：由 $\Sigma$ 中的字符构成的一个有穷序列
空字：不包含任何字符的序列，记为 $\varepsilon$
所有字的全体：包含空字，记为 $\Sigma^*$ ，实际上就是 $\Sigma$ 的闭包。

如 $\Sigma=\{a, b\}$ ，那么 $\Sigma^*=\{\varepsilon,a,b,ab,ba,aa,ab,aaa,...\}$

连接：x和y两个字符串的连接xy。 $\Sigma^*$ 的子集的连接（乘积）定义为： $AB=\{xy|x\in A \& y\in B\}$
符号串的幂运算：设x为符号串，则其幂运算定义为： $x^0=\varepsilon,x^1=x,x^2=xx,...$ 。集合的幂运算与之类似。
正闭包 $A^+$ 和闭包 $A^*$ ：A的正闭包和闭包定义为： $A^+=A^1\cup A^2\cup ...\cup A^n...,A^*=\{\varepsilon\}\cup A^+$

2.3 文法和语言的形式定义

2.3.1 形式语言

序列的集合称为形式语言。形式语言有两种表示方式。
一种方式是将语言所有可能以枚举的形式写到一个集合中去。
另一种方式针对无法枚举的情况，称为产生式。

2.3.2 文法的形式定义

规则

规则又称产生式，是一个符号与一个符号串的有序对 $(A,\beta)$ ，通常写作 $A\rightarrow \beta$ ，其中 $A$ 为规则左部，是一个符号， $\beta$ 为规则右部，是一个符号串。 $\rightarrow$ 表示“生成”、“定义为”。规则的作用是告诉我们如何使用规则中的符号生成语言中的序列，即一组规则定义了一个语言的语法结构。

文法

文法是规则的有穷集合，通常用四元组 $G=(V_N,V_T,P,S)$ 表示，其中：

$V_N$ 是规则中非终结符号的集合
$V_T$ 是规则中终结符号的集合， $V_N\cap V_T=\empty$ 。通常使用 $V$ 表示 $V_N\cup V_T$ ，称为文法中的词汇表
$P$ 是文法规则的集合
$S$ 是一个非终结符号，称为文法的开始符号或文法的识别符号，至少要在一条规则中出现，由它开始识别定义的语言

文法是对语言结构的定义和描述。文法四大要素中，关键是规则的集合。

为书写方便，对于若干左部相同的规则可以缩写为 $A\rightarrow \alpha_1|\alpha_2|...$ ，其中每一个 $\alpha_i$ 称为 $A$ 的一个候选式。约定第一条规则的左部符号为识别符号，对文法 $G$ 不使用四元式显式表示，而是只写出规则。

2.3.3 语言的形式定义

直接推导

令 $G$ 为一文法，从 $xAy$ 直接推出 $x\alpha y$ ，即 $xAy\Rightarrow x\alpha y$ ，仅 $A\rightarrow \alpha$ 是 $G$ 的一个规则且 $x,y\in (V_N\cup V_T)^*$ 。即这一次直接推导只使用了一次规则。注意推导是 $\Rightarrow$ 而规则是 $\rightarrow$ ，二者千万不要搞混。

推导

如果存在一个推导序列 $\alpha_0\Rightarrow\alpha_1\Rightarrow...\Rightarrow\alpha_n$ ，则称这个序列是一个从 $\alpha_0$ 到 $\alpha_n$ 的长度为n的推导，记为 $\alpha_0\stackrel{+}\Rightarrow\alpha_n$ ，其表示从 $\alpha_0$ 出发可以经过1步或若干步或使用若干次规则推导出 $\alpha_n$ 。

广义推导

$\alpha_0\stackrel{*}\Rightarrow\alpha_n$ 表示从 $\alpha_0$ 出发可以经过0步或若干步或使用若干次规则推导出 $\alpha_n$ 。0步指的是 $\alpha_0=\alpha_n$ 的情况。

句型和句子

设有文法 $G[S]$ ，如果 $S\stackrel{*}\Rightarrow x,x\in(V_N\cup V_T)^*$ ，则称符号串x为文法 $G[S]$ 的句型， $S\stackrel{*}\Rightarrow x,x\in(V_T)^*$ ，称x为文法 $G[S]$ 的句子。即句子只含有终结符，是一个确定的字符串序列，而矩形可能含有非终结符，可能是一个字符串范式，表示一类字符串的格式。

语言

文法 $G[S]$ 产生的所有句子的集合称为该文法 $G$ 所定义的语言，记作 $L(G[S])$ 。 $L(G[S])=\{x|S\stackrel{+}{\Rightarrow}x\&x\in V_T^*\}$ 。当文法确定时，语言也就确定。注意 $L(G)$ 是 $V_T^*$ 的一个子集，属于 $V_T^*$ 的符号串 $x$ 不一定属于 $L(G)$ ，因为 $V_T^*$ 中不是所有的符号串都满足文法规定的句型格式。

2.3.4 规范推导和规范规约

最左（最右）推导：对于一个推导序列中的每一步直接推导 $\alpha\Rightarrow\beta$ ，都是对 $\alpha$ 中的最左（最右）非终结符进行替换。最右推导又称规范推导，由规范推导推导出的句型称为规范句型。

规范规约：规范推导的逆过程，即从左向右进行规约，也称为最左规约。

2.4 短语、直接短语和句柄

2.4.1 短语和直接短语

令 $G$ 为一个文法， $S$ 为文法开始符号，假定 $\alpha\beta\delta$ 是文法 $G$ 的一个句型，如果有 $S\stackrel{*}\Rightarrow\alpha A\delta$ 且 $A\stackrel{+}\Rightarrow\beta$ ，则称 $\beta$ 是相对于非终结符 $A$ 的句型 $\alpha\beta\delta$ 的短语。特别地如果有 $S\stackrel{*}\Rightarrow\alpha A\delta$ 且 $A\Rightarrow\beta$ ，则称 $\beta$ 为直接短语。一个句型的最左直接短语称为该句型的句柄。

2.5 语法树与文法的二义性

2.5.1 推导和语法树

语法树：使用一张图表示一个句型的推导，称为语法树。一棵语法树是不同推导过程的共性抽象。
语法树的子树：由某一个非末端结点连同所有分支组成的部分。
简单子树：只有单层分支的子树。

可以根据语法树快速确定一个句子的短语、直接短语和句柄。方法如下：
短语——子树的末端结点形成的符号串是相对于子树根的短语。
直接短语——简单子树的末端结点形成的符号串是相对于简单子树根的短语。
句柄——最左简单子树的末端结点形成的符号串是句柄。

2.5.2 文法的二义性

当一个句型有多个最左（最右）推导时，表示该文法存在某个句子对应两棵不同的语法树，该文法具有二义性。一个语言是二义的，如果对其不存在没有二义性的文法。

消除二义性文法可以通过添加限制性规定、调整运算符的优先顺序和结合规则等方式实现。

2.6 文法和语言的分类

文法和语言分为4大类：0型~3型。

0型：无限制文法。即每条规则的左式和右式都为 $(V_N\cup V_T)^*$ ，且左式中至少含有1个非终结符。
1型：上下文有关文法。每一条规则形式为 $\alpha A\beta\rightarrow \alpha u\beta$ ，其中 $A\in V_N,\alpha,\beta\in(V_N\cup V_T)^*,u\in(V_N\cup V_T)^+$ ，即在替换非终结符 $A$ 时需要考虑上下文。
2型：上下文无关文法。每一条规则的形式为 $A\rightarrow\beta$ ，其中 $A\in V_N,\beta\in(V_N\cup V_T)^*$ 。即使用该规则时无需考虑 $A$ 的上下文结构而可以直接将其转换。
3型：正规文法。每一条规则的形式为 $A\rightarrow \alpha B$ 或 $A\rightarrow \alpha$ ，其中 $A,B\in V_N,\alpha\in V_T^*$ 。右线性文法和左线性文法都为3型文法。

上面4种文法可以表示的句型范围从大到小，规范性从弱到强。一些句型可能无法使用高规范文法进行表示但可以用低规范性文法表示。对于现今程序设计语言，在编译程序中，仍然采用上下文无关文法来表述其语言结构。

2.7 有关文法的实用限制和变换

对文法的实用限制有两点：

文法中不能包含如 $A\rightarrow A$ 的规则，这被称为有害规则。
文法中不能包含多余规则。即文法中出现以下两种规则：
- 某条规则左部符号不在所属文法的任何规则右部出现，这样这个规则就永远不可能用得上。
- 对文法中某个非终结符不能从其推导出任何终结符号串，这意味着如果使用了这个规则，那么它将一直推导下去永远无法到达终点，这显然是不允许的。

题型总结

1. 基本概念的理解

例-1：给出文法 $G[S]$ 如下：
$S\rightarrow Bd$
$B\rightarrow Ae$
$A\rightarrow Ad|d$
求句子 $dded$ 的句柄、所有短语和直接短语。
方法1：画出语法树。这是最为保险，也最不容易错的一种方法。此处语法树略。
方法2：进行推导。
$S\Rightarrow Bd\Rightarrow Aed\Rightarrow Aded\Rightarrow dded$ 。其中有 $B\stackrel{+}\Rightarrow ded$ ，因此 $ded$ 是一个短语。同理第一个 $d$ ， $dd$ ， $dded$ 也是短语。
直接短语是直接推导而来，因此只有第一个 $d$ 是直接短语。
句柄是最左直接短语，即第一个 $d$ 。

一定要搞清楚短语、直接短语和句柄的定义，不要混淆。

2. 根据字符串描述写出文法

例-2：使用文法表示下面描述的语言。该语言由0、1、左右括号组成，且由01开头，10结尾。中间的值可以为0、1、括号扩充的整体。由左右括号扩充的整体中，以00开头，11结尾，中间的值可以为0、1、括号扩充的整体。如01(00111)(0011011)011(0011)10是该语言的一个句子。

分析：求解写文法题时需要将问题分解，采用分治的思想逐个击破。如本题中可明显地将“括号扩充的整体”进行首先处理，然后再去处理其他的内容。将这部分定义为由非终结符 $T$ 生成，则有
$T\rightarrow(00A11)$ ，其中 $A$ 应该表示的是0或1构成的序列：
$A\rightarrow A0|A1|0|1$
外层的内容：
$S\rightarrow 01B10$ ，其中 $B$ 应该是 $T$ 和 $A$ 构成的字符串
$B\rightarrow BT|BA|T|A$
所求文法：
$S\rightarrow 01B10$
$B\rightarrow BT|BA|T|A$
$T\rightarrow (00A11)$
$A\rightarrow A0|A1|0|1$

技巧：对于一些常见的序列组合，有固定的模式可以套用——

由终结符 $\{a_1,a_2,...,a_n\}$ ${a_{1}, a_{2}, . . ., a_{n}}$ 构成的所有字符串可以使用下面的文法规则（如不包含空串则删去最后的 $\varepsilon$ $ε$ 即可）：
- $S\rightarrow Sa_1|Sa_2|...|Sa_n|a_1|a_2|...|a_n|\varepsilon$
运算符优先级控制，对于运算符 $\{*_1,*_2,...,*_n\}$ ${*_{1}, *_{2}, . . ., *_{n}}$ ，下标越大优先级越高，则可以使用下面的文法规则表示（这只是一种表示，还有其他表示方式）：
- $A_1\rightarrow A_1*_1A_2|A_2$
- $A_2\rightarrow A_2*_2A_3|A_3$
- $...$
- $A_n\rightarrow A_n*_nA_{n+1}|A_{n+1}$
- 若存在优先级相同的运算符，则作为一个规则的不同候选式。

实际上有了上面这两条规则模板，已经可以解决很多的问题了，但有时还可以通过一些更加巧妙的组合来简化文法的书写：

长度相等子串对：在句子中包含有类似于 $\alpha^n\beta^n(n\ge 0)$ $α^{n} β^{n} (n \geq 0)$ 的形式，如果采用上面的方式需要两个规则，但实际上可以简化为一条规则：
- $S\rightarrow\alpha S\beta|\alpha\beta|\varepsilon$
长度相关子串对：两个重复子串的长度不再相等，而是具有一定的关系：
- 大小关系： $\alpha^n\beta^m(n>m\operatorname{or}n<m,m,n\ge 0)$ $α^{n} β^{m} (n > m o r n < m, m, n \geq 0)$ ，以 $n>m$ $n > m$ 为例，可以写为一条规则：
  - $S\rightarrow\alpha S\beta|\alpha S|\alpha|\beta$ （此时可以不加 $\varepsilon$ ，因为此时 $m$ 和 $n$ 必有一个不为0，因此串不可能为空串）
- 倍数关系： $\alpha^{an}\beta^n$ $α^{a n} β^{n}$ ，可以将 $\alpha^a$ $α^{a}$ 看做一个整体：
  - $S\rightarrow \alpha^aS\beta|\alpha^a\beta|\varepsilon$
- 差数关系：两串长度的差值固定，将差的那一部分分离出来看做前后缀即可。
注意：形如 $a^nb^nc^n$ 的句子无法使用2型文法规则定义，因为 $b$ 子串长度取决于其左右 $a$ 子串和 $c$ 子串的长度。换句话说，我们无法对这个句子用分治法进行规则解释。但 $a^{2n}b^{2n}c^{2n}$ 可以解释，其文法为：
- $S\rightarrow ASB|AB|\varepsilon$
- $A\rightarrow a^2Ab|a^2b$
- $B\rightarrow bBc^2|bc^2$
- 这是将这个句子拆分成了 $a^{2n}b^n$ 和 $b^nc^{2n}$ 两份求解的，这两份的 $n$ 的关系由第一条规则可以定义。但 $a^nb^nc^n$ 不能这样分解是因为 $n$ 无法确定是否是偶数。当 $n$ 为偶数或奇数时相应的2型文法都可以写出来，但二者合并是无法实现的。（思考：当 $n$ 为奇数时，文法应该如何书写？）
长度相关子串对，之间夹有其他字符
- 将 $S$ 的第二个候选式 $\alpha\beta$ 变换为 $\alpha T\beta$ ，其他内容由 $T$ 规则负责解释。

3. 根据文法写出语言描述

也即第2种题型的逆推。

例-3：根据下列文法说出其定义的语言
$S\rightarrow0S|SD|D$
$D\rightarrow aS|b$

分析：其定义的语言可以通过画树状图的方式来寻找规律。每一次对候选式进行分支，可以据此获取所有该语言的句子。如上述文法定义的语言的最短的几个句子应该是： $b$ 、 $0b$ 、 $ab$ 、 $0ab$ ，可以发现所有这些句子的最后一个字符都是 $b$ 。有推导： $S\Rightarrow SD\Rightarrow0^*SD$ 、 $S\Rightarrow SD^*D\Rightarrow D^n\Rightarrow a^nS^n\Rightarrow a^nD^n\Rightarrow a^nb^n$ 。再往下分析，就比较难了，因为没有对这个文法进行化简。

对该文法尝试进行化简：
$S\rightarrow 0S|SaS|Sb|aS|b$
注意到其中有 $S\rightarrow0S|aS$ ，因此前缀应是0和 $a$ 组成的任意长度字符串，而后缀只能是 $b$ 组成的字符串。中间有一个规则是 $S\rightarrow SaS$ ，表示两个 $S$ 中间有一个 $a$ 分隔。去掉这条规则后，就只剩下对前缀后缀的规则定义了，因此这个文法描述的语言是：

一个类型的字符串A以一种方式连接起来形成的总字符串。字符串A由两个部分组成，前面是以0或a构成的任意长度字符串（含空串），后面是以b构成的任意长度字符串（不含空串）。总字符串中有1个或多个这样的字符串，这些字符串中间以a连接。

4. 二义性检查与反例

检查文法的二义性主要有判断性问题和举反例问题，多出现在运算符优先级设置不合理的文法中。二义性的直接影响是在文法分析过程中会产生移进-规约冲突和规约-规约冲突，前者出现于一个右部串是另一个右部串的子串时，后者出现在一个右部串对应多个左部串。有时对于移进-规约冲突的情形，需要进行推导才能发现右部符号串有包含情况。

CoLin's BLOG

编译原理——第2章