How can I push the current execution state onto the stack so that I can continue it later?

Question

Imagine a simple grammar:

(a|ab)c 

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

  and / \ or c / \ a ab 

This input is now set:

 abc 

We will pass first on the left side of the tree and match "a", then return to the level. Since "a" matches, "or" is also true, go to "c". "c" does not match, and we get to the end of the road.

But there was an alternative way that he could take; if we went to "ab" we would find a match.

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

• Left branch score
• If the left branch does not match, try the correct branch
• If the match on the left matches, push the current state onto the stack so that we can continue from this point later if necessary

Then whenever the parser comes to a standstill, I want to pull an element from the stack and continue on.

This is the part that I cannot understand ... how can I save the current call stack? I can save the "ab" node on the stack so that I know that the next one should do it, but then I still need to know that it needs to go back to "or" again.

---

I think Chris was on something. We must find a way to translate the tree in such a way that we do not need to go through such branches. For example, this equivalent parse tree does not have this problem:

  or / \ and and / \ / \ ac ab c 

This time we analyze on the left, click "a", it goes through, so we try to use the "c" node next to it, which fails "and" fails "or" should try the correct branch, ... "ab" goes through , another "c" goes through, and then the whole expression goes through.

Answer 1

You have the answer to your question as you expressed it.

You need to save a state. The hard part is identifying the state. Saving is easy.

Your problem is that the parser “has a state” when it begins to parse any grammar rule. (This becomes useless if you use the LALR parser, which combines the parsing of many rules into one state). This condition consists of:

• input state (for example, where is the input stream?).
• the state of the parsing stack (which left context is still being considered?)
• where the parser should continue to work, and where to continue the failure

When you understand and choose an alternative, as you described, you need to "save state", run the trial syntax for the first time. If successful, you can discard the saved state and continue. If it fails, restore the state and try the 2nd (and n-th option). (It’s easier to be brainless and just keep state regardless of whether you are faced with an alternative, but it is up to you).

How can you keep the state? Push it onto the stack. (You usually have a parser column, this is a pretty convenient place! If you don't like this, add another stack, but you will find it, and the syntax column will generally move in sync, I just create a parser column containing an entry with everything what I need, including input space, and you will find a “call stack” convenient for parts of the state, see below).

First of all, you need to save the input location; this is most likely the position of the source of the file, and probably the buffer index to optimize the reasons. This is just a scalar, so it’s pretty easy to save. Recovering an input stream may be more difficult; there is no guarantee that the parser input scanner is anywhere. Therefore, you need to move the file, re-read any buffer and move the pointer of any input buffer. Some simple checks can make it statistically cheap: keep the file position of the first character of any buffer; then deteimining, if you need to re-read the buffer, it is a matter of comparing the saved file position with the position of the original buffer file. The rest should be obvious.

You will fall back through fewer buffers (for example, your parser is faster) if you change your grammar to minimize this. In your specific grammar, you have "(a | ab) c", which can be manually rewritten as "b? C". The latter, at least, will not return through all that it represents.

The odd part keeps the parsing stack. Well, you don’t need it, because your trial syntax only extends your parsing stack that you have and restores it to the parsing state that you have if your subparameter succeeds or fails.

“where the parser continues to fail” and “where it succeeds” are just two scalars. You can think of them as parser code block indices and program counters (like continuations) or as the return address in the call stack (see "Another parallel stack!"), Followed by a conditional success / failure test.

If you want to know more about the latter, check out my SO answer on hand-coded recursive descent parsers.

If you are starting to build trees or doing something else as a side effect of parsing, you will have to think about how to capture / save the state of the side object and restore it. But whatever it is, you end up pushing the stack.

Answer 2

What you have to do is call the method for every opportunity. If you are at a dead end, you can return and you will return to where you are and are ready to try the next option.

You can indicate whether you successfully parsed the branch by returning a value from the parsing method. For example, you can return true for success and false for failure. In this case, if the parsing returns false, you can try the following option.

Answer 3

Just get your condition back in addition to your result. Let's look at a simple example where you can have an index for each element:

 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 

You will need a more complex structure to handle complex cases (whether it is a queue or a stack, it depends on how you create and destroy the recreation of your state)

Answer 4

you need to use recursion.

Sort of:

in or statement for each statement bool ret = eval (statement) if (ret) bool recVal = call recursion if (recVal) than you find the path, stop recursion. we will continue in another cycle and try the next statement.