正规式

其上的正规式及其表示的正规集可以递归定义如下。

① ε是一个正规式，它表示集合L(ε)={ε}。

② 若a是∑上的字符，则a是一个正规式，它所表示的正规集L(a)={a}。

③ 若正规式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)。

仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。

运算符“|”、“·”、“*”分别称为“或”、“连接”和“闭包”。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为：“*”、“·”、“|”。

运算符“|”表示“或”、并集。“*”表示*之前括号里的内容出现0次或多次。

若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规集U和V记作U=V。

b(ab)*=(ba)*b,(a|b)*=(a*b*)*

需要注意的是，编译原理里面的正规式叫做范式，和正则表达式不是一个概念，但是有相通之处：都是通过一定的语法规则来描述文法，也就是所谓的匹配。