parsing - Ocaml 解析字符串以生成树

Question

我有一个类似的问题:

How to print a tree structure into a string fast in 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))
我找到了另一个可能谈论这个的链接，但不确定这是否是解决我的问题的一种方式:

Parsing grammars using OCaml

请分享一些想法，谢谢。

Answer 1

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

编写自己的递归下降解析器

使用从解析器生成器生成的解析器

听起来你正在做的事情是你需要一个抽象语法树(你在问题中提到的“树”)。你可以很容易地使用 OCaml 解析器生成器来完成这样的事情，一个好的方法是 Menhir.虽然您也可以编写自己的解析器，但使用 Menhir 或 ocamlyacc 之类的工具为您完成它是一个非常通用且快速的解决方案(与在简单的递归下降中处理非 LL(1) 事物的麻烦相比)解析器)。