It is straightforward to write a parser for Prolog and one is given in an appendix. Various lexical symbols are recognised:

                                                           {lexical items}
symbol = (LCword, UCword, numeral,
          open, close, sqopen, sqclose,
          impliedby, notsy, andsy, comma, colon, dot, question,

{\fB Lexical Types. \fP}

An upper-case (UC) word begins with a capital letter and stands for a variable.

The parser produces a parse tree defined by the following data types:

tree = ^ node;

SyntaxClass = ( constant, intcon, variable, func,
                predicate, negate, rule, progrm,
                list );
node = record case tag :SyntaxClass of
          constant    :( cid :alfa );                 { eg. fred }
          intcon      :( n:integer );                 { eg. 99 }
          variable    :( vid :alfa; index :integer ); { eg. X }
          func, predicate
                      :( id :alfa; params:tree );     { eg. h(1,k(p,X)) }
          negate      :( l :tree );                   { eg. not p(7) }
          rule        :( lhs, rhs :tree );            { eg. p <= q and r. }
          progrm      :( facts, query :tree );
          list        :( hd, tl :tree )

{\fB Syntactic Types. \fP}

The index field associated with a variable is used in the renaming of variables as defined in detail later. When a rule is used, a copy of the rule is made in which the variables are renamed. This is done by setting the index fields to a new value. A variable name is considered to be an <identifier,index> pair.

Simple routines build and manipulate the tree structure:

function newnode(t:SyntaxClass) :tree;
   var n :tree;
begin new(n); n^.tag := t; newnode := n

function cons(h, t :tree) :tree;
   var c :tree;
begin c := newnode(list);
      c^.hd := h; c^.tl := t;
      cons := c

function append( a, b :tree ) :tree;
begin if a=nil then append:=b else append:=cons(a^.hd, append(a^.tl, b))

{\fB Tree Manipulation. \fP}

An output routine prints a tree by recursive traversal:

procedure printtree(t:tree; e:Env);
   var v :tree;

   procedure printId(id:alfa);
      var i:integer;
   begin i:=1;
         while i<=10 do
           if id[i]=' ' then i:=11 else begin write(id[i]); i:=i+1 end

   procedure printTail( t :tree );
   begin if t <> nil then
         begin write(', '); printtree(t^.hd, e); printTail(t^.tl) end

   if t<>nil then
      case t^.tag of
         variable:if bound(t, v, e) then printtree(v, e)
                  begin printId(t^.vid);
                        if t^.index<>0 then write('_', t^.index:1)
         intcon:  write(t^.n:1);
         predicate, func:
                  begin printId(t^.id);
                        if t^.params<>nil then
                        begin write('('); printtree(t^.params, e); write(')')
         negate:  begin write(' not '); printtree(t^.l, e) end;
         rule:    begin printtree(t^.lhs, e);
                        if t^.rhs<>nil then
                        begin write(' <= '); printtree(t^.rhs, e)
         list:    begin printtree(t^.hd, e); printTail(t^.tl) end;
         progrm:  begin printtree(t^.facts, e); writeln;
                        write('?'); printtree(t^.query, e); writeln

{\fB Print a Parse Tree. \fP}

A query may contain variables. If the query is satisfied the routine is used to print it. The routine also substitutes the values of any variables if known. These values are contained in an environment which is described in the next section.

[Previous Page] [Next Page] [Index] © L. Allison, Dept. Computer Science, Monash University