编译原理与实践：符号和符号串

在一个高级语言程序中，所有能够使用的字符构成的非空有限集，称为字母表，通常用Σ来表示。其中，每个元素称为一个符号。Σ上的一个符号串是指由Σ中的符号所构成的一个有穷序列，也称为字。不包含任何符号的序列称为空字，记为ε。用Σ*表示Σ上所有符号串的全体，空字ε也包含在其中；用φ表示不含任何元素的空集{}，需要注意ε、{}和{ε}的区别。

例如，假设字母表Σ={a，b}，则a和b就是Σ中的符号，由a、b构成的任意一个有穷序列，如aabb等，都是Σ上的一个符号串，且有Σ*={ε，a，b，aa，ab，ba，bb，aaa，…}。

符号串s的长度是指出现在s中的符号的个数，通常记作|s|。例如，aabb是长度为4的串，空字的长度为0。

设U、V是Σ*的两个子集，则U与V的乘积定义为

UV={αβ|α∈U&β∈V}

即：集合UV是由U中的任一符号串与V中的任一符号串连接构成的符号串的集合。一般而言，UV≠VU，但（UV）W=U（VW）。(www.xing528.com)

集合V的n次方幂是指V自身的n次乘积，记为

规定V0={ε}。

令V*=V0∪V1∪V2∪V3∪…，则称V*是V的闭包。记V+=V V*，则称V+是V的正则闭包。

对于上例，Σ的闭包Σ*={ε，a，b，aa，ab，ba，bb，aaa，…}，Σ的正则闭包Σ+={a，b，aa，ab，ba，bb，aaa，…}。