文法 | Dasi's Blog

1. 文法

1.1 概念辨析

语法（syntax）：是语言的结构规则，规定了语言中各个构造的规范形式

语义（semantics）：是语言的构造含义，分为静态语义和动态语义

静态语义：是一系列限定规则，确保程序本身是有意义的
动态语义：是执行时的行为和效果，明确程序的工作和输出是有意义的

文法（grammer）：是用来形式化描述语法工具，实现了从语言的基本符号推导出合法句子，实现了用有穷的规则集描述无穷的句子集

考虑 C 语言中的赋值语句

int x = ;：语法是错误的，因为存在赋值运算符=但是却没有实际值
int x = a + b;：语法是正确的，但是如果a是整型且b是布尔类型，则语义是错误的，因为这样的运算是无意义的

1.2 例子

可以认为，汉语是句子的排列组合，而句子是汉字或词语的排列组合，因此汉语可以看作为句子的无穷集，但汉字和词语是有穷集，我们需要定义一些规则，来说明如何用有穷集来刻画无穷集，即规定一个句子是怎样由汉字和词语组成的

例如“苹果十分打安全香蕉我是手机”就不是一个合法的句子，而“我是大学生”就是一个合法的句子。

在汉语中可以认为句子的其中一种合法形式是“主语+谓语”，而“谓语”的其中一种合法形式是“动词+直接宾语”，因此可以写出如下规则

<句子> ::= <主语> <谓语>
<主语> ::= <代词> | <名词>
<代词> ::= 我 | 你 | 他
<名词> ::= 王明 | 大学生 | 工人 | 英语
<谓语> ::= <动词> | <直接宾语>
<动词> ::= 是 | 学习
<直接宾语> ::= <代词> | <名词>

因此可以利用规则产生如“我是大学生”这样的句子，流程如下

<句子> 
=> <主语> <谓语>
=> <代词> <谓语>
=> 我 <谓语>
=> 我 <动词> <直接宾语>
=> 我 是 <直接宾语>
=> 我 是 <名词>
=> 我 是 大学生

2. 形式语言

2.1 字母表与符号串

字母表（alphabet）：是一门语言中有穷的元素/符号集合，通常用 $\Sigma$ 表示

$\Sigma_\text{English} = \{a,b,\ldots,z\}$
$\Sigma_\text{程序语言} = \{\text{字母,数字,专用符号}\}$
$\Sigma_\text{机器语言} = \{0, 1\}$

终结符：是会出现在最终生成的句子中的基本符号，无法再被替换或推导为其他符号，是源语言中的最小可识别单元

非终结符：也称为变量、语法实体，是在文法中可被规则进一步替换的符号，用于构造句型，但不会直接出现在最终生成的句子中

符号串（string）：是由字母表中的符号按一定顺序组成的有穷序列

符号串的长度是符号串中含有的符号个数
不含任何符号的符号串称为空串，记作 $\epsilon$
符号串的连接：xy 是把 y 的符号写在 x 的符号之后得到的符号串
符号串的方幂： $a^n$ 是把自身连接 n 次得到的字符串，如 $a^0 = \epsilon, a^1=a, a^2=aa$

2.2 符号串集合与语言

符号串集合的运算

乘积： $AB = \{ ab \mid a \in A,\, b \in B \}$ ，如 {a,b}{c,d} = {ac,ad,bc,bd}
方幂： $A^0 = {\epsilon}, A^1 = A, A^k = AA \ldots AA$ ，如若 $A = \{a, b\}$ ，则 $A^0 = \{\epsilon\},A^1 = \{a, b\}, A^2 = \{aa, ab, ba, bb\}$
Kleene 闭包： $A^* = A^0 \cup A^1 \cup A^2 \cup \ldots = \bigcup_{i=0}^\infty A^i$ ，如若 $\Sigma = \{0, 1\}$ ，则 $\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, \ldots\}$ ，即空串以及所有由 0 和 1 构成的任意长度的字符串
正闭包： $A^+ = A^1 \cup A^2 \cup \ldots = \bigcup_{i=1}^\infty A^i$ ，实际上就是 Kleene 闭包去掉了空串

语言（language）：本质上就是一个符号串集合，是从给定字母表 $\Sigma$ 的 Kleene 闭包 $\Sigma^*$ 中选出的、满足特定规则或性质的一个子集，记作 $L \subseteq \Sigma^*$

2.3 规则与文法

