我最初的方法是：用户将提供正则表达式的哈希映射,将正则表达式映射到令牌枚举.程序将按照给定的顺序逐个遍历正则表达式,看看它们是否与字符串的开头匹配(我可以在每个正则表达式的开头添加^来实现它).如果他们这样做,我可以将该正则表达式的令牌添加到该程序的令牌列表中.
我的第一个问题是,这是最有效的方法吗？目前我必须遍历每个正则表达式,但理论上我可以从所有正则表达式组合构建DFA并更有效地逐步执行.但是,创建此DFA会产生一些开销.
我的第二个问题是,我如何实现最长的匹配字符串连接断路器,就像flex一样？即,我想匹配ifa作为标识符,而不是关键字if后跟字母a.我没有看到任何有效的方法来使用正则表达式.我想我必须循环遍历所有正则表达式,尝试匹配它们,如果我有多个匹配项,则取最长的结果.但是,如果我将正则表达式转换为DFA(即我自己的DFA数据结构),那么我可以继续单步执行字符,直到DFA上没有可能的过渡边缘.此时,我可以将最后一次通过接受状态作为令牌的实际匹配,因为这应该是最长的匹配.
我的两个问题都指向将自己的翻译从正则表达式编写为DFA.这是必需的,还是我仍然可以使用普通正则表达式(由标准库实现)有效地执行此操作并仍然获得最长的匹配？
编辑：我保留了我正在使用的正则表达式引擎,因为我想要一个通用的答案,但我正在使用Rust的正则表达式库：@L_403_0@
解决方法
通常,您实现maximal-munch(匹配最长的字符串)的方式是正常运行匹配的自动机.跟踪您找到的最后一场比赛的索引.当自动机进入死机状态并停止时,您可以从令牌的开头向上输出子串到匹配点,然后在输入序列中跳回到匹配完成后的点.这可以非常有效地完成,而且根本没有太大的减速.
万一它有帮助,here are some lecture slides from a compilers course I taught探索扫描技术.
希望这可以帮助！
