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