2.1 文法的直观概念

像是英文、中文的语法，程序设计语言也有自己的一套文法——毕竟编译就是翻译语言的过程，而语言需要遵循规定的文法，才能正确、合理地被翻译成另一种语言。

以自然语言为例，我们无法列出所有的句子，但可以给出一些规则，由规则来说明句子的结构。比如用 EBNF 来表示句子的构成规则：

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

显然，我是大学生 这个句子可由以上规则推导而来，符合该文法的定义。

2.1 符号和符号串

基本概念

  • 字母表：符号的非空有限集。如：$\Sigma = {0,1}$
    • 符号：字母表中的元素。符号 $\ne$ 字符
  • 符号串：由字母表中的符号组成的任何有穷序列。如：$0, 1, 01, 1011, \dots$
    • 符号串的长度：符号串中符号的个数。例如，$x = 1011$，则 $|x| = 4$
    • 空符号串：不等于空格串。用 $\epsilon$ 表示，$|\epsilon| = 0$

符号串的运算

符号串的头（前缀）尾（后缀），固有头和固有尾

  • 如果 $z=xy$ 是一符号串，那么 x 是 z 的前缀，y 是 z 的后缀
    • 如果 x 非空，那么 y 是固有尾
    • 如果 y 非空，那么 x 是固有头

例：

  • 符号串 011 的头（前缀）：$\epsilon$, 0, 01, 011
    • 固定头： $\epsilon$, 0, 01
  • 符号串 011 的尾（后缀）：$\epsilon$, 1, 11, 011
    • 固定尾： $\epsilon$, 1, 11

符号串的连接

设 x 和 y 是符号串，它们的连接 xy 是把 y 的符号写在 x 的符号之后得到的符号串

显然有：$\epsilon x = x \epsilon = x$

例：x = 114, y = 514, 则 xy = 114514

符号串的方幂

设 x 是符号串，把 x 自身连接 n 次得到符号串 $z = xx \dots xx$，称为 x 的方幂，写作 $z=x^n$

  • $x^0 = \epsilon, x^1 = x, x^2 = x x, x^3 = x x x, \dots$

例：m = Flan，则 $m^0 = \epsilon, m^1 = Flan, m^2 = FlanFlan, m^3 = FlanFlanFlan$

符号串集合

符号串集合：若集合 A 中的一切元素都是某字母表上的符号串，则称 A 为该字母表上的符号串集合。

  • 例：$\Sigma ={a,b,c}, \quad A={ a,aa,ac}$

两符号串集合 A 和 B 的乘积：$AB = {xy | x \in A \cap y \in B}$

  • 例：A = {a, b}, B = {c, d}, 则 AB = {ac, ad, bc, bd}
  • 因为 $\epsilon x = x \epsilon = x$，所以有 ${\epsilon}A = A{\epsilon} = A$

吐槽：这不就是笛卡儿积嘛……

闭包（Closure）：指定字母表 $\Sigma$ 后，可用 $\Sigma^$ 表示 $\Sigma$ 上的所有有穷长的集合，$\Sigma^$ 称为 $\Sigma$ 的闭包

  • 可表示为字母表的方幂形式：$\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \dots \cup \Sigma^n \dots$
  • 正闭包：$\Sigma^+ = \Sigma^1 \cup \Sigma^2 \dots \cup \Sigma^n \dots$，即在闭包中去掉元素 $\epsilon$

显然有：

  • $\Sigma^* = \Sigma^0 \cup \Sigma^+$
  • $\Sigma^+ = \Sigma \Sigma^* = \Sigma^* \Sigma$

例：$\Sigma = {a, b}$，则

  • $\Sigma^* = {\epsilon, a, b, aa, ab, ba, bb, aab, \dots }$
  • $\Sigma^+ = {a, b, aa, ab, ba, bb, aab, \dots }$

注：要记住闭包是一个集合

2.3 文法和语言的形式定义

规则（重写规则、产生式、生成式）：形如 $\alpha \rightarrow \beta$ 或 $\alpha ::= \beta$ 的 $(\alpha,\beta)$ 有序对，其中 $\alpha$ 称为规则的左部，$\beta$ 称为规则的右部

  • 符号 $\rightarrow$ 或 $::=$ 读作“定义为”

课本这一节介绍了定义 2.1 到 2.6，直接抄过来也没意思，这里写写我对这些定义的理解。

定义 2.1

习惯上，

  • 终结符用小写字母表示，如：i、10110
    • $V_T$，终结符集，会出现在程序中
  • 非终结符用大写字母表示，或是用 <> 括起来，如：A、<表达式>
    • $V_{N}$，非终结符集，程序的语法成分，不会出现在程序中

很多时候只将产生式写出来就能表示文法 G 了，而不用将 G 的四元组显式地写出来

定义 2.3

$v \Rightarrow^+ w$ （碍于 Latex 的局限，实际上“+”应该在双箭头的上面），经 1 步或若干步推导

定义 2.4

$v \Rightarrow^* w$ （“*”应该在双箭头的上面），经 0 步或若干步推导

定义 2.5

句子 $\subset$ 句型，句子是句型的一个特例：

综上，文法描述的语言是该文法一切句子的集合

2.4 文法的类型

参考文献

  1. 王生源，董渊，张素琴，吕映芝，蒋维杜. 编译原理. 3 版. 北京：清华大学出版社,2015.