Parser.

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,
          eofsy
         );

{\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 )
end;

{\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
end;

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

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

{\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
   end;

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

begin{printtree}
   if t<>nil then
      case t^.tag of
         variable:if bound(t, v, e) then printtree(v, e)
                  else
                  begin printId(t^.vid);
                        if t^.index<>0 then write('_', t^.index:1)
                  end;
         constant:printId(t^.cid);
         intcon:  write(t^.n:1);
         predicate, func:
                  begin printId(t^.id);
                        if t^.params<>nil then
                        begin write('('); printtree(t^.params, e); write(')')
                        end
                  end;
         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)
                        end;
                        writeln('.')
                  end;
         list:    begin printtree(t^.hd, e); printTail(t^.tl) end;
         progrm:  begin printtree(t^.facts, e); writeln;
                        write('?'); printtree(t^.query, e); writeln
                  end
      end{case};
end{printtree};

{\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.