David M. Lloyd wrote: > On Thu, 4 Oct 2001, Michael G Schwern wrote: > > > > Backtracking is at the heart of Logic Programming (or Declarative > > > Programming, if you like). This is one of the 3 main programming paradigms > > > (along with procedural and functional). The most popular Declarative > > > language is Prolog. It is great for writing programs that are largely about > > > resource allocation and constraints. There's some links to start you off > > > here: > > > > > > http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?backtracking > > > > Sounds like a chess computer. > > It kind of struck me that this type of concept might be handy for writing > parsers directly in Perl without an 'intermediate' parsing language. Or > for making it easier to write such an intermediate language.
Backtracking is typically not used in parser implementations because it's slow over other predictive techniques. It's needed in a few cases of highly ambiguous languages (e.g. LL-infinite parsers). Another idea : it should be possible to write makefile-like rules with backtracking.
