3

我正在用 OCaml 编写一个简单的递归下降解析器。通常（据我从在线教程和书籍中得知），异常用于指示解析失败，例如：

match tok with
   TokPlus -> ...
 | _ -> raise SyntaxError

但是，我正在考虑使用选项类型，即：

match tok with
   TokPlus -> Some(...)
 | _ -> None

我想这样做的主要原因是使用选项类型可以让我优化我的一些组合器是尾递归的。

使用选项而不是异常有什么缺点吗？当我开始解析更复杂的结构时，这个决定会咬我的脚吗？

4

3 回答 3

3

不，但是您可能必须添加（很多）虚拟规则才能将错误传播回语法的根产生式。

异常的要点是您不必为每个例程添加异常处理程序；你得到隐式传播。

您是否有特定的原因需要优化尾递归？大多数解析器实际上并不会产生非常深的调用堆栈（对于真正复杂的东西只有几百级）。而且我怀疑与非解析器部分所做的所有其他工作相比，节省的时间是否显着。

于 2011-10-20T08:47:59.520 回答
2

我相信异常优化了常见情况——成功解析的代码路径更简单。通常在解析时是全有或全无 - 要么一切正常，然后返回最终结果，要么出现中断 - 你不在乎它在哪里中断，因为无论如何你都不会处理它，除了打印有意义的消息，但是一个也可以跳过这一步:) 所以看起来是异常的完美匹配。

于 2011-10-20T08:49:33.937 回答
1

递归下降解析的伟大之处在于您可以以任何您喜欢的方式（在合理范围内）编写代码。除非您想象在所有中间函数中捕获异常，否则我看不到有或没有异常递归编写尾部的问题。您更有可能在语法顶部附近有一个（或几个）异常处理程序，在这种情况下，下面的所有代码都可以很容易地尾递归。

所以，我同意 ygrek 的观点，即异常风格对于解析来说是很自然的，而且我认为使用异常并不一定会排除尾递归风格。

于 2011-10-20T15:52:06.367 回答