Re: Q: Recursive Descent w/Backtracking

SCHMIDTG@iccgcc.cs.hh.ab.com writes:
      I have a rough outline of an algorithm that is designed to handle this
      case. It uses a stack to keep track of the set of production choices
      which have been applied and the current input pointer (to string w)
      in case backtracking has to move the pointer back.
      ... Unfortunately, the algorithm is very unclear as to how the
      unexplored the nodes are managed so that the proper node is always
      explored at the right point in time.


      So does anyone have a lucid description of an algorithm which will handle
      backtracking over all possibilites of a grammar tree?


A simple combinator parser will do this by default i.e. you have to
work hard to get it not to backtrack. Descriptions of combinator
parsers can be found in many books on functional language programming,
and there are also a number of good papers on the subject. See the
FAQ in comp.lang.functional for exact references.
--

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