规则/产生式（production）：形如 $\alpha \to \beta$ 或 $\alpha ::= \beta$ 的有序对，读作“ $\alpha$ 定义为 $\beta$ ”

文法定义为四元组 $G = (V_N, V_T, P, S)$

$V_N$ ：非终结符集（Nonterminal）
$V_T$ ：终结符集（Terminal）
$P$ ：规则集（Production）
$S$ ：开始符/识别符（Start）
$V = V_N \cup V_T$ ：称为文法 G 的字母表

文法的简化规则

第一条规则的左部是开始符，或者用 G[S] 表示 S 是开始符号
非终结符用“<>”括起，或者用大写字母表示
终结符则用小写字母表示
对于左部相同的产生式 $A \to \alpha, A \to \beta$ ，可以记作 $A \to \alpha|\beta$

加减表达式的文法 G[式子]：

<式子> -> <数字串> | <式子><运算符><数字串>
<数字串> -> <数字> | <数字><数字串>
<数字> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<运算符> -> + | -

2.4 推导与归约

直接推导和直接归约：如果存在产生式 $A \to \gamma$ ，且有 $v = \alpha A \beta, w = \alpha \gamma \beta$ ，那么称 v 直接推导到 w，w 直接归约到 v，记作 $v \Rightarrow w$

推导和归约：若存在 $v = w_0 \Rightarrow w_1 \Rightarrow \ldots \Rightarrow w_n = w$ ，即 v 经过多步（可以是 0 步）产生式推到 w，那么称 v 推导出 w，w 归约到 v，记作 $v \Rightarrow^* w$

令 $V_N = \{S\}, V_T = \{0, 1\}, P = \{S \to 0S1, S \to 01 \}$
存在直接推导 $0S1 \Rightarrow 0011$ 和 $0S1 \Rightarrow 00S11$
存在推导 $S \Rightarrow^* 00001111$

2.5 句型和句子

句型（Sentential Form）：从识别符推出的符号串 $\alpha$ ，即 $S \Rightarrow^* \alpha$

句子（sentence）：是只由终结符组成句型，即 $\alpha \in V_T^*$

语言（language）：上文中提到语言是字母表闭包中满足特定性质的子集，实际上就是文法 G[S] 所能得到的所有句子的集合，记作 $L(G)$

令 $G: S \to 0S1, S \to 01$
则 $S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 0^3S1^3 \Rightarrow \ldots \Rightarrow 0^{n-1}S1^{n-1} \Rightarrow 0^n1^n$
因此 $L(G) = \{0^n1^n | n \geq 1\}$

文法等价：两个文法所定义的语言是一样的，例如 $G_1[A]: A \to 0R, A \to 01, R \to A1$ 和 $G_2[S]: S \to 0S1, S \to 01$ 定义的语言都是 $0^n1^n$

3. 文法类型

文法类型	定义	说明
0 型文法 / 无限制文法	$\alpha \to \beta, \alpha \in V^+, \beta \in V^*$	产生式没有任何形式限制，规则左右两部可以是任意符号串
1 型文法 / 上下文有关文法（Context-Sensitive Grammar）	$\alpha A \beta \to \alpha \gamma \beta$ ，其中 $\alpha, \beta \in V^*, \gamma \in V^+$ ，并且 $ \lvert x \alpha \gamma \beta \rvert \geq \lvert\alpha A \beta \rvert$	每个产生式至少不缩短符号串的长度，A 的替换依赖于它所在的上下文（ $\alpha,\beta$ ），允许存在产生式 $S \to \epsilon$
2 型文法 / 上下文无关文法（Context-Free Grammar, CFG）	$A \to \gamma, A \in V_N, \gamma \in V^*$	每个产生式的左侧必须是单一非终结符，A 的替换不依赖于它左边或右边的上下文
3 型文法 / 正规文法	$A \to aB$ 或 $A \to a$ ，且 $A, B \in V_N, a \in V_T$	产生式限制为线性形式，能够被有限自动机识别

4 种文法类型的定义是逐步增加限制的，因此每一型文法都包含前一型文法

4. 语法树

4.1 规范推导与规范句型

最左推导：在每一步推导中，总是优先替换最左边的非终结符

最右推导 / 规范推导：在每一步推导中，总是优先替换最右边的非终结符

规范句型：由规范推导所得的句型

