% -*- Mode: TeX Fill-*-

\documentstyle{article}
\addtolength{\topmargin}{-.5in}
\addtolength{\textheight}{1in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
\parindent = 0in
\parskip = .2in
\begin{document}
\begin{center}{\Large The 6.863 Earley Parser}\end{center}

\section{Introduction}

The 6.863 Earley parser will work with any well-defined context-free grammar,
including recursive ones and those containing empty categories.  It can use
either no lookahead or a one word lookahead, {\it i.e.\ }\(k = 0\) or \(k =
1\).  A feature system has been overlaid on the parser, allowing powerful
grammars to be created more easily than with a simple CFG.  Although this
feature system does not by any means implement any reasonable variation of the
GPSG theory, it will be referred to as GPSG for historical reasons.

In addition to the parser, the Earley system has Lisp facilities for creating
and editing CFG and GPSG grammars, dictionaries, and sentence sets.

\section{Loading the System}

All of the parser and utility code is Common Lisp, and were all Common Lisps
equal, the parser would be machine independent.  The files are set to load into
the package {\tt USER} The file {\tt earley.lisp} contains all the necessary
code.

\section{A Quick Overview}

The Earley system stores various types of {\em rule sets}, such as CFG
grammars, GPSG grammars, or sentence sets.  These can be edited and used as
input for the parser.  The parser requires special grammar tables as input,
which are compiled from featureless context-free grammars (GPSGs are
automatically translated into featureless CFGs).

To look at the rule sets stored, evaluate {\tt (list-all)}.  This prints out
the name, type, and number of rules in each rule set.  There are 6 different
types of rule sets: CFG, GPSG, CFG-TABLE, GPSG-TABLE, SENTENCES, and
DICTIONARY.  The -TABLE types are used as input for the parser.  They can not
be edited, but all other types of rule sets can.

\subsection{Parsing Sentences}

Before we can parse a sentence we need to supply grammar information.  The
parser requires a DICTIONARY and either a CFG-TABLE or a GPSG-TABLE before it
can parse.  Parsing is handled through the {\tt p} function.  Let's say we have
the CFG-TABLE {\tt CT} stored, and also the dictionary {\tt DICT}.  We can parse
the sentence ``John saw Mary'' by evaluating

\begin{verbatim}
>  (p '(JOHN SAW MARY) :grammar 'CT :dictionary 'DICT)
\end{verbatim}

which will return a list of valid tree structures.  The grammar and dictionary
variables are sticky, so now that we've specified the grammar to use, to parse
``John walked into the tree'' only requires

\begin{verbatim}
>  (p '(JOHN WALKED INTO THE TREE))
\end{verbatim}

Parses are returned as lists of possible tree structures, where each tree
structure has the form {\it(Category SubTree1 SubTree2 \ldots)}.  Thus for the
above example we might get back the parse list

\begin{verbatim}
  ((ROOT (S (NP (N JOHN)) 
            (VP (VP (V WALKED))
                (PP (P INTO) (NP (D THE) (NP (N TREE))))))))
\end{verbatim}

The full form of the {\em p} function is

\begin{verbatim}
(p sentence &key (template '*) grammar dictionary (use-lookahead t)
                 print-states file sentence-set)
\end{verbatim}

where {\tt sentence} can either be a list or a string; {\tt :template}
specifies which parses are to be accepted; {\tt :grammar} and {\tt :dictionary}
specify the grammar and dictionary to use; {\tt :use-lookahead} specifies
whether or not to use lookahead if it is available; {\tt :print-states}
specifies whether or not to print out all the Earley states at the end of the
parse; {\tt :file}, if given, is the name of a file to send all output to; and
{\tt :sentence-set} specifies a set of sentences to parse.  After a parse has
been completed the function {\tt retrieve-parses} with the format

\begin{verbatim}
  (retrieve-parses &optional (template '*))
\end{verbatim}
can be used to retrieve the results again.  More parsing functions,
including ones to parse sets of sentences at one time, are given in the
function listing later.

\subsection{Editing Rule Sets}

If there is a rule set {\tt SD}, a DICTIONARY, it can be listed by evaluating
{\tt (list-rules 'SD)}.  This will print out all of the rules (dictionary
entries) in the set.  A template may be specified, so all verbs in {\tt SD}
could be listed with {\tt (list-rules 'SD '(* V))}.  Likewise, all rules with
verb phrases as heads in the CFG {\tt GRAMMAR1} could be listed with
{\tt (list-rules 'GRAMMAR1 '(VP **))}.

{\em List-rules} does more than just print out rules: it also sets up rule
sets for quick editing.  Let's say we evaluated {\tt (list-rules 'SD '(* A))}
to list out all the adjectives in the dictionary {\tt SD}.  Perhaps the result
was

\begin{verbatim}
>  (list-rules 'SD '(* A))
  1.    HARD A
  2.    QUICK A
  3.    RED A
  4.    SLIMY A
  5.    SLOW A
\end{verbatim}

We can now use the three functions {\tt ADD}, {\tt DEL}, and {\tt RPL} to
edit the dictionary {\tt SD}.  To delete ``hard'' and ``slimy'' we evaluate
{\tt (del 1 4)}.  Now, we decide to add ``lazy'' in their place, so we do
{\tt (add '(LAZY A))}, and finally we decide to replace ``quick'' with
``fast'' and ``slow'' with an adverb, ``slowly'' - {\tt (rpl 2 '(FAST A) 5
'(SLOWLY ADV))}.  These three functions work on the last rule set listed with
{\tt list-rules}.  Thus they permit quick and easy editing of grammars,
dictionaries, and test sentences.

\subsection{Creating and Removing Rule Sets}

To simply remove or add a rule set, we can use the functions
{\tt (remove-rule-set name)} and {\tt (add-rule-set name type)}.  Then rules
can be added or removed from them either by using the previously mentioned
editing functions, or through

\begin{verbatim}
  (add-rule name-of-rule-set rule)
  ;; (add-rule 'GRAMMAR1 '(S ==> NP AUXP VP))

  (del-rule name-of-rule-set rule)

  (add-rule-list name-of-rule-set rule-list)
  ;; (add-rule-list 'DICT '((THE D) (AND CONJ)))

  (del-rule-list name-of-rule-set rule-list)
\end{verbatim}

These will not help us generate the tables the parsers need for running, but
only base rule sets.  Specialized functions are provided to compile rule sets
into -TABLEs. Translating a CFG {\tt GRAMMAR1} to a CFG-TABLE {\tt CT} usable
by the parser takes one step, which requires specifying the root node of the
CFG and also whether \(k = 0\) or \(k = 1\).  The lookahead table takes little
time to compute, so presumably $k$ will be $1$.  The translation function is
{\tt create-cfg-table}, which takes the form

\begin{verbatim}
  (create-cfg-table table-name cfg-name root k)
\end{verbatim}
or in our case, with root {\tt ROOT}

\begin{verbatim}
  (create-cfg-table 'CT 'GRAMMAR1 'ROOT 1)
\end{verbatim}

The corresponding function for GPSG grammars is {\tt create-gpsg-table}, which
takes the same arguments.

\subsection{Templates}

There are two places templates are used, in retrieving parses and in listing
rule sets.  They merely provide a filtering system to either limit the types of
parse tree structures accepted or limit the types of rules to be printed.  Look
back to the respective sections for more background information.

Templates follow four basic rules
\begin{enumerate}
\item A symbol matches itself or any list with that symbol as it's first
element, or car.
\item A list matches another list if each element matches, or if each
element before a double asterisk in the template list matches the other
list.
\item An asterisk * matches any symbol or list.
\item A double asterisk ** matches any symbol or list unless it appears
in a list, in which case it matches any ending to that list.
\end{enumerate}
thus the template {\tt NP} matches {\tt NP} and {\tt (NP (N JOHN))},
the template {\tt (* V)} matches {\tt (JUMP V)}, and the template
{\tt (* ==> NP **)} matches any list with {\tt ==>} as it's second
element and {\tt NP} as it's third element.  For instance, if we had
just parsed a sentence which 26 different structures, we might want to
examine only those with an adjunct prepositional phrase attached to the verb
phrase after the object.

\begin{verbatim}
>  (retrieve-parses '(ROOT (S NP (VP * PP **) **)))
\end{verbatim}

\subsection{Loading and Saving Rule Sets}

Some rule sets can be saved in text files designed to be read back with the
standard Lisp {\tt load} function.  Unfortunately, because Lisp has problems
reading arrays, rule sets of type CFG-TABLE and GPSG-TABLE can not be saved.
So even if a text file is used to store a base grammar, the parser tables must
be recompiled before use.

To save rule sets to a readable text file, use the function {\tt save-rules}
supplying as arguments the name of the file and the names of all the rule sets
we wish to save.  If only the file name is supplied, all rule sets possible to
save are saved.  Below two rule sets are saved, deleted, and reloaded.  given
below.

\begin{verbatim}
>  (save-rules "~/rules.lisp" 'RULE-SET-1 'RULE-SET-2)
>  (remove-rule-set 'RULE-SET-1)
>  (remove-rule-set 'RULE-SET-2)
>  (load "~/rules.lisp")
\end{verbatim}

\subsection{Incidental Warnings}

Many functions will return incedental messages as they run.  These less
important messages can be toggled by evaluating {\tt (verbose)}, or can be
specified with {\tt (verbose :set nil)} and {\tt (verbose :set t)}.  Detailed
information on GPSG parsing is printed when {\tt verbose} is turned on.

\section{Rule Formats}

Dictionary entries and CFG or GPSG rules have certain required formats.
A DICTIONARY entry must by a list with the first element the symbol for
the word, and all other elements either symbols or lists representing
the categories the word can take. Thus sample entries are {\tt (WALK N
(V Action + Tense INF))} and {\tt (I (PRO Pers 1st))}.  A dictionary without
features will work with a GPSG set of rules, but each word will be
featureless.  Likewise, features will be ignored when using a GPSG
dictionary with a CFG.  If a word is entered multiple times (each time
with one or more definitions), the union of the sets of definitions will
be used.

CFG rules take the format {\tt (HEAD ==> T1 T2 ... Tn)} where $n$ can
even be zero, representing an empty category.  Each element in the list
must be a symbol and the second element must be {\tt ==>}.  A  GPSG
rule has GPSG categories substituted for symbols.  A GPSG category is
either a symbol (like a CFG category) or a list with the category type
as it's first element.  After the first element come pairs of items, the
first being a feature name and the second being a value, either a symbol
or a category.  Features to be matched for unification can be specified
with a value starting with ``?''.  Some valid CFG and GPSG rules are  

\begin{verbatim}
  ;; CFG
  (NP ==> D N)
  (S ==> NP VP)
  (NP ==> ) ;; empty category
  ;; GPSG
  ((AUX ADV +) ==> AUXADVP)
  ((AP WH ?a) ==> (AP WH ?a) (VP FIN ?b / (NP WH ?b)))
  ((NP PL +) ==> (D) (N PL +))
  ((S FIN ?val) ==> (NP WH -) (AUX FIN ?val) (VP FIN ?val))
\end{verbatim}

The parser does not parse GPSGs directly, but instead parses a featureless set
of rules and then adds features and performs unification later.  This means
that parsing may go very quickly for GPSGs, but parse retrieval may take
longer.

Sentence sets treat sentences as rules, and each sentence can either be a
string or a list of words (symbols).  The sentences can be parsed as a group,
making multiple tests a bit easier.

\section{Debugging Parses}

The parsing function {\tt p} will print out the states generated by the Earley
parser while it runs if the {\tt :print-states t} argument is given.  But this
often doesn't provide enough information for debugging GPSG parses.  After a
parse has been completed the function {\tt states} can be used to get more
detailed information about what occurred.

{\tt (states start end \&key matching print-parses print-rules)}

{\tt states} takes two arguments which specify the start point and end point
of states to be printed.  In other words, it only prints information about
completed states that build phrases between the starting and ending points.  If
{\tt :print-rules} is specified to be true, then along with each state a
corresponding GPSG rule is printed.  If {\tt :print-parses} is true, then all
of the phrases that were created are printed for each state.  The
{\tt :matching} argument is a filter to apply to these phrases.  Each of the
states is printed with an asterisk preceding it if no phrases were produced
during the GPSG unification process.

\begin{verbatim}
>  (p '(who saw mary) :print-states t)
_ 0  0   *D0* ==> . ROOT $
_ 0  0   ROOT ==> . S

...

_ 3  3   S-W/NP ==> . S/NP
_ 3  3   S-W/NP ==> . AUX S-NOAUX/NP
_ 3  3   S-W/NP ==> . AUX S/NP
(((ROOT)
   ((QBAR) ((NP WH + PRO +) ((PRO WH +) WHO))
           ((S-W FIN + / NP)
             ((S FIN + / NP OBJ-MOVT -)
               ((NP / NP))
               ((VP FIN +) ((V2 FIN +) SAW)
                           ((NP WH -) ((NAME) MARY))))))))

>  (states 1 3)
_ 1  1   VP ==> V2 NP .
_ 1  1   S/NP ==> NP/NP VP .
* 1  1   R ==> S/NP .
_ 1  1   S-W/NP ==> S/NP .

>  (states 1 3 :print-rules t)
_ 1  1   VP ==> V2 NP .
  Rule: ((VP FIN ?A) ==> (V2 FIN ?A) (NP))
_ 1  1   S/NP ==> NP/NP VP .
  Rule: ((S FIN + / NP OBJ-MOVT -) ==> (NP / NP) (VP FIN +))
* 1  1   R ==> S/NP .
  Rule: ((R) ==> (S FIN + / NP OBJ-MOVT + REL +))
_ 1  1   S-W/NP ==> S/NP .
  Rule: ((S-W FIN ?A / ?B) ==> (S OBJ-MOVT - FIN ?A / ?B))

>  (states 1 3)
_ 1  1   VP ==> V2 NP .
_ 1  1   S/NP ==> NP/NP VP .
* 1  1   R ==> S/NP .
_ 1  1   S-W/NP ==> S/NP .

>  (states 0 1 :print-parses t)
_ 0  0   NP ==> PRO .
((NP WH + PRO +) ((PRO WH +) WHO))
* 0  0   ROOT ==> NP .
\end{verbatim}

{\tt states} prints an asterisk in front of a state if that state failed to
produce any phrases during the GPSG feature-passing portion of a GPSG parse.
Unfortunately {\tt states} can not provide any information on why a rule might
have failed.  Using the {\tt :print-parses} option lets you see the phrases
that result from successfull rule applications, but not failed ones.  This
information is available during the parse by parsing with {\tt verbose} on.
For instance, we can find out why the starred state {\tt * 1 1 R ==> S/NP .}
failed

\begin{verbatim}
>  (verbose :set t)
T
>  (p '(who saw mary))
Done CFG Parse.
Rule Failure:  (R) ==> (S FIN + / NP OBJ-MOVT + REL +)
Sub Trees:  (S FIN + OBJ-MOVT - / NP)
Rule Failure:  (S FIN + OBJ-MOVT +) ==> (NP WH - / NIL) (VP FIN +)
Sub Trees:  (NP WH + SPECIFIC +) (VP FIN +)
Rule Failure:  (S FIN + OBJ-MOVT + / ?SLASH) ==> (NP WH - / NIL)
                                                 (VP FIN + / ?SLASH)
Sub Trees:  (NP WH + SPECIFIC +) (VP FIN + / NP)
Done Parse Retrieval
\end{verbatim}

While this provides the information we need, in a large parse it can be
difficult to sift through the entire printout to find the desired failure
points.

\section{GPSG Rules and Feature Passing}

GPSG rules are preprocessed before parsing.  Their features are stripped to
created a featureless CFG that is used by the parser in the first stage of
parsing.  Parse trees that are recovered by the initial parse are augmented
with features in a second pass that utilizes the original featured rules.

Features are used to refine rules without multiplying out the number of
categories.  If a rule has in its right hand side a category with a certain
feature specification, then whatever subphrase matches that category must have
the same feature specification.  This can be used to ensure, for instance, that
a rule matches only plural NPs and not just NPs in general without having to
create a seperate category for plural NPs.  Feature values can be passed
upwards, so that a phrase inherits feature values from its daughters.

With the feature system it is possible to create ridiculously baroque devices.
As much care as possible should be taken to avoid unchecked feature generation;
unfortunately the simplicity of the context-free-grammar formalism sometimes
necessitates this.

In a GPSG rule, each category can either be a simple category symbol or a list
of a category symbol and feature-value pairs.  A feature-value pair is a
combination of a symbol that names a feature and a value for that feature.
Possible GPSG categories are {\tt NP}, {\tt (NP)}, {\tt (NP PLURAL +)} and
{\tt(NP PLURAL ?X / VP)}.  In these categories the symbols {\tt plural} and
{\tt /} are feature names and {\tt +}, {\tt ?X} and {\tt VP} are feature
values.  Features found in the left hand side of a GPSG rule are given to the
phrase produced by the rule.  Features on the right hand side refine which
daughters will match the categories- daughter phrases must contain the features
specified.  So the rule

{\tt ((NP PLURAL +) ==> (DET SING -) ADJ (N PLURAL +))}

will fire if its first daughter has the value {\tt -} for its {\tt SING}
feature and the third daughter has the value {\tt +} for its {\tt PLURAL}
feature.  Naturally the categories {\tt DET}, {\tt ADJ} and {\tt N} must also
match.  Notice that the rule does not imply that the second daughter can not
have features; it does not matter what extra features the daughters have so
long as the specified ones match.  The rule will produce a {\tt NP} phrase that
has the value {\tt +} for its {\tt PLURAL} feature, and no other features.

\subsection{Feature Matching Semantics}

Two values are considered equal for the purposes of matching if they are {\tt
eq} or if one of them is the {\tt car} of the other, or if one of them is {\tt
*}, or if they are both lists and each subelement matches.

If a category specification specifies a value for a certain feature and the
phrase it is matching does not contain a value for that feature (or the value
is {\tt nil}), then the specification matches so long as the feature name does not
start with {\tt +}.  So the specification {\tt (NP PLURAL -)} will match {\tt
(NP)} and {\tt (NP PLURAL -)}, but {\tt (NP +PLURAL -)} will only match {\tt
(NP +PLURAL -)}, not {\tt (NP)}.

\subsection{Unification}

If a specification contains a symbol starting with {\tt ?} in a feature value
slot, then that symbol will match any value in that slot.  Furthermore, if the
same symbol is found in another part of the same or a different specification
in the same rule, it must match the same value it matched before.  The symbol
can be used in the left hand side of a rule to define a feature value.  The
rule

{\tt ((NP CLR ?X) ==> (DET PLURAL ?A) (ADJ COLOR ?X) (N PLURAL ?A))}

specifies that the value for {\tt PLURAL} must be the same in the first and
third daughters, and that the value for the {\tt COLOR} feature in the second
daughter will be given to the resulting phrase in the {\tt CLR} feature.

If a feature is not present in a daughter phrase, then unification does not
take place on its value.  So if the {\tt N} daughter does not contain a value
for the {\tt PLURAL} feature (or it is {\tt nil}), then {\tt ?A} is left free
to vary in the {\tt DET} phraseq.  And if {\tt COLOR} is not specified for {\tt
ADJ}, then the resulting {\tt NP} will have no feature specification for {\tt
CLR}.

\subsection{The Slash Feature}

It is possible to include empty categories in a grammar by just putting in
rules of the sort {\tt (X ==>)} but this often leads to gross overgeneration
and inefficiency in a complex grammar, especially in the system used here where
the initial parsing is done without feature information.  A good solution is to
automatically augment the rules with information about empty categories.  Empty
categories are written {\tt ((X / X) ==>)} and rules are multiplied out to
explicitly include empty category information in the slash feature {\tt /}.
The slash feature is automatically propagated from one daughter to its parent,
so that a rule like {\tt (A ==> B C)} generates two additional rules, {\tt ((A
/ ?SLASH) ==> (B / ?SLASH) C)}, and {\tt ((A / ?SLASH) ==> B (C / ?SLASH))}.

The slash feature has special feature-passing semantics associated with it.
First of all, slash propagation does not occur in rules that have a slash
feature specification in their left hand side.  So none of the rules {\tt ((A /
nil) ==> B C)} and {\tt ((VP / NP) ==> V)} and {\tt ((VP / NP) ==> V (NP /
NP))} will generate any new subrules.  This provides a way to ensure that rules
do not allow unwanted empty categories.  Secondly, the slash feature is only
passed up from one phrase on the right hand side at a time.  This is why the
rule {\tt (A ==> B C)} did not generate any rule of the form {\tt ((A / ?SLASH)
==> (B / ?SLASH) (C / ?SLASH))}.  Thirdly, slashes are never propagated from a
category specification that already includes the slash feature.  So {\tt (A ==>
(B / Z) C)} only generates the one additional rule {\tt ((A / ?SLASH) ==> (B /
Z) (C / ?SLASH))}.  Finally, if a specification includes a slash then it will
only match a phrase that has a slash feature, {\it i.e.}, {\tt (X / ?SLASH)}
will match {\tt (X / Z)} but not {\tt (X)}.

Slashes are folded into the featureless rules used by the CFG parser in the
initial stage of parsing a GPSG grammar.  This is why it is more efficient to
parse with slashed rules.  Instead of the rule {\tt ((A / ?SLASH) ==> B (C /
?SLASH))} being represented as {\tt (A ==> B C)} it actually becomes {\tt (A/X
==> B C/X)} and {\tt (A/Y ==> B C/Y)} and so on for all possible empty
categories {\tt X} and {\tt Y}.  While this greatly multiplies the number of
rules it turns out to be significantly more efficient (figure out why for
yourself).  Many of the rules are removed before parsing by some obvious
filters.

\section{Function Summary}
\newcommand{\descfn}[2]{{\tt #1} \\ \begin{small} #2 \end{small}}
\parskip = .15in

\subsection{Loading and Saving Rule Sets}

\descfn{(save-rules file-name \&rest rule-set-names)}{Save rule sets to a text
file.  If {\tt rule-set-names} is {\tt nil}, then all possible are saved.}

\subsection{Manipulating Rule Sets}

\descfn{(list-all)}{List all the rule sets names, their types, and how many
rules are in them.}

\descfn{(rule-set name \&optional type)}{Returns the rule set {\tt name} if it
is of type {\tt type} (always if {\tt type}) is not given.  A rule set is of
the form {\tt (name type rule-list)} where the {\tt rule-list} is the list of
rules.}

\descfn{(add-rule-set name type)}{Create a rule set {\tt name} of the type {\tt
type}.  Marks the new rule set for editing using {\tt add}, {\tt del}, and {\tt
rpl}.}

\descfn{(remove-rule-set name)}{Remove the rule set {\tt name}.}

\descfn{(sort-rules name)}{Alphabetically sort the rules in the rule set {\tt name}.}

\descfn{(list-rules name \&optional (template '*))}{List all the rules in the
rule set {\tt name} that match the given template.}

\descfn{(add rule1 rule2 ...)}{Add rules to the last rule set listed with {\tt
list-rules} or last rule set created.}

\descfn{(del n1 n2 ...)}{Remove the numbered rules from the last rule set
listed with {\tt list-rules} or last rule set created.}

\descfn{(rpl n1 rule1 n2 rule2 ...)}{Replace the numbered rules with the new
ones in the last rule set listed with {\tt list-rules} or last rule set
created.}

\descfn{(add-rule name rule)}{Add {\tt rule} to the rule set {\tt name}.}

\descfn{(del-rule name rule)}{Remove {\tt rule} from the rule set {\tt name}.}

\descfn{(add-rule-list name rule-list)}{Add the rules in the list {\tt
rule-list} to the rule set {\tt name}.}

\descfn{(del-rule-list name rule-list)}{Remove the rules in the list {\tt
rule-list} from the rule set {\tt name}.}

\subsection{Creating Grammar Tables}

\descfn{(create-cfg-table cfg-table-name cfg-name root k)}{
Create the rule set {\tt cfg-table-name} by translating the CFG
{\tt cfg-name} into a CFG-TABLE, under the assumption that {\tt root}
is the root node.  If {\tt k} is 0 no lookahead table is created. If it
is 1, one is.}

\descfn{(create-gpsg-table gpsg-table-name gpsg-name root k)}{
Create the rule set {\tt cfg-table-name} by translating the GPSG
{\tt cfg-name} into a GPSG-TABLE, under the assumption that {\tt root}
is the root node.  If {\tt k} is 0 no lookahead table is created. If it
is 1, one is.  The root should be a symbol, not a featured category.}

\subsection{Parsing Sentences}

\verb+(p sentence &key (template '*) grammar dictionary (use-lookahead t)+\\
\verb+                 print-states file sentence-set)+\\
{\small See description in text.  If a sentence set (a rule set of type
SENTENCES) is specified, then what is returned is a list of elements,
the car of which is the sentence and the cdr the list of parses.  When
parsing a sentence set, the given {\tt sentence} is appended onto the
sentence set.  If a file name is specified, all output is to that file.}

\descfn{(retrieve-parses \&optional (template '*) \&key print-states)}{Return
the results of the last sentence parse which match the template {\tt template}.
If a GPSG grammar is being used and {\tt print-states} is set true, then
unification information is printed during retrieval.}

\descfn{(states start end \&key matching print-rules print-parses)}{ Print
debugging information on states that completed phrases from {\tt start} to {\tt
end}.}

\end{document}

