文法中正规式、正规集定义

• 语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。
• 词法规则可用3型文法（正规文法）或正规表达式描述，她产生的集合是语言规定的基本字符集∑（字母表）上的一个子集，称为正规集。

正规式和正规集：

对于字母表∑，其上的正规式及其表示的正规集可以递归定义如下：
1. ε（epsilon）是一个正规式，它表示集合 L(ε)=｛ε｝。
2. 若a是Σ上的字符，则a是一个正规式。它所表示的正规集为｛a｝。
3. 若正规式 r 和 s 分别表示正规集L(r)和L(s)，则：
a. r|s 是正规式，表示集合 L(r)∪L(s)。
b. r ·s 是正规式，表示集合L(r)L(s)。
c. r* 是正规式，表示集合（L(r)）* 。
d. (r) 是正规式，表示集合 L(r)。

• 仅通过有限次地使用上述3个步骤定义的表达式才是Σ上的正规式，其中运算符“|”、“·”、“ * ”、分别表示为 或、连接、闭包。 在正规式的书写中，连接运算符 "·"可省略，运算的优先级从高到低顺序排序为“ * ”、“·”、“|”。

设∑=｛a，b｝，下表列出了∑上的一些正规式和相应的正规集。