Re: Backtracking parsers

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.

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