这点知识，貌似也是编译原理课程的一个考点…………

（直接从正则表达式构造DFA的）

正则表达式，接触得已经不少，各种语言都会有些正则表达式的库来增强字符串处理功能，这里就编译原理的词法分析要用到的内容浅析下下。

嗯，我很懒……还是课件截图：

这里用递归定义来定义正则的，原因是简洁方便，方便以后进一步学习，比如NFA。如果要说正则表达式的术语定义，又得找维基了，链接%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F

“在计算机科学中，是指一个用来描述或者匹配一系列符合某个句法规则的字符串的单个字符串”

简单点讲，就是用一种方便点的表达式来描述一个复杂的语言。

举个例子：a(a|b)*b这个正则表达式表示的意义就是a开头，b结尾的，由a和b构成的字符串的集合。

NFA，Nondeterministic Finite Automata，不确定的有限状态自动机。

要先理解FA先，也就是有限状态自动机，其实就是个识别器，只能对每个可能的输入串简单地回答“是”或“否”。

然后NFA是一种FA，其特点是在某个状态S下输入某个字符a，可以进入多个不同状态，还有就是空串ε也可以作为输入字符标号。

这里继续举例说明：