Re: Backtracking parsers

Michael Lee Finney <michael.finney@acm.org>
9 Jun 2000 21:36:09 -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)
Re: Backtracking parsers gneuner@dyn.com (2000-06-20)
Re: Backtracking parsers michael.finney@acm.org (Michael Lee Finney) (2000-06-20)
Re: Backtracking parsers michael.finney@acm.org (Michael Lee Finney) (2000-06-20)
Re: Backtracking parsers michael.finney@acm.org (Michael Lee Finney) (2000-06-30)
| List of all articles for this month |

From: Michael Lee Finney <michael.finney@acm.org>
Newsgroups: comp.compilers
Date: 9 Jun 2000 21:36:09 -0400
Organization: Lynchburg.net (lynchburg.net)
References: 00-05-111 00-05-119 00-06-015 00-06-032
Keywords: parse

gneuner@dyn.com says...
> I may be dense but I'm still missing something ... I don't see how
> inline substitution of the constituant clauses in Prod1 is going to
> make recognition context sensitive if the language itself isn't.
>
> Even if the language is context sensitive and selection of the proper
> alternative requires gestault knowledge independent of the ongoing
> parse, I'm still left with the question:
>
> How do you "continue" a parse of Prod3 that hasn't yet begun?


There are two questions here. Let me clear the last one up first, my
original post was:


>>
I was talking to friend about a grammar, and he suggested that there were
grammar problems that I couldn't see. It turned out to be a communication
problem, but it raised a very interesting question. If you have a grammar
such as:


      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.
<<


However, everywhere in the last paragraphs I used "prod3" I should have
used "prod2". My apologies that I did not see the typo sooner. I saw what
I thought I wrote.


So, you are not continuing prod3, but rather prod2.


Post a followup to this message

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