Thu, 3 Nov 1994 05:58:52 GMT

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

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.