正规式 _生活百科

文章插图
正规式【正规式】正规式是一种表示正规集的工具，正规式是描述程式语言单词的表达式，对于字母表∑ 。
基本介绍中文名：正规式
释义：一种表示正规集的工具
r|s是正规式：表示集合L(r)∪L(s)；
r·s是正规式：，表示集合L(r)L(s)；
简介其上的正规式及其表示的正规集可以递归定义如下。① ε是一个正规式，它表示集合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*)*需要注意的是，编译原理里面的正规式叫做範式，和正则表达式不是一个概念，但是有相通之处：都是通过一定的语法规则来描述文法，也就是所谓的匹配。