ANTLR学习心得——抄书(1)

我的BLOG很少，或者说几乎从不抄书，大多数都是原创。但是，这一次，我觉得大抄而特抄一把，因为关于"编译原理"的很多知识，我实在是了解得太少了，东鳞西爪的看各种互联网上的资料，也始终无法认识透彻，我买的那本裘老师翻译的书，又实在是写得过于飘忽，不能明白。还好我是"超星图书馆"的会员，前两天我在图书馆里找到了一本《编译原理》的教材，由陈英编著，一看之下，顿时明白了好多。因此决定照抄出来，至于是不是侵犯陈老师的版权，也不多想了，到时候陈老师要是找我的麻烦，我再给他赔礼道歉吧。
 
定义2．1(字母表)
字母表是元素的非空有穷集合。字母表中的元素称为符号，因此字母表也称为符号集，它包含了语言中允许出现的全部符号。不同的语言可以有不同的字母表，例如，汉语的字母表中包括汉字、数字和标点符号等。二进制数语言的字母表是{0,1}。C语言的字母表可以认为是一切可打印字符组成的集合。通常用希腊字母Σ或大写英文字母等表示字母表，用集合元素表示形式枚举字母表中的符号。例如，字母表A={a,b,c,d}与字母表Σ={0,1}等：

定义2．2(符号串)
由字母表中的符号组成的任何有穷序列称为符号串。
例如，001110是字母表Σ={0,1}上的符号串，字母表A={a,b,c}上的一些符号串有：a,b,c,b,ba,aaca等。通常使用小写字母表示符号串，x=STR表示x是由符号S、T和R，并按此顺序组成的符号串。
符号串总是建立在某个特定字母表上的，且仅由字母表上的有穷多个符号组成。在符号串中，符号的顺序是很重要的，例如符号串ab就不同于ba，abca和aabc也不同。
如果某符号串x中有m个符号，则称其长度为m，表示为|x|=m。例如，定义在字母表Σ＝{0,1}上的符号申00lll0的长度是6。
允许不包含任何符号的符号串，称其为空符号串或空串。空串用ε表不，其长度为0，即|ε|＝0。
从离散数学的角度定义符号串，则有：
(1)字母表Σ上的符号串；
(2)若x是Σ上的符号串，且a∈Σ，则xa或ax是Σ上的符号串；
(3)y是Σ上的符号串，当且仅当y可由(1)和(2)产生。
习惯上，也称符号串为字符串或字。
下面说明符号串的前缀、后缀和子符号串及与符号串相关的概念。
符号串的前缀、后缀和子符号串：设x是一个符号串，把从x的尾部删去0个或者若干个
符号之后剩余的部分称为x的前缀。类似，从x的首部删去0个或若干个符号之后剩余的部
分称为x的后缀。例如，设x=abcd，则ε,a,ab,abc都是x的前缀：而ε,c,bc,abc都是x
的后缀。若x的前缀(后缀)不是x自身，则将其称为x的真前缀(真后缀)。
从—个符号串中删去它的一个前缀或一个后缀之后剩余的部分称为该符号串的子符号
串或子串。例如，x＝abc，则ε,a,b,c,ab,bc,cd,abc,bcd及abcd都是x的子字符串。
在给出符号串定义的基础上，讨论有关符号串的一些运算。

定义2．3〔符号串的连接)
设x和y是两个符号串，如果将符号串y直接拼接在符号串x之后，则称此操作为符号
串x和y的连接，记作xy。
例如，j＝abc，k＝xyz，则jk＝abcxyz，kj＝xyzabc。显然连接运算是有序的。—般来
说xy≠yx，仅当s为空串，则有εx＝xε=x。

定义2．4(符号串的方幂)
设x是某字母表上符号串，把x自身连接n次得到符号串z，即z＝xx…x(n个x)，称是符号串x的n次幂，记作z＝x^n。
设x是符号串，则有定义
x^0=ε
x^1=x
x^2=xx
x^3=x^2x=xx^2=xxx
......
x^n=xx..x(n个x)
例如：x=abc，x^2=abcabc，x^3=abcabcabc。

下面定义几个符号串的集合运算。
定义2．5(符号串集合的乘积)
设A、B是两个符号串集合，AB表示A与B的乘积，则有定义
AB＝{xy|x∈A,y∈B}
例如，设A={ab,c},B={d,ef}，则
AB＝{abd,abef,cd,cef}

注意有{ε}A=A{ε}=A，⊙A=A⊙=⊙，其中⊙为空集。

定义2．6(符号串集合的方幂)
设A是符号串集合，A自身的乘积可以用方幂表示。则有定义
设P为字符串集：
A^0={ε}
A^1=A
A^2=AA
A^3=A^2A=AA^2=AAA
......
A^n=AA...A(n个A)
显然有:
A^(i+j)=A^iA^j
例如，P=(ab,x,aby)，则PP={abab,abx,ababy,xab,xx,xaby,abyab,abyx,abyaby}。

定义2．7(符号串集合的并)
设P、Q为字符串集，集合P∪Q为P和Q的并，它的元素是P或Q中的元素。
例如，  P={0,1,01}  Q={0,10,11,00}，则
P∪Q={0,1,01,10,11,00}

定义2．8(符号串集合的闭包)
设A为符号串集，A的正闭包记作A+，则有
A+=A^1∪A^2∪...∪A^n∪...
A的自反闭包记作A*，则有
A*=A^0∪A+={ε}∪A+=A+∪{ε}
由定义知，A+=AA*。
例如，A={01,10}，则有
A*={ε,01,10,0110,1001,010101,100110,...}
A+={01,10,0110,1001,010101,100110,...}