Ocaml解析字符串以制作树

Question

我有类似这样的问题:

如何在Ocaml中快速将树结构打印成字符串？

但是以相反的方式,我已经有一个字符串,并希望将其解析为一棵树.

例如,我有

type expr = 
  Number of int
 |Plus of expr*expr
 |Prod of expr*expr

我有一个像1 + 2*3 + 4的字符串(与上面的链接略有不同,假设*有更高的程序+)
然后我希望我的结果是一个expr类型Prod(Plus(1,2), Plus(3, 4))

我找到了另一个可以谈论这个的链接,但不确定它是否是解决问题的方法:

使用OCaml解析语法

请分享一些想法,谢谢.

Answer 1

这是一个标准的解析问题：所有编译器/解释器/等都会面临...有很多方法可以解决这个问题，基本上可以归结为以下几点：

• 编写您自己的递归下降解析器
• 使用解析器生成器生成的解析器

听起来您正在做的事情需要抽象语法树（您在问题中提到的“树”）。您可以轻松地使用 OCaml 解析器生成器来完成此类任务，Menhir 就是一个不错的选择。 虽然您也可以编写自己的解析器，但使用像 Menhir 或 ocamlyacc 这样的工具来为您做这件事是一个非常通用且快速的解决方案（与在简单的递归下降中处理非 LL(1) 事物的麻烦相比）解析器）。