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

习惯上,

  • 终结符用小写字母表示,如:i10110
    • $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.