Re: [boost] Re: [ANN] Spirit C++ parser framework.

From: joel de guzman (joel_at_[hidden])
Date: 2001-05-25 19:07:26

From: "John Max Skaller" :

> 
> (a|b)*abb
> 
> This cannot be parsed by recursive descent, because RD only
> backtracks to the last node containing another choice
> and which _also_ contains the failure. Real backtracking
> backtracks to the last node examined containing another
> choice, it need not contain the subgoal, and the subgoal
> might include success as well as failure (depending
> on whether you want one parse, or all of them).
> 

Right. (a|b) will consume all 'ab's with RD. RD
back-tracks only if a parse is unsucessful. Your
example backtracks (a|b) just to the point where
the overall goal becomes a success. Example:

aabababbaaababb

While RD will make (a|b) subgoal consume all of
the input and thus fails parse because there is still
an abb expected, the true back-tracking parser
that you mentioned backtracks (a|b) at the point:

aabababbaaab ('till here) abb

and the rest is consumed by abb.

Is my understanding correct?
That's very cool! I'm learning a lot from you guys.

... Ok so help me out. Is it ok if I take 'exhaustive'
out from the definition? Or, would you happen to have
a better description?

Thanks a lot,
Joel de Guzman