# Re: prolog and recursive descent parsing?

## "oliverhunt@gmail.com" <oliverhunt@gmail.com>Tue, 18 Sep 2007 18:55:48 -0000

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: "oliverhunt@gmail.com" Newsgroups: comp.compilers Date: Tue, 18 Sep 2007 18:55:48 -0000 Organization: Compilers Central References: 07-09-067 Keywords: prolog, parse Posted-Date: 19 Sep 2007 15:56:33 EDT

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

Post a followup to this message