编译原理：文法、句型、句子、语言和文法的类型

Ch2: 文法和语言

一门高级语言是一个记号系统，需要定义语言和语义两部分。

1. 符号串上的运算:#

1.0 符号串的长度#

$x$ 为一串，则 $|x|$ 为 $x$ 所占字符表中，字符的个数

1.1 符号串的(固有)头和(固有)尾，(真)前缀和(真)后缀#

若 $z = xy$ ，则 $x$ 为 $z$ 的头(前缀)，注意 $x$ 可以为 $\varepsilon$

$x$ 为 $z$ 的头，且 $x \ne z$ ，则 $x$ 为 $z$ 的固有头/真前缀

1.2 符号串的连接。#

$x$ , $y$ 为两个符号串, $z = xy$ ， $|z| = |x| + |y|$

x = \varepsilon x=x \varepsilon

1.3 符号串的方幂#

$x^n$ 表示将串 $x$ 重复连接 $n$ 次

x^0=\varepsilon \\ x^mx^{n-m}=x^{n-m}x^m=x^n,\quad n\ge m

1.4 符号串集#

定义: 如果集合 $<span class="md-search-hit">A</span>$ 中所有的元素都是定义在符号表 $\Sigma$ 上的符号串，则称集合 $<span class="md-search-hit">A</span>$ 为定义在字符表 $\Sigma$ 的符号串集合

定义两个符号串的乘积: $A \times B = \{xy|x\in A,y \in B\}$

\{\varepsilon\} \times A = A

已有符号集 $\Sigma$ ,根据集合乘积的定义，可得到集合的方幂 $\Sigma^n$

其中:

\Sigma^0 = {\varepsilon}

定义闭包:

\Sigma^*=\Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup ...

定义正闭包:

\Sigma^+=\Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup ...

\Sigma ^* = \Sigma^+ \cup \Sigma^0 \\ \Sigma ^+ = \Sigma^\ \times \Sigma^*

2. 文法的定义: ( $V_N,V_T,P,S$ )#

对于某一语言，能够使用的是语言当中的句子，如果这些句子是有穷的，对于该语言可以列出一个有限大的句子集合。

但是有的语言当中的句子是无穷的，因此需要有限数量的文法来描述无穷数量的句子。

文法: 用有穷集合描述无穷集合的工具。

文法由非空有穷集合** $V_N,V_T,P$ **和一个起始符 $S$ 构成。

2.1 非终结符集 $V_N$ （non-terminal symbols)#

非终结符的含义是，能够继续被替换下去的符号。

rule:
1. 一般用尖括号“<>”扩起非终结符。
2. 一般用大写字母表示非终结符。

2.2 终结符集 $V_T$ (terminal symbols)#

终结符的含义是，不能够继续被替换的符号。

rule:

  1. 一般不用尖括号扩起。
  1. 一般用**小写字母**表示终结符

2.3 规则集 $P$ (prescriptions)#

定义：

规则(重写规则/产生式/生成式)，是一种形如 $\alpha \to \beta$ , $\alpha ::= \beta$ , $(\alpha,\beta)$ 的有序对。读作: $\alpha$ 定义为 $\beta$

其中 $\alpha$ 是规则的左部， $\alpha \in (V_N \cup V_T)^*,且至少包含一个非终结符$

$\beta$ 是规则的右部， $\beta \in (V_N \cup V_P)^*$

2.4 识别符(开始符) $S$ #

定义:

识别符 $S$ 是一个非终结符，即 $S \in V_N$ 。

rule: 1. 识别符 $S$ 至少需要在一条规则中的左部出现。 1. 一般第一条产生式的左部就是识别符 $S$ 1. 文法 $G$ 还可以表示为 $G[S]$ ，突出识别符 $S$

2.5 字母表(字汇表)V#

定义:

字母表 $V = V_N \cup V_T$ 。

另外:

V_N \cap V_T = \varnothing

故 $\{V_N,V_T\}$ 是 $V$ 的一个划分。

3. 推导#

3.1 直接推导#

定义:

若规则 $\alpha \to \beta$ 是文法 $G$ 的一条规则，且有 $\delta,\gamma \in V^*$ , $\exist v,w$ 满足:

v = \delta \alpha \gamma \ \ \ \ w=\delta \beta \gamma

其中 $\delta,\gamma$ 可以是空串。

则以下说法等价:

$v$ 应用规则 $\alpha \to \beta$ 直接推导出 $w$
$w$ 直接归约到 $v$
$w$ 是 $v$ 的直接推导
$v$ 是 $w$ 的直接归约
$v => w$

