1

我有一个非常标准的递归下降解析器。该算法很简单：每个函数从 a 中读取字符，stream然后返回FAIL或调用后续解析函数（由相应的语法规则指定）：

function parseFoo() {
  var ret = parseBar(stream);
  if (ret == FAIL) {
    ret = parseQuax(stream);
    ...
  }
  ...
  return ret;
}

我想解决我stream一次没有完整的情况 - 我异步获取它的部分。因此，我需要的是“可中断性”的特性——我必须能够保存解析器的状态，然后从那时起继续。

遗憾的是，这是嵌套函数调用不可能做到的一件事，因为解析器的所有状态都“存储”在调用堆栈中（按照函数的顺序和它们的局部变量）。

所以我必须以parse*不同的方式构造函数。

我使用的语言是JavaScript。

有人可以指出我如何进行的任何想法吗？

编辑：

  • 我似乎很清楚我需要某种状态机。我无法围绕生成器或延续传递风格，在我看来，在保存状态和恢复时有很多小故障。对我来说，我能想到的最清晰的途径是将嵌套调用转换为某种堆栈，将局部变量重写为存储在堆栈项中的一些哈希图，并以不同的线性方式构造解析代码，这样我就可以轻松地“转到“到某个状态。

  • 我看到的子问题之一可能是：由于我没有完整的stream，我认为我必须尝试多个路径并存储所有部分解析的尝试。例如，如果语法说a = b | cthenb可能太长以至于它没有完全在stream. 所以我不能在解析中“挂起” b，我必须同时尝试并保存部分计算。我对吗？

4

1 回答 1

1

这取决于所使用的编程语言。

您基本上需要一些对延续的支持（您可以将其理解为调用堆栈的抽象）。换句话说，您可能希望以连续传递样式(CPS) 进行编码。

如果使用 C 编码，您可能会对CPC感兴趣。

如果使用 Javascript 编码，您可能需要在 CPS 中手动编码。另请参阅this、this、this question、this pages等......

于 2014-04-17T10:56:03.367 回答