编译原理课程设计
图
图中,有一种特殊的转换&)转换,表示输入一个空字符,由一个状态转换为另一个状态。例如
状态(到*,(到+之间的转换就是&)转换。&)转换是的一种特有的转换。另外,状态'
输入字符,可以转换为或者(,是不确定的,这也就是成为不确定性有限状态自动机的原因。
图中有两个圈的状态,-表示终结状态,即找到匹配正则表达式的字符串。
与相对应,表示确定性有限状态自动机。与不同,
不存在&)转换,并且每一个状态转换函数的值只对应一个状态,即一个状态输入一个字符,只
能有一个状态相对应。
NFA与DFA的区别
...显然,更加适合我们进行字符串匹配,因为输入一个字符,总能从一个状态确定地转换为另一个
状态,直到终结状态。一个输入可能对应多个状态,因此需要进行回溯,先尝试一条路径,发现走
不通,再回退到原来的状态尝试另外一条路径,显然匹配算法不如简单。
...给定一个,总有一个与之对应,即一个可以转换成一个等价的,我们将使用子集构
造算法实现到的转换。
转换算法
子集构造算法
...首先,我们将正则表达式转换为,采用的算法是算法。对&)和字符,我们构造如
下之等价的如图:
图
...对基本的操作符//0/1,我们构造如下与之等价的如图(: