% -*- 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}