# Re: prolog and recursive descent parsing?

## haberg@math.su.se (Hans Aberg)Wed, 19 Sep 2007 19:51:24 GMT

From comp.compilers

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)
| List of all articles for this month |

 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 Posted-Date: 19 Sep 2007 15:59:46 EDT

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?

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