如何将当前执行状态推送到堆栈中以便以后可以继续执行？
想象一个简单的语法：
(a|ab)c 其中读取（a或ab）后跟c。 解析树看起来像这样：
and / \ or c / \ a ab
现在给它这个输入：
abc
我们首先遍历树的左侧，然后匹配“a”，然后返回一个级别。 由于“a”匹配，“或”也是如此，因此转到“c”。 “c”不匹配，我们走到了尽头。
但它可以采取另一条路径; 如果我们走到“ab”，我们就会找到一场比赛。
所以我想要为“或”节点做的基本上是这样的：
- 评估左分支
- 如果左分支不匹配，请尝试右分支
- 如果左匹配匹配，则将当前状态推送到堆栈，以便我们可以在以后必要时继续
然后每当解析器遇到死胡同时，我想从堆栈中弹出一个项目并再次从那里继续。
这是我无法弄清楚的部分……我如何基本上保存当前的调用堆栈？ 我可以将“ab”节点保存在堆栈中，这样我就知道我必须接下来执行那个节点，但是之后它仍然需要知道它需要后退到“或”。
我认为克里斯有所作为。 我们必须找到一种翻译树的方法，这样就不必像这样跳过树枝。 例如，这个等效的解析树没有这个问题：
or / \ and and / \ / \ ac ab c
这次我们解析左边，点击“a”，它通过，所以我们尝试旁边的“c”节点，失败，“和”失败，“或”必须尝试正确的分支，……“ab “通过，另一个”c“通过，然后整个表达通过。
你可以用你提出的方式回答你的问题。
你需要保存状态 。 棘手的部分是确定国家。 保存很容易。
您的问题是解析器在开始解析某些语法规则时“有状态”。 （如果使用LALR解析器，将许多规则的解析合并为单个状态，则会变得更加混乱）。 该州包括：
- 输入的状态（例如，输入流在哪里？）。
- 解析堆栈的状态（到目前为止看到的左上下文是什么？）
- 解析器应该继续成功的地方，以及继续失败的地方
当您解析并面对您所描述的选择替代时，您需要“保存状态”，在第一个术语上运行试验解析。 如果成功，您可以丢弃已保存的状态并继续。 如果失败，恢复状态，并尝试第二（和第n个替代）。 （无论你是否面对另一种选择，它都更容易变得无脑，只有拯救状态，但这取决于你）。
你怎么能拯救国家？ 将其推入堆栈。 （你通常有一个解析堆栈，这是一个非常方便的地方！如果你不喜欢它，添加另一个堆栈但你会发现它并且解析堆栈通常同步移动;我只是使解析堆栈包含一个记录我需要的所有东西，包括输入的空间。你会发现“调用堆栈”方便部分状态;见下文）。
首先是保存输入位置; 这可能是文件源位置，并且出于优化原因可能是缓冲区索引。 这只是一个标量，因此很容易保存。 恢复输入流可能更难; 没有任何关于解析器输入扫描器在任何地方附近的保证。 因此，您需要重新定位文件，重新读取任何缓冲区，并重新定位任何输入缓冲区指针。 一些简单的检查可以使这在统计上更便宜：存储任何缓冲区的第一个字符的文件位置; 然后确定是否必须重新读取缓冲区是将保存的文件位置与缓冲区起始文件位置进行比较的问题。 其余应该是显而易见的。
如果重新排列语法以最小化，那么您将通过更少的缓冲区（例如，您的解析器运行得更快）回溯。 在你的特定语法中，你有“（a | ab）c”，可以用手重写“ab？c”。 后者至少不会回溯任何代表。
奇怪的部分是保存解析堆栈。 好吧，您不必这样做，因为您的试用解析只会扩展您拥有的解析堆栈，并将其恢复到您的子解析成功或失败的解析状态。
“解析器继续失败的地方”和“成功的地方”只是另外两个标量。 您可以将它们表示为解析代码块的索引，程序计数器（例如，continuation）或作为调用堆栈上的返回地址（请参阅？另一个并行堆栈！），然后是成功/失败的条件测试。
如果你想了解后者的一些细节，请查看我在手工编码的递归下降解析器上的答案。
如果你开始构建树，或者做其他事情作为解析的副作用，你将不得不想象如何捕获/保存副作用实体的状态，并恢复它。 但不管它是什么，你最终会把它推到堆栈上。
你应该做的是为每种可能性调用一种方法。 如果你走到了死胡同，你可以回来，你将会回到原来的位置，并准备好尝试下一个选项。
您可以通过从解析方法返回值来指示是否成功解析了分支。 例如，您可以返回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
您将需要一个更复杂的结构来处理更难的情况（无论是队列还是堆栈都取决于您在重建状态时如何构建和销毁）
你需要使用递归。
就像是：
in或语句中的每个语句bool ret = eval（statement）if（ret）bool recVal =调用递归if（recVal）比你找到一个路径停止递归。 否则我们继续在另一个循环中尝试下一个语句。