3.2 长度大于0的推导 $v \xRightarrow{+} w$ #

定义:

如果有推导序列:

v => w_1 => w_2 => \cdots => w_n => w (n>0)

则称:

$v$ 推导到 $w$ , 长度为 $n$
$w$ 归约到 $w$
$v \xRightarrow{+} w$

3.3 长度大于等于0的推导 $v \xRightarrow{*}w$ #

定义:

$v = w 可写作v \xRightarrow{0} w$

则 $v \xRightarrow{+} w$ 或者 $v = w$ ，写作 $v \xRightarrow{*}w$ ，读作: $v$ 推导到 $w$

4. 句型、句子、语言#

4.1 句型#

定义:

有文法 $G[S]$ ，对某一 $x \in V^*$ , 若 $x$ 可由识别符 $S$ 推导而来，即:

S \xRightarrow{*} x

则称 $x$ 为文法 $G[S]$ 的句型。

Hint:
识别符 $S$ 满足 $S \xRightarrow{*} S(S=S)$ ，但 $S$ 是一个非终结符，故 $S$ 本身是一个句型而不是句子。

4.2 句子#

定义：

有文法 $G[S]$ 和文法 $G[S]$ 上的句型 $x$ ，如果 $x$ 仅由终结符组成或者为空串,即:

S \xRightarrow{*} x \wedge x \in (V_T)^*

则句型 $x$ 为文法 $G[S]$ 的句子。

句子是不包含非终结符的句型。

4.3 语言(Language)#

定义:

对文法 $G[S]$ ,

L[G] = \{x| x \in (V_T)^* \wedge S \xRightarrow{*} x \}

则 $L[G]$ 为文法 $G[S]$ 的语言。

文法 $G[S]$ 的语言是该文法一切句子的集合。[包含空串]

4.4 文法的等价#

定义:

有两个文法 $G_1[S_1],G_2[S_2]$ ,若：

L[G_1] = L[G_2]

则称文法 $G_1$ 和文法 $G_2$ 等价。

两个文法等价当且仅当他们能够表示的语言相同。

5. 文法的类型#

5.1 0型文法（短语文法Phrase Structure Grammar）:图灵机#

定义:

对于一文法 $G[S]$ 规则集 $P$ 中的规则 $\alpha \to \beta$ 都满足:

\alpha \in V^* 并且\alpha 至少包含一个非终结符 \\ \beta \in V^*

即是一个0型文法。

任何0型语言都是递归可枚举的。任何递归可枚举集也都是0型语言。

5.2 1型文法（上下文有关文法 Context-Sensitive Grammar）:线性界限自动机#

定义:

对于一个0型文法 $G[S]$ ，若规则集 $P$ 中的规则 $\alpha \to \beta$ 都满足:

|\alpha| \le |\beta| \vee \beta = \varepsilon

此文法即是一个1型文法。

0型文法规则集中除了 $\beta = \varepsilon$ 的情况，规则右部的长度不小于左部的长度，则文法为一个1型文法。

5.3 2型文法（上下文无关文法 Context-Free Grammar): 下推自动机#

定义：

对于一个0型文法 $G[S]$ ，对于规则集 $P$ 中的规则每一个规则 $\alpha \to \beta$ ，满足:

\alpha \in V_N \\ \beta \in V^*

即每一条规则都形如 $A \to \beta$ ，该文法为一个2型文法。

每一条规则的左部都是一个非终结符的文法就是上下文无关文法。

上下文无关文法也是上下文有关文法。

5.4 3型文法 (正规文法:左线性文法/右线性文法) : 有穷状态自动机#

定义:

对于一个文法 $G[S]$ ，规则集中每一条规则 $\alpha \to \beta$ 都满足:

\alpha = A, A\in V_N \\ \beta = aB \ \vee \beta = \ a , B \in V_N

