我怎样才能将当前执行状态到堆栈，这样我可以从它稍后继续？ [英] How can I push the current execution state into a stack so that I can continue from it later?

问题描述

试想一个简单的语法：

(a|ab)c

其内容（A或AB），其次是温度。解析树是这样的：

Which reads (a or ab) followed by c. The parse tree would look like this:

   and
   / \
  or  c
 /  \
a   ab

现在给它这个输入：

abc

我们会遍历先顺着左侧的树，并匹配A，然后回到了一个级别。由于一匹配，或也是如此，所以移动到C。 C不符的，我们上路的结尾

We would traverse first down the left side of the tree, and match "a", then go back up a level. Since "a" matched, the "or" is also true, so move on to the "c". "c" does not match, and we hit the end of the road.

但有可能采取的替代路径; 。有我们走过下调至AB，我们会发现一个匹配

But there was an alternate path it could have taken; had we traversed down to "ab", we would have found a match.

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

So what I want to do for "or" nodes is essentially this:

1. 评估左支


2. 如果左支不匹配，尝试右支


3. 如果离开了比赛匹配，推进当前状态叠加，使我们可以从这个角度稍后继续如有必要

然后，当解析器陷入死胡同，我想弹出一个项目从堆栈，并从那里再继续。

Then whenever the parser hits a dead end, I want to pop an item off the stack and continue from there again.

这是我想不通的部分.. 。怎么我基本上保存当前的调用堆栈？我可以保存AB节点堆栈，让我知道我必须执行一个下一个，但后来它仍然需要知道它需要回落到或之后。

That's the part I can't figure out...how do I essentially save the current call stack? I can save the "ab" node in a stack so that I know I have to execute that one next, but then it still needs to know it needs to fall back up to the "or" afterwards.

我觉得克里斯是要发生什么。我们必须找到一种方法来转换树，这样就不必遇到像那个分支跳转。例如，这相当于解析树不存在这样的问题：

I think Chris was on to something. We have to find a way to translate the tree such that it isn't necessary to jump across branches like that. For example, this equivalent parse tree doesn't have that problem:

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

这一次，我们解析下来的左边，点击是，它传递的，所以我们尝试一下旁边的C节点，即失败和失败或已尝试右支，......AB通过，其他的C通过，然后整个表达式通行证。

This time we parse down the left, hit "a", it passes, so we try the "c" node beside it, that fails, "and" fails, "or" has to try the right branch, ... "ab" passes, the other "c" passes, and then the whole expression passes.

推荐答案

您有答案的方式你的问题，你提出它。

You have the answer to your question in the way you posed it.

您需要保存的状态的。最棘手的部分是确定的状态。保存很容易。

You need to save the state. The tricky part is identifying the state. Saving it is easy.

您的问题是解析器有一个状态，它开始分析一些语法规则时。 （如果您使用的LALR分析器，它融合了许多规则解析到一个单一的状态，这得到混乱）。该州包括：

Your problem is that the parser "has a state" when it starts parsing some grammar rule. (This gets messier if you use an LALR parser, which merges the parsing of many rules into a single state). That state consists of:

• 的状态的输入的（例如，在哪里输入流？）。


• 解析栈的状态（就是左边的背景下迄今所看到的？）


• 其中解析器应该继续成功，以及在哪里继续失败

• the state of the input (e.g., where is the input stream?).
• the state of the parse stack (what is the left context seen so far?)
• where the parser should continue for success, and where to continue for failure

当你分析，面对你所描述的一个选择替代品，你需要拯救国家，跑在第一项试验解析。如果成功的话，你可以扔掉保存的状态，然后继续。如果出现故障，恢复状态，并尝试第二次（第n替代品）。 （它更容易被愚笨和不管你是否面临替代只是保存状态，但是这取决于你）。

