正则表达式 – 如何在词法分析器中有效地实现最长匹配？
|
我有兴趣学习如何编写像flex这样的词法生成器.我一直在阅读“编译器：原理,技术和工具”(“龙书”),我对flex的工作原理有一个基本的了解.
我最初的方法是：用户将提供正则表达式的哈希映射,将正则表达式映射到令牌枚举.程序将按照给定的顺序逐个遍历正则表达式,看看它们是否与字符串的开头匹配(我可以在每个正则表达式的开头添加^来实现它).如果他们这样做,我可以将该正则表达式的令牌添加到该程序的令牌列表中. 我的第一个问题是,这是最有效的方法吗？目前我必须遍历每个正则表达式,但理论上我可以从所有正则表达式组合构建DFA并更有效地逐步执行.但是,创建此DFA会产生一些开销. 我的第二个问题是,我如何实现最长的匹配字符串连接断路器,就像flex一样？即,我想匹配ifa作为标识符,而不是关键字if后跟字母a.我没有看到任何有效的方法来使用正则表达式.我想我必须循环遍历所有正则表达式,尝试匹配它们,如果我有多个匹配项,则取最长的结果.但是,如果我将正则表达式转换为DFA(即我自己的DFA数据结构),那么我可以继续单步执行字符,直到DFA上没有可能的过渡边缘.此时,我可以将最后一次通过接受状态作为令牌的实际匹配,因为这应该是最长的匹配. 我的两个问题都指向将自己的翻译从正则表达式编写为DFA.这是必需的,还是我仍然可以使用普通正则表达式(由标准库实现)有效地执行此操作并仍然获得最长的匹配？ 编辑：我保留了我正在使用的正则表达式引擎,因为我想要一个通用的答案,但我正在使用Rust的正则表达式库：http://static.rust-lang.org/doc/master/regex/index.html 解决方法
在时间上,将所有正则表达式编译成一个与并行匹配所有模式的自动机相比,效率更高.虽然它可能会大大增加空间使用量(但是相对于模式大小,DFA可能会呈指数级数),因此值得研究这是否会受到影响.
通常,您实现maximal-munch(匹配最长的字符串)的方式是正常运行匹配的自动机.跟踪您找到的最后一场比赛的索引.当自动机进入死机状态并停止时,您可以从令牌的开头向上输出子串到匹配点,然后在输入序列中跳回到匹配完成后的点.这可以非常有效地完成,而且根本没有太大的减速. 万一它有帮助,here are some lecture slides from a compilers course I taught探索扫描技术. 希望这可以帮助！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |