c# - 如何将当前执行状态压入堆栈以便稍后继续执行？

Question

想象一个简单的语法:

(a|ab)c

其中读取 (a 或 ab) 后跟 c。解析树看起来像这样:

   and
   / \
  or  c
 /  \
a   ab

现在给它这个输入:

abc

我们会首先向下遍历树的左侧，匹配“a”，然后返回上一级。由于“a”匹配，“或”也为真，所以转到“c”。 “c”不匹配，我们走到了尽头。

但是它可以选择一条替代路径；如果我们向下遍历到“ab”，我们就会找到一个匹配项。

所以我想为“或”节点做的基本上是这样的:

1. 评估左分支
2. 如果左分支不匹配，尝试右分支
3. 如果左匹配确实匹配，将当前状态压入堆栈，以便我们稍后可以在必要时从这一点继续

然后每当解析器遇到死胡同时，我想从堆栈中弹出一个项目并从那里再次继续。

那是我想不通的部分……我如何从根本上保存当前的调用堆栈？我可以将“ab”节点保存在一个堆栈中，这样我就知道我接下来必须执行那个节点，但它仍然需要知道它需要回退到“or”之后。

---

我认为Chris正在做某事。我们必须找到一种方法来翻译树，这样就不必像那样跳过分支。例如，这个等效的解析树没有那个问题:

     or
    /  \
 and   and
 / \    / \
a   c  ab  c

这次我们向左下方解析，点击“a”，它通过了，所以我们尝试它旁边的“c”节点，失败，“and”失败，“or”必须尝试右分支，.. . “ab”通过，另一个“c”通过，然后整个表达式通过。

Answer 1

你提出问题的方式就有了问题的答案。

您需要保存状态。棘手的部分是识别状态。保存它很容易。

你的问题是解析器在开始解析某些语法规则时“有一个状态”。 (如果您使用 LALR 解析器，这会变得更加困惑，它将许多规则的解析合并到一个状态中)。该状态包括:

• 输入的状态(例如，输入流在哪里？)。
• 解析堆栈的状态(到目前为止看到的左上下文是什么？)
• 解析器应该在哪里继续成功，在哪里继续失败

当您正在解析并面临您所描述的选择时，您需要“保存状态”，对第一个术语运行试解析。如果成功，您可以丢弃保存的状态并继续。如果失败，恢复状态，并尝试第 2 个(和第 n 个备选方案)。 (不管你是否面临备选方案，无脑和保存状态更容易，但这取决于你)。

如何保存状态？将其插入堆栈。 (你通常有一个解析栈，那是一个非常方便的地方!如果你不喜欢那个，添加另一个栈，但你会发现它和解析栈通常同步移动；我只是让解析栈包含一个记录我需要的所有东西，包括输入空间。你会发现“调用堆栈”对部分状态很方便；见下文)。

第一件事是保存输入的位置；这可能是文件源位置，出于优化原因可能是缓冲区索引。那只是一个标量，所以很容易保存。 恢复输入流可能更难；无法保证解析器输入扫描器就在它原来的位置附近。所以你需要重新定位文件，重新读取任何缓冲区，并重新定位任何输入缓冲区指针。一些简单的检查可以使这在统计上很便宜:存储任何缓冲区第一个字符的文件位置；然后确定是否必须重新读取缓冲区是将保存的文件位置与缓冲区起始文件位置进行比较的问题。其余的应该是显而易见的。

如果你重新安排你的语法以最小化它，你将通过更少的缓冲区回溯(例如，你的解析器运行得更快)。在您的特定语法中，您有“(a | ab ) c”，可以手写为“a b?c”。后者至少不会回溯 a 代表的任何内容。

奇怪的部分是保存解析堆栈。好吧，你不必这样做，因为你的试验解析只会扩展你拥有的解析堆栈，并将其恢复到你拥有的解析状态，无论你的子解析是成功还是失败。

“解析器失败的地方”和“成功的地方”只是另外两个标量。您可以将它们表示为解析代码块和程序计数器(例如，延续)的索引，或者表示为调用堆栈上的返回地址(参见？另一个并行堆栈!)，然后是成功/失败的条件测试。

如果您想了解有关后者的一些详细信息，请查看我的 SO answer on hand-coded recursive descent parsers.

如果您开始构建树，或做一些其他作为解析副作用的事情，您将必须弄清楚如何捕获/保存副作用实体的状态，并恢复它。但无论它是什么，您最终都会将其压入堆栈。