Re: Backtracking parsers

On 30 May 2000 02:32:37 -0400, Michael Lee Finney
<michael.finney@acm.org> wrote:


> prod1 := (prod2 | prod3) prod4
> prod2 := ...
> prod3 := ...
> prod4 := ...
>
>If you are parsing prod1, have recognized prod2 and then fail to
>recognize prod4, the usual method of applying backtracking would be to
>discard the prod2 match and attempt to match prod3 followed by prod4.
>As far as I know this is the way that backtracking is always done.
>
>However, he suggested that what should happen is that, supposing prod3
>contained alternatives, backtracking would occur at the bottom most,
>right portion of prod3 with successive backtracks proceeding up the
>parse tree for prod3.


No insight, but an observation.


If prod2 is itself a prefix to one of prod3's alternatives, it would
make some sense to avoid reevaluating it when possible, but your
example didn't specify this.


Aside from the prefix case, both branches of


        prod1 := (prod2 prod4) | (prod3 prod4)


would have to have been [at least] partially evaluated so that there
is some prod3 state to be continued [unless you want to argue that
continuing an empty tree is semantically different from continuing a
non-existant one :)]. For a linear parser, this would be equivalent
to a breadth first search and would not be terribly efficient in the
general case.


For a parallel parser, however, it might make sense to focus effort on
a positive partial result, perhaps temporarily suspending evaluation
of prod3 to focus on the prod2 branch which has already achieved a
prefix match. But in a parallel parser, the notion of "backtracking"
really isn't relevant ... simply halting computation on failed
branches is easier.




George Neuner
Dynamic Resolutions, Inc.

Return to the comp.compilers page.
Search the comp.compilers archives again.