在Haskell中将字符串解析为其他数据类型

Question

最近我一直在尝试用Haskell创建一个正则表达式解释器。我所做的是创建一个新数据类型，其中包含所有可能的构造函数（序列、*、^、区间等），然后定义一个匹配函数。它效果很好，但我的问题是，我必须将输入（例如字符串"a(b*)(c|d)ef"）转换为我的数据类型（"Seq (Sym a) (Seq (Rep Sym b) (Seq (Or Sym c Sym d) Sym ef))"）。我在这个问题的部分遇到了麻烦（我尝试创建一个新的数据类型，即解析树，但我完全失败了）。你有什么想法可以帮我解决这个问题吗？

- Iulia Muntianu

---

如果你不是只为了好玩而构建这个项目，那么还有Text.Regex可供使用。 - Jani Hartikainen

http://www.haskell.org/haskellwiki/Parsec：我不知道它的细节，但它是一个非常好的用于解析的库...使用它还可以教你很多关于单子的东西。 - Riccardo T.

Answer 1

经典的方法是使用解析器组合库，例如Parsec。 解析器组合库（类似于解析器生成器）允许您编写语法描述，从而产生语言中字符串到令牌的解析器。 您只需要将您的语法编码为一个Parsec函数。

例如，请参见此先前的SO问题：Using Parsec to parse regular expressions。

- Don Stewart

---

@Jani Hartikainen：不幸的是，我不被允许使用Text.Regex。 - Iulia Muntianu

谢谢，我会尝试使用Parsec并看看我能做什么。 - Iulia Muntianu

Answer 2

这是一篇关于正则表达式实现的有趣文章（一份剧本）:

正则表达式的一场戏

- JJJ