A play on regular expressions: functional pearl
A play on regular expressions: functional pearl
复制标题
正则表达式的游戏：功能性珍珠
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
T. Wilke
中科院分区：
文献类型：
--
作者：
Sebastian Fischer;F. Huch;T. Wilke
Cody、Hazel和Theo，两位经验丰富的Haskell程序员和自动机理论专家，开发了一个优雅的Haskell程序来匹配正则表达式：（i）程序是纯函数式的;（ii）它在任意半环上都是重载的，这不仅允许解决普通的匹配问题，而且还支持其他应用，如计算最左最长匹配或匹配数，所有这些都用一个算法实现;（iii）它比其他匹配器更强大，因为它可以通过利用懒惰来解析每一种上下文无关语言。
开发的程序是基于一种旧的技术，将正则表达式转换为有限自动机，这使得它在最坏情况下的时间和空间界限以及实际性能方面都很有效：尽管它很简单，但Haskell实现可以与最近发布的专业C++程序竞争相同的问题。
Cody, Hazel, and Theo, two experienced Haskell programmers and an expert in automata theory, develop an elegant Haskell program for matching regular expressions: (i) the program is purely functional; (ii) it is overloaded over arbitrary semirings, which not only allows to solve the ordinary matching problem but also supports other applications like computing leftmost longest matchings or the number of matchings, all with a single algorithm; (iii) it is more powerful than other matchers, as it can be used for parsing every context-free language by taking advantage of laziness.
The developed program is based on an old technique to turn regular expressions into finite automata which makes it efficient both in terms of worst-case time and space bounds and actual performance: despite its simplicity, the Haskell implementation can compete with a recently published professional C++ program for the same problem.