文法 G：
$E \to E+T | T$
$T \to T \times F | F$
$F \to (E)|i$
句子 $i \times i + i$ 的推导：
最左推导： $E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow i + T \Rightarrow i + T \times F \Rightarrow i + F \times F \Rightarrow i + i \times F \Rightarrow i + i \times i$
最右推导： $E \Rightarrow E + T \Rightarrow E + T \times F \Rightarrow E + T \times i \Rightarrow E + F \times i \Rightarrow E + i \times i \Rightarrow T + i \times i \Rightarrow F + i \times i \Rightarrow i + i \times i$

4.2 语法树

推导树/语法树（Parse Tree）：一种用来直观地表示一个符号串根据文法规则的推导过程的树形结构

每个节点：标记了字母表中的一个符号
根节点：起始符
内部节点：产生式中被替换的非终结符
叶子节点：最终得到的符号串中的各个终结符
直接子节点从左到右的顺序必须与产生式右部一致
A的直接子结点从左到右构成了一个推导 $A \to A_1A_2 \ldots A_n$

二义：存在某个句子对应两棵不同的语法树，即存在某个句子存在两个不同的最左（最右）推导

5. 文法使用

5.1 句型分析

句型分析：识别一个符号串是否为某文法的句型，也就是识别当前符号串是否在语法上正确

自顶向下的分析方法（Top-Down）：从文法的起始符号开始，反复使用各种产生式，寻找与输入符号串匹配的推导，即从根节点向下构造语法树
自底向上的分析方法（Bottom-UP）：从输入的符号串开始，逐步进行归约，直到归约到文法的起始符号，即从叶子节点向上构造语法树

考虑文法G[S]，对于输入串 w = cabd

S->cAd
A->ab
A->a

利用自顶向下的分析方法，先对起始符号 S 利用产生式得到 S=>cAd，此时 c 已经匹配，考虑下一节点 A，利用产生式得到 cAd=>cabd，此时与输入串完全匹配，因此认为 w 是文法 G 的句子

利用自底向上的分析方法，先对符号串 cabd 分析，发现 a 和 ab 都可以归约，考虑对 a 进行归约得到 cAbd，此时没有产生式可以用于归约，因此回溯到上一步对 ab 进行归约得到 cAd，然后再进行归约可以得到 S

5.2 短语与句柄

短语（phrase）：设有文法 G 和句型 $\alpha\beta\delta$ ，如果存在某个非终结符 A 使得 $S \Rightarrow^* \alpha A \delta$ 且 $A \Rightarrow^+ \beta$ ，则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对于非终结符 A 的短语

直接短语：特别的，对上述定义如果有 $A \to \beta$ ，则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对于非终结符 A 的直接短语

句柄（handle）：是自底向上分析中的概念，是当前句型中最左直接短语，即可以立即归约为非终结符的短语，又称为“可归约串”

考虑文法G[E]:

E -> T | E + T
T -> F | T * F
F -> (E) | a | b | c

对于句型 a * b + c

存在 E => a * F + c 且 F => b，那么 b 是句型 a * b + c 相对于非终结符 F 的短语
存在 E => T + c 且 T => a * b，那么 a * b 是句型 a * b + c 相对于非终结符 T 的短语
存在 E => E 且 E => a * b + c，那么 a * b + c 是句型 a * b + c 相对于非终结符 E 的短语
虽然 b + c 是原句型的一部分，因为存在 E => b + c，但是不存在 E => a * E

5.3 短语与语法树

每个子树的叶子节点构成子树根的短语
高度为 2 的子树的叶子节点构成子树根的直接短语
最左边的两层子树的叶子节点构成句柄

第一层的子树根节点 E 对应短语为： $T \times F + i$
第二层的子树根节点 E 对应短语为： $T \times F$
第二层的子树根节点 F 对应短语为： $i$
第三层的子树根节点 T 对应短语为： $T \times F$ ，因为高度为2，因此也是直接短语，因为在最左边，因此也是句柄
第三层的子树根节点 F 对应短语为： $i$ ，因为高度为2，因此也是直接短语

5.4 使用限制

有害规则：虽然形式上符合文法，但是对语言的推导产生负面影响，如引起文法的二义性或增加解析复杂度

多余规则：在文法中存在但实际上对于生成语言没有任何贡献或可以被其他规则替代

不可到达：非终结符不在任何规则的右部出现
不可终止：不能推导出终结符的非终结符

文法 G[S]：7 是不可到达的，6 和 2 是不可终止的

$\begin{aligned} 1.S &\to Be\\ 2.B &\to Ce\\ 3.B &\to Af\\ 4.A &\to Ae\\ 5.A &\to e\\ 6.C &\to Cf\\ 7.D &\to f\\ \end{aligned}$