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

想象一个简单的语法：

(a|ab)c

其内容为（a 或 ab），后跟 c。解析树看起来像这样：

   and
   / \
  or  c
 /  \
a   ab

现在给它这个输入：

abc

我们首先沿着树的左侧向下遍历，并匹配“a”，然后返回上一层。由于“a”匹配，“or”也为真，因此继续处理“c”。 “c”不匹配，我们走到了路的尽头。

但它本可以采取另一条道路：如果我们向下遍历到“ab”，我们就会找到匹配项。

所以我想要对“或”节点做的基本上是这样的：

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

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

这是我无法弄清楚的部分......我如何基本上保存当前的调用堆栈？我可以将“ab”节点保存在堆栈中，以便我知道接下来必须执行该节点，但它仍然需要知道之后需要回退到“or”。

I think Chris https://stackoverflow.com/a/9747020/65387正在做某事。我们必须找到一种方法来平移树，这样就不需要像那样跳过树枝。例如，这个等效的解析树就不存在这个问题：

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

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

按照你提出问题的方式，你已经得到了答案。

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

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

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

当您正在解析并面临您所描述的选择时，您需要“保存状态”，对第一项进行试验解析。如果成功，您可以丢弃保存的状态并继续。如果失败，恢复状态，并尝试第二个（和第n个替代方案）。 （无脑更容易，无论你是否面临替代方案，只是保存状态，但这取决于你）。

怎样才能拯救国家呢？将其推入堆栈。 （您通常有一个解析堆栈，这是一个非常方便的地方！如果您不喜欢这样，请添加另一个堆栈，但您会发现它和解析堆栈通常同步移动；我只是让解析堆栈包含一条记录我需要的所有东西，包括输入空间。您会发现“调用堆栈”对于状态的某些部分很方便；见下文）。

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

如果您重新排列语法以最大限度地减少缓冲区，您将回溯更少的缓冲区（例如，您的解析器运行得更快）。在您的特定语法中，您有“(a | ab ) c”，可以手动将其重写为“a b?c”。后者至少不会回溯 a 代表的任何内容。

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

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

如果您想了解后者的详细信息，请查看我的所以回答手工编码的递归下降解析器。 https://stackoverflow.com/a/2336769/120163

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