| 词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言基本字符集∑（字母表）上的字符串的一个子集，称为正规集。
|
|
|
| 对于字母表∑，其上的正规式（正则表达式）及其表示的正规集可以递归定义如下。
|
|
|
| （1）ε是一个正规式，它表示集合L（ε）={ε}。
|
|
|
| （2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为L（a）={a}。
|
|
|
| （3）若正规式r和s分别表示正规集L（r）和L（s），则：
|
|
|
|
|
|
|
|
|
|
|
| 仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。
|
|
|
| 运算符“|”“·”“*”分别称为“或”“连接”和“闭包”。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为“*”“·”“|”。
|
|
|
| 设∑={a，b}，在下表中列出了∑上的一些正规式和相应的正规集。
|
|
|
|
|
|
|
| 若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如，b（ab）*=（ba）*b，（a|b）*=（a*b*）*。
|
|
|
