Wed, 19 Sep 2007 19:51:24 GMT

Related articles |
---|

prolog and recursive descent parsing? carl_thinks_cs@yahoo.com (carl immanuel manalo) (2007-09-16) |

Re: prolog and recursive descent parsing? oliverhunt@gmail.com (oliverhunt@gmail.com) (2007-09-18) |

Re: prolog and recursive descent parsing? haberg@math.su.se (2007-09-19) |

Re: prolog and recursive descent parsing? peter.ludemann@gmail.com (2007-09-21) |

From: | haberg@math.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | Wed, 19 Sep 2007 19:51:24 GMT |

Organization: | Virgo Supercluster |

References: | 07-09-067 |

Keywords: | prolog, parse |

carl immanuel manalo <carl_thinks_cs@yahoo.com> wrote:

*> How does prolog use recursive descent parsing to solve problems given*

*> to it?. Does it make a graph of the parse tree or something?*

The Haskell Hugs <http://haskell.org/hugs/> comes with a Mini-Prolog demo,

and fiddling around with it is great. There is also the book Sterling &

Shapiro, "The Art of Prolog". And the Usenet newsgroup comp.lang.prolog.

In brief, the Prolog engine keeps a list of statements, called goals,

and looks for a substitution that proves them from the database,

starting of with the initial query. It lops off the first goal in the

list, and checks for unifications (substitutions that make the

expressions identical) with the heads of the database statements, and

if there is a match: if the statement has empty body, it is a proof,

and if it is non-empty, the body statements are added to the list of

goals. And so, recursively.

Thus, it makes a first depth of the proof tree, also specializing the

goals (a mathematical proof of the original statement does not admit

specialization of the statements in the goal list, only those in the

database). It works like an ordinary function stack that can branch

the search for functions (when unification matches more that one

statement in the database).

Hans Aberg

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.