Compilers - prolog and recursive descent parsing?

Author

prolog and recursive descent parsing?

carl immanuel manalo

2007-09-18, 8:11 am

How does prolog use recursive descent parsing to solve problems given
to it?. Does it make a graph of the parse tree or something?

I've only encountered recursive descent parsing to solve problems like
boolean algebra or number arithmetic but prolog can do much more than
this.

I understand that it's easy enough to do for facts like.

male(bill).
female(mary).

one only has to compare the query to the facts in the database per
token. but what about rules like?

parent(X,Y):-mother(X,Y).
grandparent(X,Y):-parent(X,Z),parent(Z,Y).

I find it difficult to imagine that you would only check them per
token.

So, how does prolog handle this?

oliverhunt@gmail.com

2007-09-19, 7:16 pm

I'll do my best to answer some of these questions but it's been a long
Time I'Ve Done anything at all involving prolog

On Sep 16, 4:44 pm, carl immanuel manalo <carl_thinks...@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?
I've never heard of anyone solving prolog programs using a parser --
it requires arbitrary levels of backtracking which is doable in a
parser, but doesn't really make sense, especially given the parser
would be requiring semantic knowledge.

> I've only encountered recursive descent parsing to solve problems like
> boolean algebra or number arithmetic but prolog can do much more than
> this.

Ah, now i see. You're not using the parser to solve anything, the
parser merely converts the input into a more readily manipulatable
structure. If we take a simple expression grammar:

expr -> term '+' expr
| term '-' expr
| term
term -> NUMBER
| '(' expr ')'

(which admittedly is not very exciting, and also result in little
problem like incorrect order of operations...)
Now our parser might look like this:
ReturnType expr() {
ReturnType lhs = term();
token = nextToken();
if (token.type == PlusToken)
return createPlusNode(lhs, expr());
else if (token.type == MinusToken)
return createMinusToken(lhs, expr());
else
return lhs;
}

ReturnType term() {
token = nextToken();
if (token.type == NumberToken)
return createNumberNode(token);
else if (token.type == LParenToken) {
ReturnType expression = expr;
if (nextToken().type != RParenToken)
error();
return expression;
} else
error()
}

We could imagine in an OO environment ReturnType might be a simple
tree sctructure, eg:
class Tree{}
class Branch extends Tree {
Tree[] children;
}
class Leaf extends Tree {
Token token;
}

so createPlusNode and createMinusNode would create instances of
Branch, and createNumber would create a Leaf node.

Now if we wanted to just evaluate inline we could say that ReturnType
was float, in which case createPlusNode would return lhs + rhs,
createMinusNode would return lhs - rhs, and createNumberNode would
convert the string form of the number into an actual float.
Spontaneously the parser has become an interpreter, rather than a tree
builder.

For anything more complicated than simple expressions it would not be
possible to do this, but i hope that from this you can see that while
the primary purpose of a parser is to convert an input stream into a
more easily manipulatable structure in certain limited cases it can
(effectively) perform the evaluation.

In any real world grammar this would not be the case.

> I understand that it's easy enough to do for facts like.
>
> male(bill).
> female(mary).
>
> one only has to compare the query to the facts in the database per
> token. but what about rules like?
>
> parent(X,Y):-mother(X,Y).
> grandparent(X,Y):-parent(X,Z),parent(Z,Y).
>
> I find it difficult to imagine that you would only check them per
> token.
>
> So, how does prolog handle this?

The parser would be doing the job of converting the input stream into
a parse tree, it would be the job of the interpreter to actual process
the parse tree[s] afterwards.

In the case of simple predicates, eg:
parent(mary, jane).
parent(bill, sarah).
parent(bill, mary).
parent(bill, alfred).

The interpreter is like to just shove them directly into a database of
some kind (hashtable, etc)
In the case of rules like:
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

Then the interpreter will have to perform semantic analysis of the
rule. Broadly speaking prolog works by string matching and
substitution, so grandparent(bill, jane) would be evaluated along
these lines:
grandparent(bill, jane) :- parent(bill, Z), parent(Z, jane).
* There are two predicates that match parent(bill, Z), Z = { sarah,
mary, alfred} prolog tries first Z = sarah
grandparent(bill, jane) :- parent(bill, sarah), parent(sarah, jane).
* parent(sarah, jane) doesn't exist so prolog backs up to its last
decision point (eg. Z), now it tries Z=mary
grandparent(bill, jane) :- parent(bill, mary), parent(mary, jane).
* all predicates are satisified:
Yes.
* We could try again (hitting "enter" i think?), which causes prolog
to go back to its last decision point, eg. Z. Now Z=alfred
grandparent(bill, jane) :- parent(bill, alfred), parent(alfred,
jane).
* parent(alfred, jane) failes, so we backtrack to Z, now there are no
other possible values for Z so we faile:
No.

And that's basically how the evaluation works (i can't recall the
exact algorithm because it was a long time ago). But it's important
to understand the the evaluation is not being performed by the parser.

--Oliver

Hans Aberg

2007-09-19, 7:16 pm

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

peter.ludemann@gmail.com

2007-09-21, 4:26 am

On Sep 16, 4:44 pm, carl immanuel manalo <carl_thinks...@yahoo.com>
wrote:
> How doesprolog use recursive descent parsing to solve problems given
> to it?. Does it make a graph of the parse tree or something?

"Logic Grammars" by Harvey Abramson, Veronica Dahl is a good
reference, although it goes far beyond what most compilers need; one
of the examples involves Latin, where the words can appear in almost
any order (although I seem to remember someone asking how to do that a
little while ago, for declarations ...)

Most parsing in Prolog uses DCG or similar notation. Here's a
tutorial: http://www.w3.org/People/cmsmcq/2004/lgintro.html
Grammar E2 shows how to write an attribute grammar to produce a parse
tree (in Prolog, there's essentially no distinction between an
attribute you bring into a grammar rule and one you emit -- I used
this once to write a parser that could either explain a C declarations
or generate one from pseudo-English).

There are other, more powerful, notations that DCG - DCTG and EDCG
spring to mind. Google can help you find them.

- peter

Sponsored Links