Re: Q: Recursive Descent w/Backtracking

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


  pjj@cs.man.ac.uk (Pete Jinks) writes:
>Try Prolog, which is exactly suited to this problem. If you *really* want to
>know how to do it yourself, read about how Prolog is implemented.


> Well, 'standard' Prolog (whatever that means) will almost certainly
                                                      ^^^^^^^^^^^^^^^^^^^
> spend exponential time backtracking over all the possibilities. What
> you want is 'dynamic programming' (incredible misnomer, but impossible
                              ^^^^^^^^^^^^^^^^^^^
> to now change), which will allow you to 'investigate' (for some
> meanings of 'investigate') all possibilities in polynomial time.
> ...


Well, XSB Prolog means that (and more). It is 'standard' in that it
accepts the same source language as 'standard Prolog'. To know more
read


@article{warren:memoing:cacm:92,
          author = "D.S. Warren",
          title = "Memoing for Logic Programs",
          journal = "CACM",
          volume = 35,
          number = 3,
          year = 1992,
          pages = "94--111",
          comment = "Also available by ftp cs.suny.sb.edu"
          }


@article{warren:computing:jlp:93,
          author = "D.S. Warren",
          title = "Computing the Well-Founded Semantics of Logic Programs",
          journal = "JLP",
          volume = 17,
          number = "2--4",
          year = 1993
          }


Olivier Ridoux
--

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