如何将当前执行状态推送到堆栈中，以便以后可以继续执行

本文关键字：执行 继续 堆栈 执行状态 | 更新日期: 2023-09-27 18:28:14

想象一个简单的语法：

(a|ab)c

哪个读（a或ab），后面跟着c。解析树看起来像这样：

   and
   / '
  or  c
 /  '
a   ab

现在给它这个输入：

abc

我们会先从树的左侧穿过，匹配"a"，然后再回到一个水平面。由于"a"匹配，所以"or"也是真的，所以转到"c"。"c"不匹配，我们撞到了路的尽头。

但它本可以走另一条路；如果我们一直走到"ab"，我们就会找到匹配的。

所以我想为"或"节点做的基本上是这样的：

  1. 评估左分支
  2. 如果左分支不匹配，请尝试右分支
  3. 如果左匹配确实匹配，则将当前状态推到堆栈上，以便在必要时稍后从该点继续

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

这是我想不通的部分。。。如何保存当前调用堆栈？我可以将"ab"节点保存在堆栈中，这样我就知道接下来必须执行该节点，但它仍然需要知道之后需要返回到"或"。

我想克里斯知道什么了。我们必须找到一种方法来翻译这棵树，这样就没有必要像那样跳过树枝。例如，这个等价的解析树没有这个问题：

     or
    /  '
 and   and
 / '    / '
a   c  ab  c

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

如何将当前执行状态推送到堆栈中，以便以后可以继续执行

您可以通过提出问题的方式找到答案。

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

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

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

当您在解析时，如您所描述的那样，面临一个替代选择时，您需要"保存状态"，对第一个术语运行试用解析。如果成功，您可以放弃已保存的状态并继续。如果失败，请恢复状态，然后尝试第2个（和第n个）选项。（无论你是否面临另一种选择，无脑和只保存状态都更容易，但这取决于你）。

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

第一件事是保存输入位置；这可能是文件源位置，并且出于优化原因可能是缓冲区索引。这只是一个标量，所以很容易保存恢复输入流可能更困难；解析器输入扫描程序离它原来的位置很近，这是毫无疑问的。因此，您需要重新定位文件，重新读取任何缓冲区，并重新定位任何输入缓冲区指针。一些简单的检查可以使这在统计上变得便宜：存储任何缓冲区的第一个字符的文件位置；如果必须重新读取缓冲区，则需要将保存的文件位置与缓冲区起始文件位置进行比较。剩下的应该是显而易见的。

如果您重新排列语法以最小化缓冲区，您将通过更少的缓冲区进行回溯（例如，解析器运行得更快）。在你的特定语法中，你有"（a|ab）c"，可以手工改写为"a b？c"。后者至少不会反悔于a所代表的一切。

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

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

如果你想了解后者的一些细节，请查看我对手工编码递归下降解析器的SO回答。

如果你开始构建树，或者做一些其他事情作为解析的副作用，你必须想办法捕获/保存副作用实体的状态，并恢复它。但无论它是什么，你最终都会把它推到堆栈上。

您应该做的是为每种可能性调用一个方法。如果你遇到了死胡同，你可以回来，你会马上回到原来的位置，并准备好尝试下一个选项。

您可以通过返回解析方法的值来指示是否成功解析了分支。例如，您可以为成功返回true，为失败返回false。在这种情况下，如果解析返回false，则尝试下一个选项。

只需在返回结果的同时返回您的状态。让我们举一个简单的例子，你可以为每个元素建立一个索引：

Grammer: (a|ab)c
Translated: AND(OR(a,ab),c)
Input: abc
Call AND
Call OR
a matches, return true,1
c does not match, start over
Call OR giving 1
ab matches, return true,2
c matches, return true

您将需要一个更复杂的结构来处理更困难的情况（无论是队列还是堆栈，都取决于您在重新创建状态时如何构建和销毁）

您需要使用递归。

类似于：

在或声明中对于每个语句bool ret=eval（语句）if（ret）bool recVal=调用递归if（recVal）比你找到的路径停止递归。其他的我们在另一个循环中继续，并尝试下一个语句。

相关文章：