Imagine a simple grammar:

```
(a|ab)c

```

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

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

```

Now given it this input:

```
abc

```

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.

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. Evaluate left branch
2. If left branch doesn't match, try right branch
3. If left match does match, push current state on to stack so that we can continue from this point later if necessary

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

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](https://stackoverflow.com/a/9747020/65387) 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

```

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.