词法分析

正则表达式

正则表达式（RE）是一种用来描述正则语言的更紧凑的表示方法。

正则表达式的定义

上面的优先级的顺序是从高到低

例子

正则语言

可以用正则表达式定义的语言叫做正则语言或正则集合

正则文法与正则表达式等价

对任意正则文法G，存在定义同一语言的正则表达式r。 对任何正则表达式r，存在生成同一语言的正则文法G

正则定义

例子

有穷自动机(FA)

例子

最长字串匹配原则

上面的意思是：假设输入的是<=，那么自动机识别到<之后到达终态，会继续查看下一个符号，尽可能找到最长的匹配。那么对于<=来说，就匹配到2这个终态。

有穷自动机的分类

又穷自动机分成两类：确定的FA——DFA，非确定的FA——NFA

DFA例子

非确定的有穷自动机（NFA）是从状态S出发，沿着标记位a的边不止一个路径

NFA例子

等价性

上面可以看出：正则文法与正则表达式等价，正则表达式与自动机等价 还是NFA比较好识别。但是从计算机的角度来说，DFA比较好实现

带有“生成ε边”的NFA

从上面可以看出，A状态可以在不接收任何字符的情况下进入B状态，但进入B状态之后就不能再接收0号信号。

从正则表达式到有穷自动机

正则表达式（RE）直接到DFA是不太好实现的，所以我们通过NFA

根据RE(正则表达式)构造NFA

例子

1. 先画起始状态和终止状态
2. 把正则表达式分成多个子表达式
3. 然后对各个子表达式进行转换工作

从NFA到DFA的转换

模仿上面怎么写的就可以。

带ε边的和上面的变化不一样，要注意一下，你会发现它没有写A这个状态，而是直接用ABC这个状态描述的。