\documentclass[]{article}
\usepackage[]{}



\begin{document}
\section{A Top-down, depth-first, left-to-right parser}
The following pages provide the Prolog code for a simple top-down, 
depth-first left-to-right parser. There are two versions of the parser
\begin{enumerate}
    \item one that just recognises whether a string of words is a 
    well-formed instance of a given syntactic category, and
    \item one that also builds a parse-tree for the analysis
\end{enumerate}

Both parsers use a grammar, which should be consulted first, because 
the file contains the definition of ==> as an operator, which also 
appears in the parser code.

The code can be saved to your filespace by saving the web page as 
text and giving it a suitable name with a .pl extension.


\subsection{The grammar}
\begin{verbatim}
% declare ==> as an infix operator

 :- op(1050, xfx, `==>').   

% The grammar

s ==> np, vp.
np ==> det, n.
vp ==> v, np.

det ==> the.
n ==> dog.
n ==> cat.
v ==> chased.
\end{verbatim}


\subsection{The parser}
\begin{verbatim}
/* A depth-first, left-to-right parser.
   
   Here is how the parser is called:

| ?- parse(s, [the,dog,chased,the,cat], []).

yes
*/

parse(Cat, [Firstword|Restwords], Restwords):-
    (Cat ==> Firstword).

parse(Cat, String, Rest ):-
   (Cat ==> Daughters),
   parsedaughters(Daughters, String, Rest).

parsedaughters((Cat, Cats), String, Rest):-
   parse(Cat, String, Next),
   parsedaughters(Cats, Next, Rest).

parsedaughters(Cat, String, Rest):-
   parse(Cat, String, Rest).
\end{verbatim} 

\subsection{Variant of the parser that builds trees}
 \begin{verbatim}
/* Variant of the depth-first, left-to-right parser
   that also builds trees in the form of lists of
   lists. It requires the grammar file to be loaded
   first.
   
   Here is how the parser is called:

| ?- parse(s, T, [the,dog,chased,the,cat], []).

T = [s,[np,[det,the],[n,dog]],[vp,[v,chased],[np,[det,the],[n,cat]]]] ? 

yes
*/


parse(Cat, [Cat,Firstword], [Firstword|Restwords], Restwords):-
    Cat ==> Firstword.

parse(Cat, [Cat|Tree], String, Rest ):-
   (Cat ==> Daughters),
   parserest(Daughters, Tree, String, Rest).

parserest((Cat, Cats),  [Tree, Resttree], String, Rest):-
   parse(Cat, Tree, String, Next),
   parserest(Cats, Resttree, Next, Rest).

parserest(Cat, Tree, String, Rest):-
   parse(Cat, Tree, String, Rest).
\end{verbatim}



\section{A Propositional Logic Interpreter}
\begin{verbatim}
/* file logic.pl */

/* A simple program to demonstrate the use of operators in Prolog. 
Logical connectives and, or, if and ~ (negation) are defined as
operators and given the same semantics as their Prolog counterparts. 
A small procedure play/0 is provided to allow the answers 'true' and
'false' to be supplied.  To run the program, type 'play.'  and then
input a propositional calculus expression, followed by a full stop and
carriage return.  e.g.

| ?- play.
> |: p and q.
true
> p and r.
false
> r and r.
false
> q and r.
false
> q or r.
true
> p implies q.
true
> p implies q and r.
false
> p implies q or r.
true
> stop.
Goodbye

Type 'stop.' to finish. */

% Operator definitions

:- op(1000, xfy, or).

:- op(900, xfy, and).

:- op(800, fy, ~).

:- op(1100, xfx, implies).

% Allow Prolog to simply fail if given an unknown 
% predicate

:- prolog_flag(unknown, _, fail).

% Definitions of connectives
~X :- \+ X.
and(X, Y):-  X , Y.
or(X, Y):-   X ; Y.

% This one is cunning, 'X implies Y' is defined with 
% the semantics of  (~X) or Y -- which has the same 
% truth conditions.
 
implies(X, Y):- \+ X ; Y.

% p and q are true.
p.
q.

% Top level. Write a prompt and accept input. Then 
% evaluate input.
play:-
   write('> '),
   read(X),
   evaluate(X).
   
% If X is 'stop', then output 'goodbye' and terminate.
evaluate(X):-
   X = stop,
   write(goodbye), nl.

% If X succeeds, write 'true' and continue.   
evaluate(X):-
   X,
   write(true), nl,
   play.

% Otherwise, output 'false' and continue.   
evaluate(_):-
   write(false), nl,
   play.

:-play.
\end{verbatim}

\end{document}
