From: joel de guzman (joel_at_[hidden])
Date: 2001-05-25 19:07:26
From: "John Max Skaller" :
> 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:
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk