Re: Q: Recursive Descent w/Backtracking

ridoux@irisa.fr (Olivier Ridoux)
Mon, 7 Nov 1994 08:50:18 GMT

          From comp.compilers

Related articles
Q: Recursive Descent w/Backtracking SCHMIDTG@iccgcc.cs.hh.ab.com (1994-10-21)
Re: Q: Recursive Descent w/Backtracking rockwell@nova.umd.edu (1994-10-28)
Re: Q: Recursive Descent w/Backtracking ichudov@wiltel.com (1994-10-28)
Re: Q: Recursive Descent w/Backtracking davidm@Rational.COM (1994-10-25)
Re: Q: Recursive Descent w/Backtracking bevan@cs.man.ac.uk (1994-10-31)
Re: Q: Recursive Descent w/Backtracking pjj@cs.man.ac.uk (1994-10-28)
Re: Q: Recursive Descent w/Backtracking hbaker@netcom.com (1994-11-03)
Re: Q: Recursive Descent w/Backtracking ridoux@irisa.fr (1994-11-07)
| List of all articles for this month |

Newsgroups: comp.compilers
From: ridoux@irisa.fr (Olivier Ridoux)
Keywords: parse
Organization: Irisa, Rennes (FR)
References: 94-11-027
Date: Mon, 7 Nov 1994 08:50:18 GMT

>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
--


Post a followup to this message

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