即规则形如 $A\to a$ 或者 $A \to aB$ 。(一定有终结符，且终结符一定在左边，非终结符可有可无。）

其中 $a \in V_T \cup {\varepsilon}$ 。

此文法为一个3型文法，是一个右线性文法。

定义:

对于一个文法 $G[S]$ ，规则集中每一条规则 $\alpha \to \beta$ 都满足:

\alpha = A, A\in V_N \\ \beta = Ba \ \vee \beta = \ a , B \in V_N

即规则形如 $A\to a$ 或者 $A \to aB$ 。(一定有终结符，且终结符一定在右边，非终结符可有可无。）

此文法也是一个3型文法，是一个左线性文法。

但有的规则终结符在左边，有的规则在右边的文法不是3型文法！

显然，3型文法一定是一个上下文无关文法。

5.5 语言的类型#

不同种文法产生不同种语言。

0型文法 \to 0型语言 \\ 上下文有关文法 \to 上下文有关语言 \\ 上下文无关文法 \to 上下文无关语言 \\ 正规文法 \to 正规语言

6. 上下文无关文法与语法树#

6.1 语法树#

上下文无关文法已经很足够能描述现今的一般的程序设计语言了。因此后续如果出现文法，一般指的就是上下文无关文法。

定义 $6.1.1$ 语法树是一种形象地表示上下文无关文法推导过程的直观工具。也成为推导树。并且只要给定一个上下文无关文法，对于 $G$ 的任何句型，都能够构造出一棵语法树。

语法树满足:

\begin{align} &0. 语法树的根节点是起始符S\\ &1. 语法树的节点都是该文法的字符\\ &2. 语法树的非叶子节点(有后继的节点)都是非终结符节点。 \Leftrightarrow 语法树的终结符都是语法树的叶子节点\\ &3. 非叶子节点A的直接子孙n_1,n_2,\cdots,n_k从左到右连在一起构成了规则集P中一条规则的右部，A是左部 \\ & \ \ \ 也就是有一条文法G的规则A\to n_1n_2\cdots n_k \end{align}

6.2 推导和语法树#

定义 $6.2.1$ 最右(左)推导: ** 如果一个推导每一次都是替换最右(左)边的非终结符，则这个推导称为最右(左)推导**。其中最右推导也被称为规范推导。由规范推导推导而来的句型称为规范句型。

定义 $6.2.2$ 最左(右)归约：如果一种归约每一次都是先把最左(右)边的终结符归约为非终结符，那么这个归约就被称为最左(右)归约。其中最左归约被称为规范归约。

最左归约是最右推导的逆过程。

一种推导就对应一棵语法树。但是一棵语法树一般对应多种推导。比如既对应最左推导也对应最右推导。

但是一棵语法树就只对应一个最右(左)推导。

6.3 语言和语法树#

把一颗语法树的叶子节点从左往右连在一起就是一个文法的句型。

一颗语法树对应一个句型。但是一个句型并不一定只对应一颗语法树。

定义 $6.3.1$ 二义文法: 如果一个文法的某一个句子对应了至少2棵语法树(2种最右推导)，则称该文法是二义的。

注意：语言的二义性和文法的二义性不一样。如果文法 $G$ 是二义的，也会存在另一个文法 $G'$ (可能二义，也可能不是二义的)产生的语言 $L[G']$ 和 $L[G]$ 等价。

定义 $6.3.2$ 语言的二义性: 如果产生语言 $L$ 的所有上下文无关文法 $G$ 都是二义的，才称这个语言是先天二义的。

已经证明: 判断一个文法是否为二义文法，和一种语言是否为二义语言都是递归不可解的。即不存在一个算法，它可以在有限步内给出任何输入的这两个问题的答案。[不存在一个算法，它可以在有限步骤内判断任何一个文法的二义性。]

如果想判定一个文法的二义性，就要找出一个句子，它对应了至少2个正规推导(2棵语法树)。

对于一个程序设计语言来说，我们希望对它的每一个语句的分析都是单一意思的，因此需要消除文法的二义性。

消除文法二义性的办法一般是：为文法的非二义性寻找一组充分条件，比如给文法规定一些运算的结合顺序，保证有的运算先进行。

\begin{align} & S \to T | E + T \\ & T \to F|T*F \\ & F \to (E)|i \end{align}

引入中间变量 $F$ ，保证必须先归约 $()$ 里的E才能归约 $*$ 。

引入中间变量 $T$ ，保证只有当归约 $*$ 后才能归约 $+$ 。

*一定比+更先结合。

7. 句型分析#

7.1 句型分析和分析算法#

定义 $7.1.1$ 句型分析是识别一个符号串是否是某个文法的句型，也就是某个推导的构造过程。

一般把完成句型分析的程序叫做分析程序或者识别程序。

分析算法可以从左往右也可以从右往左分析单词。

分析算法的实现方式主要有：
自顶向下(从开始符号 $S$ 出发，不断推导到该句型)
自底向上(从该句型出发，不断归约到开始符号 $S$ )

7.2 自顶向下的分析方法#

不断利用产生式替换最左非终结符，使匹配上目标句型第一个未被匹配的字符。