Re: prolog and recursive descent parsing?

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

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