When you are parsing and face a choice alternative as you have described, you need to "save the state", run a trial parse on the first term. If successful, you can throw away the saved state and continue. If failure, restore the state, and try the 2nd (and nth alternatives). (Its easier to be brainless and just the save state regardless of whether you face an alternative, but that's up to you).

你怎么能保存状态？推入堆栈。 （你通常有一个解析栈，这是一个非常方便的地方，如果你不喜欢，添加另一个堆栈，但你会发现同步它和一般的举动解析协议栈;！我只是做了解析堆栈包含了创纪录所有的东西，我需要，包括对输入空间，你会发现在调用堆栈方便国家的部分;见下文）。

How can you save the state? Push it into a stack. (You typically have a parse stack, that's a pretty convenient place! If you don't like that, add another stack but you'll discover it and the parse stack in general move synchronously; I just make the parse stack contain a record with all the stuff I need, including space for the input. And you'll find the "call stack" convenient for parts of the state; see below).

的第一件事就是拯救的输入的位置;这可能是一个文件源位置和可能的原因，优化的缓冲指数。这只是一个标量，因此很容易保存。的恢复的输入流可能更难;有没有gaurantee解析器输入扫描仪是接近它在何处的任何地方。所以，你需要重新定位文件，重新读取任何缓存，并重新定位任何输入缓冲区指针。一些简单的检查，可以使这个统计便宜：存储任何缓冲的第一个字符的文件位置;那么deteimining如果你不得不重新读取缓冲区是比较具有缓冲启动文件位置保存的文件位置的问题。其余的应该是显而易见的。

The first thing is to save the input location; that is likely a file source position and for optimizing reasons likely a buffer index. That's just a scalar so it is pretty easy to save. Restoring the input stream may be harder; there's no gaurantee that the parser input scanner is anywhere near where it was. So you need to reposition the file, re-read any buffer, and reposition any input buffer pointer. Some simple checks can make this statistically cheap: store the file position of the first character of any buffer; then deteimining if you have to re-read the buffer is a matter of comparing the saved file position with the buffer start file position. The rest should be obvious.

您会通过减少缓冲区（例如，您的解析器运行速度更快）原路返回，如果你重新排列你的语法，以尽量减少。在特定的语法，你有（A | AB）C，这可能是用手A B C？重写。后者将至少不会在任何一个代表原路返回。

You'll backtrack through fewer buffers (e.g, your parser runs faster) if you rearrange your grammar to minimize that. In your specific grammar, you have "(a | ab ) c", which could be re-written by hand to "a b? c". The latter will at least not backtrack across whatever a represents.

奇数部分是节省了解析堆栈。那么，你不必，因为你的试用解析只会延长你解析栈，并将其恢复到你有你的subparse无论是成功还是失败的解析状态。

The odd part is saving the parse stack. Well, you don't have to, because your trial parse is only going to extend the parse stack you have, and restore it to the parse state you have whether your subparse succeeds or fails.

，其中解析器的推移失败和里那张成功只是两个标量。你可以代表他们为你解析代码块索引和程序计数器（例如，延续）或您的调用堆栈上的返回地址（请参阅？另一个平行叠！）后跟条件测试成功/失败。

"where the parser goes on fail" and "where it goes on success" are just two more scalars. You can represent them as indexes of your parsing code blocks, and program counters (e.g., continuations) or as a return address on your call stack (see? another parallel stack!) followed by a conditional test to success/failure.

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

If you want some details on the latter, check out my SO answer on hand-coded recursive descent parsers.

如果你开始建立的树木，否则做一些如解析的副作用，你就必须弄清楚如何捕获/保存侧实现实体的状态，并恢复它。但不管它是什么，你最终会推动它在堆栈上。

If you start building trees, or doing something else as a side effect of the parse, you'll have to figure how to capture/save the state of the side-effected entity, and restore it. But whatever it is, you'll end up pushing it on a stack.

这篇关于我怎样才能将当前执行状态到堆栈，这样我可以从它稍后继续？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！