Backtracking parsers

Michael Lee Finney <michael.finney@acm.org>
30 May 2000 02:32:37 -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)
[5 later articles]
| List of all articles for this month |

From: Michael Lee Finney <michael.finney@acm.org>
Newsgroups: comp.compilers
Date: 30 May 2000 02:32:37 -0400
Organization: Lynchburg.net (lynchburg.net)
Keywords: parse, question

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.


I had never considered this approach, and certainly it would
substantially increase the bookkeeping involved in writing a
backtracking parser.


However, once we understood the miscommunication, the question that
arose is: does backtracking in that manner increase the expressiveness
of the grammar, and if so, how? Also, are there any advantages in
doing so. Or, perhaps, am I mistaken and that is the normal approach
for backtracking?


One observation is that backtracking in that manner would be
equivalent to extracting the definition of prod2, prod3 and prod4 and
substituting them directly into the definition of prod1. Backtracking
in the other manner would be equivalent to encapsulating the
definitions of prod2, prod3 and prod4 so that once recognized, they
are all or nothing.


Does anyone have any insights into this?


Post a followup to this message

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