正则表达式的表示方法

在词法分析中最重要的运算方式就是并，连接和闭包。

运算	定义
L∪M	串s属于L或者属于M
L·M	串st中s属于L且t属于M
L*	L的kleene闭包L*=∪0<=i<=∞Li
L+	L的正闭包L+=∪1<=i<=∞Li

例如:
L∪M中L∈{a-z或A-Z}，M∈{0-9}则L包含26*2+10=62个字符的集合。
L·M中则表示26*10+26*10=520个长度为2的字符串的集合。
L^*表示所有字母构成的集合包括空串?。
L⁺表示有一个或多个字母构成的串。

下面看一个实例:
C语言中的标识符有以下规则，首字母必须为字母或者下划线，其他字母为字母数字下划线，所以可以构成以下正则表达式: (L|E)·(L|D|E)^* {L∈{a-z|A-Z}, E∈{ _ }, D∈{0-9}。
正则表达式在程序中具有缩写的表示形式 [a-zA-Z0-9]表示L|D，则L|E应该写成[a-zA-Z_], L|D|E则写成[a-zA-Z0-9_]所以上述表达式可以写成:
[a-zA-Z_][a-zA-Z0-9_]*
所以在lex程序中就可以用上述扩展的正则表达式来表示。也可以将其封装:
letter     [a-zA-Z_]
digit      [0-9]

{letter}({letter}|{digit})*
在lex中定义了一个符号后，再使用它就需要在符号两边加花括号。   
在正则表达式的扩展形式中还可以用符号?来表示零个或者1个实例。
digit?表示空集或者一个在≤9的数字。

lex的正则表达式的扩展表示方法:
c             一个字符
\c            字符的转义
"S"          字符串S 
.              除了换行以外的任意字符
^             一行的开始，例如^#代表#符号必须位于本行的开始位置
$             行的结尾，例如abc$，表示c必须位于本行的末尾
[s]           s中的任意字符，例如: [abc]表示a|b|c
[^s]         不在s中的任意字符，例如: [^abc]表示除了abc的任意字符
s*            与串s匹配的0或多个串，例如:a*代表0或n个a
s+            与串s匹配的1或多个串，例如:a+代表1或n个a
s?            与串s匹配的0或1个串，例如: a?代表0或1个a
s{m, n}     最少m个，做多n个s的重复，例如:a{1, 5}代表a或者aaaaa
s1s2         s1后接s2，例如: ab
s1|s2        s1或s2，例如: (a|b)
s1/s2        s1后面必须接有s2，例如: abc/123代表匹配后面接123的abc

编译原理(第二版)            Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffery D.Ullman