Regular Expression是用来定义languages的。那什么又是Language呢？在书中，language的定义是：A language is any countable set of strings over some fixed alphabet。根据这个定义说明，一种Language,首先我们需要明确他的alphabet是什么。比如编程语言的alphabet应该是所有的字母，数字，符号等吧。自然语言的alphabet应该就是所有的字母吧。这也说明，要了解一门语言（什么语言都是），我们应该首先了解它的 alphabet所包含的是什么，只有这样我们才能构建术语该语言的string。Language其实是一个集合，在这个集合上我们可以执行的操作主要有 Union, Concatenation和closure。从这可以看出，对于Language的操作只是对Set的操作的一个子集。比如，我们不能进行交，差等操作。
Regular Expression是一种用来describe语言的方式。如果一门Language是一个有限集合的话，我们可以使用集合的表示方法，如列举，来表达，但是如何一门语言是一个无限集合的话，regular expression就为我们提供了一种表达这种语言的方式。也就是说regular expression的神奇之处是它可以让我们表达无限的集合。但是，需要注意的是RE所能够表达的语言是有限的。那什么样的语言才能够用RE来表示呢？（自动机理论的问题）
Regular Expression其实也是一种语言而已。那么作为语言他的alphabet又是什么呢？首先，它包括他所定义的Language的alphabet。另外它还包括其他四种符号：|， ×，（，）。这集中符号可以算作是操作符。这就跟算术表达式一样。里面的数字就是算术表达式的符号，但是他需要一些算符如+，-，×,/ 来讲这些符号链接起来。那RE中所包含的这些符号有表示什么意思呢？也就是说这些操作的含义是什么，它会对他所定义的alphabet中的字母实行什么样的操作。| 表示的是或，×，表示的是一种repetition, （）的含义和算术表达式中的含义相同。RE中还有一种操作符没有实质的符号，也就是连接。如果a,b是alphabet中的内容，那么ab表示他们的连接。
利用上面定义的三种符号我们可以利用RE来表示很多的语言，但是有时我们会定义额外的操作来使一些常见的操作更加容易。这体现的原则就是：Make Common Case Simple。这和体系结构中ISA的设计中的理念相同。这些额外操作中常见的有：+ （表示1 or More），?(表示0 or 1)， 还有就是所谓的Character classes ，如[a-z]表示a到z的所有小写字母。r{m,n}表示r重复次数介于m和n之间。
阅读(581) | 评论(0) | 转发(0) |
