Re: Q: Recursive Descent w/Backtracking

hbaker@netcom.com (Henry G. Baker)
Thu, 3 Nov 1994 05:58:52 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: hbaker@netcom.com (Henry G. Baker)
Keywords: parse, LL(1), prolog
Organization: nil
References: 94-10-151 94-10-210
Date: Thu, 3 Nov 1994 05:58:52 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.


            Henry Baker
            Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.
            Contact hoodr@netcom.com if you have trouble ftping
--

Post a followup to this message

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