我们都知道编译器要对高级程序设计语言进行词法、语法等分析。要想让计算机能够自动的分析语言,就要把相关的语言学知识,也就是文法提供给计算机。那么在计算机中是如何表示语言及其文法的呢?这就是我们这一章要介绍的内容。


首先我们来看基本概念。

字母表

第一个概念是字母表,我们用符号来表示。一个字母表是一个有穷符号集合,符号的典型例子包括字母、数字、标点符号等等。例如由0和1两个数字构成的集合{0,1}是一个二进制字母表。另外ASCII字符集还有Unicode字符集都是字母表。既然字母表示一个集合,那么我们就可以在字母表上进行一些集合运算。

字母表上的乘积运算

首先我们来看字母表的乘积。

假设∑1和∑2是两个字母表,那么他们的乘积是一个集合,集合中的每个元素有两个符号构成。第一个符号来自于字母表∑1, 第二个符号来自于字母表∑2

例如字母表{0,1}和字母表{a,b}相乘得到的结果是一个集合。集合中的元素分别是{0,a},{0,b},{1,a}和{1,b}。

字母表上的幂运算

接下来我们来看字母表上的幂运算。字母表的n次幂是n个相乘。

0 ={ ε }
n =∑n-1∑,n≥1

例如二进制字母表,他的三次幂等于三个二进制字母表相乘,那么最后得到的集合中的元素都是长度为三的0,1字符串。

{0, 1}3={0, 1} {0, 1} {0, 1} ={000, 001, 010, 011, 100, 101, 110, 111}

可见字母表的n次幂实际上就是长度为n的符号串构成的集合。这里n可以等于零,也就是说的零次幂表示长度为零的符号串构成的集合。长度为零的符号串其实就是没有符号的符号串。我们把它叫做空串,我们这里用一个特殊的符号ε来表示空串。

字母表的正闭包运算

下面我们来看字母表的正闭包运算。字母表的正闭包是的各个正数次幂的并集。

+ = ∑ ∪ ∑2 ∪ ∑3 ∪ …

例如{a,b,c,d}+这个字母表,它的正闭包就是由字母表上长度为一的字符串的集合,并上长度为二的字符串集合再并上长度为三的字符串集合,以此类推。

由此可见,字母表的正闭包实际上就是长度为正数的符号串构成的集合。 例:

{a, b, c, d }+ = {a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}

字母表的克林闭包

下面我们来看字母表的克林闭包。字母表的克林闭包是在字母表的正闭包的基础上再并上一个的零次幂,也就是说在正闭包的基础上,再添加一个空串。

= ∑0 ∪ ∑+ = ∑0 ∪ ∑ ∪ ∑2 ∪ ∑3 ∪ …

由此可见字母表的克林闭包,实际上就是任意符号串构成的集合,这个符号串的长度可以为零。 例:

{a, b, c, d } = {ε, a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}

假设是一个字母表,那么的克林闭包中的每一个元素都称为是上的一个串。

由此可见,串就是字母表中符号的一个有穷序列。字符串s的长度就是指字符串s中符号的个数。

通常我们在s的前后各加一条竖线,用来表示s的长度,记作|s|

例如这个字符串|aab|,它的长度就是三,那么长度为零的字符串称为是空串,用符号ε表示, |ε|= 0。

串上的运算-连接

好了,下面我们来看串上的运算。首先我们来看连接运算。

如果x和y是两个串,那么x和y的连接是指把y附加到x后面而形成的串记为xy。例如如果x等于dog,y等于house,那么xy就等于doghouse。

空串是连接运算的单位元,也就是说对于任意一个串s在他的前面或者后面连接上一个空串得到的还是s。

εs = sε = s

假设x、y、z是三个字符串,如果x=yz,那么y就是x的前缀,z就是x的后缀。

串上的运算-幂

如果把串上的连接运算看做是串的乘法运算的话,那么我们可以定义串的幂运算。

串s的n次幂等于将n个s进行连接。

s1 = s0s = εs = s,s2 = ss,s3 = sss,…

例如若s等于ba那么s的一次幂就等于ba,s的二次幂就等于baba,s的三次幂就等于bababa 依此类推。

这里值得注意的是,s的零次幂是表示将零个s连接起来,这实际上就是空串,所以s的零次幂等于空串。

原文链接:

最后修改日期:2020年5月14日

留言

撰写回覆或留言