Re: prolog and recursive descent parsing?

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

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