Re: Backtracking parsers

gneuner@dyn.com (George Neuner)
31 May 2000 23:05:36 -0400

          From comp.compilers

Related articles
Backtracking parsers michael.finney@acm.org (Michael Lee Finney) (2000-05-30)
Re: Backtracking parsers gneuner@dyn.com (2000-05-31)
Re: Backtracking parsers adrian@dcs.rhbnc.ac.uk (2000-06-01)
Re: Backtracking parsers michael.finney@acm.org (Michael Lee Finney) (2000-06-01)
Re: Backtracking parsers gneuner@dyn.com (2000-06-06)
Re: Backtracking parsers michael.finney@acm.org (Michael Lee Finney) (2000-06-09)
Re: Backtracking parsers michael.finney@acm.org (Michael Lee Finney) (2000-06-10)
Re: Backtracking parsers cfc@world.std.com (Chris F Clark) (2000-06-14)
[4 later articles]
| List of all articles for this month |

From: gneuner@dyn.com (George Neuner)
Newsgroups: comp.compilers
Date: 31 May 2000 23:05:36 -0400
Organization: Dynamic ReSolutions, Inc.
References: 00-05-111
Keywords: parse

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.


Post a followup to this message

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