17.2.3 文法

文法是描述语言句子如何生成的规则系统。编译器做语法分析时，不是凭感觉判断程序结构，而是按照文法判断 Token 序列能否推导出来。

文法四元组

一个文法通常写作：

$$G=(V_N,V_T,P,S)$$

组成	含义
$V_N$	非终结符集合，表示还可以继续展开的语法变量
$V_T$	终结符集合，表示最终语言中的基本符号
$P$	产生式集合，描述怎样替换和展开
$S$	开始符号，推导的起点

非终结符像“句子里的占位结构”，终结符像“真正落到纸面上的单词”。例如表达式文法中，E、T 可以是非终结符，id、+、* 可以是终结符。

推导与语法树

产生式 E -> E + T | T 中，竖线 | 表示“或者”。从开始符号出发，不断用产生式替换非终结符，最终只剩终结符，就得到一个句子。

flowchart TB
  E["E"] --> E1["E"]
  E --> P["+"] 
  E --> T["T"]
  E1 --> T1["T"]
  T1 --> ID1["id"]
  T --> ID2["id"]

这棵树可以表示 id + id 的结构。根节点是开始符号，内部节点通常是非终结符，叶子节点是终结符。

闭包符号

形式语言中常用闭包描述“重复多少次”。

写法	含义	是否包含空串 $\epsilon$
$A^{+}$	一个或多个 A	不包含
$A^{\ast }$	零个或多个 A	包含

因此 $A^{\ast }=\{\epsilon ,A,AA,AAA,\dots \}$，而 $A^{+}$ 至少要有一个 A。

Chomsky 文法层次

类型	名称	识别模型	课程/考试关注
0 型	短语结构文法	图灵机	表达能力最强，了解即可
1 型	上下文有关文法	线性有界自动机	比较少考
2 型	上下文无关文法	下推自动机	程序语言语法的核心
3 型	正规文法	有限自动机	词法分析、正规式重点

编程语言的完整语义无法只靠上下文无关文法描述，但语法结构大多由上下文无关文法刻画。词法层面的标识符、数字、关键字等更适合用正规文法、正规式和有限自动机处理。

为什么新层次会替代旧层次

不是越强的文法越好。0 型文法表达力强，但分析代价高，不适合编译器高效识别。正规文法表达能力弱，却足够描述词法规则，而且可以由有限自动机快速识别。上下文无关文法在表达能力和可分析性之间取得平衡，所以成为程序语法分析的主力。

小练习

题：程序设计语言的语法规则通常与哪类文法关系最密切？

答：上下文无关文法，即 2 型文法。

自查

1. 非终结符和终结符的区别是什么？
2. $A^{\ast }$ 为什么可以推出空串？
3. 为什么词法分析更常使用正规文法，而不是表达能力更强的 0 型文法？