下你所需,载你所想!
汇集开发技术源码资料

MYT算法应用分析

:1.36KB :1 :2022-01-04 13:42:16

部分简介

MYT算法应用如果开发者对于本文件有需要的可以参考,使用宽度优先搜索确定每个状态的编号,并且形式化输出。

使用调度场算法把正则表达式转为后缀形式,并且添上连接符'.'
对于几个运算符('.'、'*'、'|'),规定'*'优先级最高,其次是'.','|'优先级最低
例如,对于正则表达式ab*,它的后缀形式为ab*.,
而对于正则表达式(ab)*,它的后缀形式为ab.*

MYT算法的分析
为了应付考试,我们可以说会手工建NFA就行。比较迅速的方法就是从嵌套多的地方入手,像搭积木一样搭建NFA。为了避免出错,建议时刻记住每个转换的添加的边数和空串数。
MYT算法的好处在于,任何字符串都能通过这个算法转换成NFA,它是沿着正则表达式的语法分析树自底向上递归处理的。不过我们可以发现,要添加的空串和边实在是太多了,这为我们后面继续转换成DFA带来了很多不少麻烦,因此这也是有代价的。

热门推荐

相关文章