Backtracking parsers

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?

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