7

我有一个类似的问题：

如何在 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 解析语法

请分享一些想法，谢谢。

4

2 回答 2

4

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

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

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

于 2012-04-19T02:32:34.540 回答
4

OCaml 发行版包含ocamlyacc一个工具，可以完全满足您的需求（正如 Kristopher 指出的那样，还存在其他工具）。

有关 的一个很好的解释ocamlyacc，请参见例如本教程和相关示例，其中定义了小型表达式语言（类似于您的）的解析器。

于 2012-04-19T06:32:28.440 回答