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 文法的类型
参考文献
- 王生源,董渊,张素琴,吕映芝,蒋维杜. 编译原理. 3 版. 北京:清华大学出版社,2015.