The TRAINS Parsing System

Version 4.0

A User's Manual

James F. Allen
Dept. of Computer Science
University of Rochester
Rochester, NY 14627
james@cs.rochester.edu


Abstract

This report is a user's manual for the TRAINS parsing system. The parser is based on the bottom-up parser described in Natural Language Understanding, Second Ed. (Allen, 1994, Chapters 3,4,5). It uses the same formats for the grammar and the lexical entries, and the same basic bottom-up algorithm. There are a number of extensions beyond the basic system described in the book, each of which will be discussed in this report, including

Acknowledgements

This research was supported in part by ONR/ARPA grant esearch grant no. N00014-92-J-1512 and NSF grant IRI-9623665. Thanks to Mark Core, Aaron Kaplan, and Drew Simchik for work on the parser at various stages of its development.

Table of Contents

1 The Format of Constituents and Grammatical Rules

2 Defining Grammars

3 Compiling and Using Grammars and Lexicons

4 Morphological Analysis

5 Running the Online Parser

6 Tracing and Other Control Options

7 Accessing the Chart

8 Handling Gaps

9 Debugging Grammars

10 Hierarchical Features

11 Enhanced Lexicon Input Capabilities

12 Procedural Attachment

13 Tricks and Tips

14 Obtaining the System

1 The Format of Constituents and Grammatical Rules

In all input and output interactions, constituents are represented as a list starting with the syntactic category of the constituent, followed by an arbitrary number of feature value pairs. For example, here is an NP constituent with an AGR feature 3s, and a SEM feature CONTAINER:

(NP (AGR 3s) (SEM CONTAINER))

Feature values may be LISP atoms, embedded constituents, variables, or constrained variables. A variable can be written in several different forms:

?<atomic name> - an unconstrained variable (e.g., ?A), which will match any value;
(? <atomic name>) - syntactic variant of a simple variable (e.g., ?A);
(? <atomic name> <val1> ... <valn>) - a variable constrained to be one of the indicated values (e.g., (? A 3s 3p));
?!<atomic name> - a variable that matches anything but the empty value " " (e.g., ?!A).
(? !<atomic name> <val1> ... <valn>) - a variable constrained to be anything except one of the indicated values (e.g., (? !A 3s)) will match anything but the value 3s.

A special construction allows constituents to be values, and is of the form

(% <cat> (<feat> <val>)*).

For example, here is a VP constituent with an NP constituent with AGR value 3s as the value of the SUBJ feature:

(VP (AGR 3s) (SUBJ (% NP (AGR 3s)))).

Note if you omitted the % in this example, then the value of the SUBJ feature would be interpreted simply as a list structure and not as an embedded constituent.

The basic syntax for a grammatical rule is

(<lhs constit> <rule id> <rhs constit 1> ... <rhs constit n>)

Constituents on the right hand side of a rule may be designated as head constituents by enclosing them in a list with the first element being the atom head . The treatment of head features is discussed in section 2.

For example, the following is a rule for a sentence-level constituent S:

    ((s (agr ?a))
      -1>
      (np (agr ?a))
      (head (vp (agr ?a)))
  

This rule has as its left hand side an S constituent with the AGR feature being the variable ?a, a rule identifier of -1>, and two constituents on the right hand side: an NP and a VP, both with an AGR feature that must unify with the AGR feature in the S constituent. The VP is the head constituent.

Rules may also have weights associated with them, and the parser uses a best-first search strategy to build constituents using the rules with the highest weights first. This allows the user to define context-free probabilistic grammars as described in Natural Language Understanding (Allen, 1994). Weights do not have to follow the laws of probability, however. The user may specify any weights they wish on rules in order to affect the search. The weight for a rule is indicated immediately following the rule ID. If not specified, the weight of a rule is set to a default value, which is initially set to 1.0. This can be changed by the user as described in Section 3. Here's rule -1-> again, this time specified to have a weight of .5.

    ((s (agr ?a))
      -1> .5
      (np (agr ?a))
      (head (vp (agr ?a)))
      

Rules may contain a variable as a constituent on the right hand side. This is useful for allowing subcategorization information in the feature system. For example, here is a rule that will work for any verb that takes a single constituent complement (assuming the lexicon is defined appropriately)

    ((vp)
      -vp1> 
      (head (v (subcat ?c)))
      ?c)
  

With such a rule, simple transitive verbs would have to have the SUBCAT value (% NP) in the lexicon.

2 Defining Grammars

A grammar is a list of rules, together with a prefix that indicates what input format is being used. The rules above are in what is called "cat format", where the CAT feature is not explicitly present. For example, here is a small grammar in CAT format.

  (setq *testGrammar1*
    '(cat
        ((s (agr ?a)) -1-> (np (agr ?a)) (vp (agr ?a)))
        ((np (agr ?a)) -2-> (art (agr ?a)) (n (agr ?a)))
        ((vp (agr ?a) (vform ?v)) -3-> (v (agr ?a) (vform ?v) (subcat _none)))
        ((vp (agr ?a) (vform ?v)) -4->
  		            (v (agr ?a) (vform ?v) (subcat _np)) (np))))
  

Using Head features

A head feature captures a constraint between the values of the mother constituent to its head subconstituents (see Allen, 1994). Head features can be defined for a set of rules, and are very useful for abbreviating rules with large numbers of systematically defined features. If head feature format is used in a grammar, every rule should have at least one head subconstituent on the left hand side. In this parser, head features are local to specific categories rather than being global to the grammar (say, as in GPSG). Since the overall grammar is defined incrementally from a set of smaller grammars, the head features are not global to the final grammar. Rather, they are local to each cluster of rules defined. The head features for a grammar are specified using the form

(Headfeatures (<cat1> <feat1.1> ... <feat1,m>) ...(<catn> <featn,1> ... <featn,k>)).

For example, here is the same grammar as *testGrammar1* above, but in head feature format

  (setq *testGrammar2*
       '((headfeatures (vp vform agr) (np agr))
               ((s (agr ?a)) -1-> (np (agr ?a)) (head (vp (agr ?a))))
               ((np) -2-> (art (agr ?a)) (head (n (agr ?a))))
               ((vp) -3-> (head (v (subcat _none))))
               ((vp) -4-> (head (v (subcat _np))) (np))))
   

These two grammars would generate exactly the same grammar in the internal format.

Foot Features

A foot feature moves feature values from any subconstituent to the mother (see Allen, 1994). Foot features can only be defined globally at the present time, so using them adds significant overhead to a large grammar. Unlike head features, which are a notational convenience, the behavior of foot features cannot easily be captured in the standard grammar format. When a feature F is defined as a foot feature, then whenever a rule is used, if one of the subconstituents has a value for F, then that value is passed on to the mother constituent. If two subconstituents define a value for feature F, then the values must unify. For example, foot features are needed to define the behavior of the feature WH, which indicates if a constituent contains a wh-term in any sub constituent.

(define-foot-feature <feature name>)
This defines the feature name as a foot feature globally throughout the grammar. For example, the WH feature is defined as a foot feature by (define-foot-feature 'WH).

Declaring Lexical Categories

For improved tracing and the handling of gaps, you need to declare all lexical categories. If you don't use the gap feature, declaring the lexical categories is not essential. The following categories are preset by the system:

      n      noun
      v      verb
      adj    adjective
      art    article
      p      preposition
      aux    auxiliary verb
      pro    pronoun
      qdet   question determiner
      pp-wrd words that function like pp phrases
      name   proper name
      to     the word "to"
  

Additional lexical categories are defined as follows:

(defineLexicalCategories <list of categories>)
This defines the lexical categories to be the list specified.

(addLexicalCat <category name>)
This adds the indicated lexical categories to the current list of lexical categories.

Lexical Entries

A lexicon consists of a list of word entries of form

(<word> <constit>)

where the constit is in abbreviated format as described above. Here's a sample lexicon

  (setq *Lexicon1*
    '((dog (n (agr 3s) (root dog)))
      (dogs (n (agr 3p) (root dog)))
      (pizza (n (agr 3s) (root pizza)))
      (saw (v (agr ?a1) (vform past) (subcat _np) (root see)))
      (barks (v (agr 3s) (vform pres) (subcat _none) (root bark)))
      (the (art (agr 3s) (root the)))))
  

3 Compiling and Using Grammars and Lexicons

The system allows the user to maintain sveral different grammars and lexicons simultaneously and switch between them efficiently with each call to the parser. Before a grammar and lexicon can be used, they must be compiled into internal format. Then when the parser is called, you specify the pre-compiled grammar/lexicon combination you want to use. OR you can define a default grammar/lexicon and have the parser default to this whenever a grammar/lexicon is not specified in the call to the parser. These functions all take an optional grammar/lexicon structure (GL-structure), and return a new grammar/lexicon structure that contains the additional information supplied. If no grammar/lexicon structure is provided in a call, these funcitons create a new grammar/lexicon structure.

(compile-grammar <grammar spec> <optional GL-structure>)

Compiles the specified grammar rules and adds them to the GL-structure, or creates a new GL-structure if not is specified.

(compile-lexicon <lexicon spec> <optional GL-structure>)

Compiles the specified lexicon and adds the entries to the GL-structure, or creates a new GL-structure if not is specified.

There are two functions for accessing the active grammar:

(get-grammar <optional GL-structure>)
This returns a list of the rules in the specified grammar, or the default grammar if none is specified

(show-grammar <GL-structure> <optional rule id> ... <optional-rule-id>)
This prints the rules with the indicated rule IDs in the indicated grammar. If the first argument is not a legal GL-structure, it is assumed to be a rule identifier and the default grammar is used. For example,
(show-grammar '-s1-> '-vp->)
would print out all rules in the default grammar with the ID -s1-> or -vp1>. If no IDs are specified, the entire grammar is printed out.

For the lexicon, a similar pair of functions is provided.

There are several functions for accessing lexical entries

(worddef <word> <optional GL-structure>)
This returns all the lexical entries for the indicated word in the indicated grammar (or the default if none is specified), e.g., (worddef 'to) returns all the entries for TO.

(get-lexicon <optional GL-structure>)
This returns the complete active lexicon
. This is a hash table. The entires for any individual word can then be obtained using GETHASH, e.g., (gethash 'go (get-lexicon)).

(defined-words <optional GL-structure>)
This returns a list of all the words that are defined in the lexicon.

Compatabilty Functions With Earlier Versions

The following functions provide compatabilty with old versions of the parser. They allow you to define the default grammar and lexicon directly.

(make-grammar <grammar spec>)
This defines the active grammar to the specified grammar.

(augment-grammar <grammar spec>)
This adds the rules in the specified grammar to the active grammar.

(make-lexicon <list of lexical entries>)
This defines the active lexicon to be the specified lexical entries.

(augment-lexicon <list of lexical entries>)
This adds the lexical entries to the active lexicon

Setting the Default Rule Probability

If you want to change the default rule probability from 1.0, you may do so using the following function. Note that this default is used when the rules are added to the active grammar. So different defaults could be used for different sections of the grammar if they are added separately.

(Set-Default-Rule-Probability <number>)
Sets the default rule probability to the indicated number. While meaningful probabilities must fall between 0 and 1, the parser actually accepts any numbers the user wishes to define as it does not depend on the laws of probability in any of its calculations.

4. Morphological Analysis

A simple but useful facility is provided that takes string input and expands contractions and punctuation:

(Tokenize <sentence as a string>)
This expands contractions and converts punctuation in a string into a list of atoms for the parser. For example, the string "I don't know Avon's size." returns the list (I DO NOT KNOW AVON ^S SIZE PUNC-PERIOD). Table 1 gives example of the expansions that Tokenize handles.

Punctuation is mapped in special symbols: PUNC-PERIOD ("."), PUNC-COLON (":"), PUNC-SEMICOLON (";"), PUNC-COMMA (","), PUNC-QUESTION-MARK ("?"), PUNC-EXCLAMATION-MARK ("!").

Abbreviation Example Result

  Regular n't forms   don't     DO N^T
  Regular 'll forms   you'll    YOU ^LL
  Regular 'd forms    I'd       I ^D
  Regular 're forms   you're    YOU ^RE
  Regular 've forms   we've     WE ^VE
  Possessives 's      George's  GEORGE  ^S
  Possessives '       engines'  ENGINE ^
  Significant blank   I_want I  WANT
  o'clock             o'clock   O^ CLOCK
  Contraction         I'm       I ^M
  Contraction         Let's     LET ^S
  

Table 1: Summary of Expansions performed by the function Tokenize

5 Running the Parser

The parser runs with respect to a selected grammar and lexicon that has been built using the functions in the section on Compiling and Using Grammars and Lexicons . Once a grammar and lexicon are compiled, they can be selected using the following function.
(select-grammar <GL-structure>)

Makes the specified GL-structure the default grammar and lexicon for future calls to the parser.

Getting Started Quickly

The easiest way to call the parse is to use the function P , which takes a tring input, tokenizes it expanding the morphological forms, calls the parser and returns the best answers. For example, assuming the grammars and lexicon from chapter 4, we would get the follwoing behavior:

  PARSER(44): (p "a fish saw the man")
THE BEST PARSES FOUND S181:(S (1 NP159) (INV -) (AGR 3S) (2 VP178)) from 0 to 5 from rule -1>, Prob = 1.0 NP159:(NP (1 ART152) (AGR 3S) (2 N156)) from 0 to 2 from rule -2>, Prob = 1.0 ART152:(ART (VAR V151) (LF A) (LEX A) (INPUT A) (AGR 3S) (ROOT A1)) from 0 to 1, Prob = 1.0 N156:(N (VAR V155) (LF FISH) (LEX FISH) (INPUT FISH) (ROOT FISH1) (AGR 3S) (IRREG-PL +)) from 1 to 2, Prob = 1.0 VP178:(VP (1 V161) (VFORM PAST) (AGR 3S) (2 NP177)) from 2 to 5 from rule -5>, Prob = 1.0 V161:(V (VAR V160) (LF SAW) (LEX SAW) (INPUT SAW) (ROOT SEE1) (VFORM PAST) (SUBCAT _NP) (AGR 3S)) from 2 to 3, Prob = 1.0 NP177:(NP (1 ART170) (AGR 3S) (2 N174)) from 3 to 5 from rule -2>, Prob = 1.0 ART170:(ART (VAR V169) (LF THE) (LEX THE) (INPUT THE) (ROOT THE1) (AGR 3S)) from 3 to 4, Prob = 1.0 N174:(N (VAR V173) (LF MAN) (LEX MAN) (INPUT MAN) (ROOT MAN1) (AGR 3S)) from 4 to 5, Prob = 1.0 PARSER(45): (p "a fish saw the man" '(lex)) THE BEST PARSES FOUND S181: (S), 0-5 (-1>), P=1.0 NP159: (NP), 0-2 (-2>), P=1.0 ART152: (ART (LEX A)), 0-1 (NIL), P=1.0 N156: (N (LEX FISH)), 1-2 (NIL), P=1.0 VP178: (VP), 2-5 (-5>), P=1.0 V161: (V (LEX SAW)), 2-3 (NIL), P=1.0 NP177: (NP), 3-5 (-2>), P=1.0 ART170: (ART (LEX THE)), 3-4 (NIL), P=1.0 N174: (N (LEX MAN)), 4-5 (NIL), P=1.0

Running the Parser Incrementally

The online parser is called using two functions, each taking a list of atoms (i.e., the words) as its argument, e.g.,

(start-BU-parse <list of words>)
This initiates a new parse starting with the indicated words (e.g.,
(start-BU-parser '(the dog)))

(continue-BU-parse <list of words>)
This continues the parse with the indicated words(e.g., calling
(continue-BU-parse'(ate the pizza))
after
(start-BU-parser '(the dog)))
will produce the chart for the sentence "the dog ate the pizza".

"Best-First" Parsing

While the parser operates in a best-first fashion, it has no built-in stopping criteria to determine when a good interpretation has been found. You can control this in one of two ways. You can define your own stopping criteria using procedural attachment. Or you can process by setting a threshold value on the rating of constituents that should be added to the chart. If no good interpretation is found at one setting, you can then lower the threshold and have the parser continue using the continue-BU-parse function. The threshold is initially 0, meaning all interpretations will be explored. You may chage this value using the function

(setThreshold <number>)
Parser will only add constituents to the chart that exceed the specified threshold (which should be between 0 and 1). Lattice-based Parsing

The parser also supports a generalized input format that allows it to parse word lattices and other structures. When calling the parser, you may use the following format in place of a single atom presenting a word:

(<word atom> <optional modifiers>)

where the optional modifiers are indicated in keyword format

:start <start position>
- indicates the starting position of the word. Default is the next position in the input
:end <end position>
- indicates the ending position of the word. Defaults to the start position plus one
:prob <number>
- indicates the "probabilistic" weight of the word. Defaults to 1.0
:filter <constit spec>
- indicates the syntactic category and necessary features of the word entry. Only those lexicon entries that unify with this filter are used. If not specified, all entries in the lexicon are used. If the constit spec is an atom, it specifies the syntactic category required. If the constit-spec is a list, it must be of the form (<cat> (<feat> <val>)*), as in (NAME (SEM CITY)).

For example, given the input item (ate :start 3 :prob .5), the parser would look up all lexical entries for ATE and create entries from position 3 to 4 for each with probability .5. Given the input item (run :start 4 :filter NOUN), the parser would only use lexical entries for RUN that are nouns. Given (Toledo :start 5 :end 8 :filter (NAME (SEM CITY))), the parser would only use lexical entries for TOLEDO that are names with SEM feature CITY, and each constituent spans from position 5 to 8.

Backing Up

Backing up the parser is simple.

(backupto <position>)
This causes the parser to the position indicated, where 0 is the position before any words, 1 is between the first and second words, etc. Or if lattice-based parsing is being used, the position is determined by the lattice positions supplied.

Setting the Maximum Chart Size

The function ContinueUtterance can be called as long as you wish, until the chart exceeds its maximum size. The max chart size can be found by calling (GetMaxChartSize), and the default size is 2000 constituents. If you are not using the lattice-based parsing, you can reduce this to the maximum number of words you ever expect to see in a sentence, although the overhead is minimal. You may change this by calling SetMaxChartSize, e.g., (SetMaxChartSize 5000).

6 Tracing and Other Control Options

Global Tracing

There are two global levels of tracing provided:

(traceon)
This causes a trace message as each constituent is added to the chart

(verboseon)
This causes a trace message of each arc extension as well.

(verboseoff)
This stops the extended tracing

(traceoff)
This disables all tracing

Specific Tracing

You can trace all activity of a single rule in the grammar, which causes a message to be printed whenever it is extended and when it is completed and adds a constituent to the chart.

(trace-rule <rule-id> ... <opt-rule-id>)
This traces all rules that have the indicated identifier (e.g., (trace-rule '-1->) causes a trace message whenever rule -1-> is extended or is completed). You may trace as many rules simultaneously as you want. To disable individual tracing, you have to use (traceoff).

The default trace message prints all features in every constituent. You can change this by specifying which features you would like to see.

(set-trace-features <list of feature names>)
This will cause all trace messages to only print the indicated features. If the argument is T, then all features are printed. If it is NIL, then no features are printed.

Setting a Break Point

You can set a single break point, where the parser will stop when it adds a constituent that matches an indicated pattern to the chart.

(break-on <constit>)
This sets the parser to stop when a constituent is found that unifies with the constituent specified. For example,
(break-on (% S (STYPE (? x DECL YNQ)))
would cause the parse to stop when it finds an S constituent with the STYPE feature being DECL or YNQ. The parser retains all its state, so you can continue a parse after stopping it simply by calling (Continue-BU-parse nil). To turn off the break point, simply call break-on with nil as an argument.

7 Accessing the Chart

There are several ways to view the chart built from the last parse:

(show-chart <opt-feat-list> <opt-start-index> <opt-end-index>)
This prints out the complete chart, showing all chart entries as they were built bottom-up. If the <optional feature list> is specified, only the features mentioned are printed. If it is the value T, all features are printed. If the <optional start index> and <optional end index> are specified, then only the constituents between these positions are printed. If the starting position is specified and the end position omitted, all constituents after the starting position are printed. Consider the examples:
(show-chart '(LEX LF)) - display entire chart showing only LEX and LF features
(show-chart '(LEX LF) 3) - display entire chart from position 3 to end showing only LEX and LF features
(show-chart t 3 6) - show chart between positions 3 and 6, showing all features.

(show-best <opt-feat-list> <opt-start-index> <opt-end-index>)
This prints out only the chart entries that span the complete input between the specified indices, or the entire sentence if the indices are not specified. If no constituent spans the entire utterance, this prints the smallest sequence of constituents that cover the entire sentence. See discussion of show-chart above for interpretation of defaults for parameters.

(show-answers <opt-feature-list> <opt-start-index> <opt-end-index>)
This prints out the complete parse tree rooted at each of the constituents found in show-best. This function binds all the variables in the subconstituents as it prints giving a better view of the overall parse tree than the full chart where the constituents are shown as they were defined bottom-up.

(show-constit <constituent-name> <opt-feat-list>)
This prints out the complete parse tree rooted at the indicated constituent. If the optional feature list is specified, then only those features are printed.

Accessing the Chart from Programs

To access the chart from within a program, a similar set of functions are provided that return values rather than printing them. These use the internal data structures CONSTIT and ENTRY used by the parser. Consituents are defined by the structure
  	(defstruct constit
  		  cat feats head)
  	
which means the following functions are defined:
constit-cat - return the category of the constituent
constit-feats - returns the list of feature-value pairs defined for the constituent
constit-head - will be T is this was a head constituent in the parse.
Entries on the chart consist of a constituent plus additional information about where it is positioned in the input and what rule produced the constituent:
  	(defstruct entry
  	  constit start end rhs name rule-id prob)
  	
which means the following functions are defined:
entry-constit - return the constituent for the entry
entry-start - the starting position
entry-end - the ending position
entry-rhs - a list of the consitutents forming the RHS of the rule that produced the constituent
entry-name - the internal name of the entry
entry-rule-id - the id of the rule that produced the constituent
entry-prob - the probability score assigned for this constituent.

With these defined, you can access the chart using the following functions:

(get-best <opt-start-index> <opt-end-index>)
Returns a list of the entries for the constituents that span the entire input.

(get-answers <opt-start-index> <opt-end-index>)
Like
get-best
except that it returns the best trees. Trees are represented as lists of the form (<root-entry> <subtree1> ... <subtree -n>).

(get-entry entry-name)
Returns the tree rooted at the entry named.

(get-constit entry-name)
Returns the constituent for the entry rooted at the entry named, same as (entry-constit (get-entry <name>)).

(get-cat-constits-between category-name <opt-start-index> <opt-end-index>)
Returns all entries on the chart of the indicated category between the specified indices.

The following example shows these functions in operation using *grammar5-7* and *lexicon5-6* defined in the sample grammar files.
  PARSER(17): (start-bu-parse '(a happy man))
  NIL
  PARSER(27): (get-best)
  (#S(ENTRY 
    :CONSTIT #S(CONSTIT :CAT NP 
                        :FEATS ((1 DET34) (WH -) (AGR 3S) (2 CNP44)) 
                        :HEAD NIL) 
    :START 0 
    :END 3
    :RULE-ID -5-7-2>
    :PROB 1.0))
  PARSER(28): (get-answers)
  ((#S(ENTRY 
     :CONSTIT #S(CONSTIT :CAT NP 
                         :FEATS ((1 DET34) (WH -) (AGR 3S) (2 CNP44)) 
  		       :HEAD NIL)
       :START 0 
       :END 5 
       :NAME NP45 
       :RULE-ID -5-7-2>  
       :PROB 1.0)
     (#S(ENTRY 
         :CONSTIT #S(CONSTIT :CAT DET :FEATS (# #) :HEAD NIL) 
         :START 0 
         :END 1 
         :NAME DET34
         :RULE-ID -5-7-5> 
         :PROB 1.0))
       (#S(ENTRY :CONSTIT #S(CONSTIT :CAT ART :FEATS # :HEAD NIL) 
           :START 0 
           :END 1  
           :NAME ART31 
           :RULE-ID NIL 
           :PROB 1.0)))
     (#S(ENTRY :CONSTIT #S(CONSTIT :CAT CNP :FEATS (# # #) :HEAD NIL) 
         :START 1
         :END 3
         :NAME CNP44 
         :RULE-ID -5-7-4> 
         :PROB 1.0)
       (#S(ENTRY :CONSTIT #S(CONSTIT :CAT ADJ :FEATS # :HEAD NIL)  
           :START 1 
           :END 2 
  	 :NAME ADJ36 
           :RULE-ID NIL 
           :PROB 1.0))
       (#S(ENTRY :CONSTIT #S(CONSTIT :CAT N :FEATS # :HEAD NIL) 
           :START 2 
           :END 3 
  	 :NAME N40 
           :RULE-ID NIL 
           :PROB 1.0)))))
  
  PARSER(29): (get-entry 'np45)
    (#S(ENTRY 
        :CONSTIT #S(CONSTIT :CAT NP 
                            :FEATS ((1 DET34) (WH -) (AGR 3S) (2 CNP44)) 
                            :HEAD NIL) 
        :START 0    
        :END 3 
        :NAME NP45 
        :RULE-ID -5-7-2> 
        :PROB 1.0)
      (#S(ENTRY 
          :CONSTIT #S(CONSTIT :CAT DET :FEATS ((AGR 3S) (1 ART31)) :HEAD NIL) 
          :START 0 
          :END 1
          :NAME DET34 
          :RULE-ID -5-7-5> 
          :PROB 1.0)
        (#S(ENTRY 
            :CONSTIT #S(CONSTIT :CAT ART :FEATS (# # # # # #) :HEAD NIL) 
            :START 0 
            :END 1 
            :NAME ART31 
            :RULE-ID NIL 
            :PROB 1.0)))
      (#S(ENTRY 
          :CONSTIT #S(CONSTIT :CAT CNP :FEATS ((1 ADJ36) (AGR 3S) (2 N40)) :HEAD NIL) 
          :START 1 
          :END 3 
          :NAME CNP44 
          :RULE-ID -5-7-4> 
          :PROB 1.0)
        (#S(ENTRY 
            :CONSTIT #S(CONSTIT :CAT ADJ :FEATS (# # # # # #) :HEAD NIL) 
            :START 1 
            :END 2 
            :NAME ADJ36 
            :RULE-ID NIL 
            :PROB 1.0))
        (#S(ENTRY 
            :CONSTIT #S(CONSTIT :CAT N :FEATS (# # # # # #) :HEAD NIL) 
            :START 2 
            :END 3 
  	  :NAME N40
            :RULE-ID NIL 
            :PROB 1.0))))
  									
  PARSER(30): (get-constit 'np45)
    #S(CONSTIT 
        :CAT NP 
        :FEATS ((1 DET34) (WH -) (AGR 3S) (2 CNP44)) 
        :HEAD NIL)
  									
  PARSER(31): (get-cat-constits-between 'np 0 5)
    (#S(ENTRY 
         :CONSTIT #S(CONSTIT :CAT NP 
                             :FEATS ((1 DET34) (WH -) (AGR 3S) (2 CNP44)) 
                             :HEAD NIL)
         :START 0 
         :END 3 
         :NAME NP45
         :RULE-ID -5-7-2> 
         :PROB 1.0))
  

8 Handling Gaps

The system supports a basic facility for automatically propagating GAP features and inserting gaps at appropriate locations during the parse. There are functions to enable and disable gap processing. Note that gap processing must be enabled before a grammar is loaded so that the GAP feature is inserted in the rules.

(enableGaps)
This enables gap processing.

(disableGaps)
This disables gap processing.

When gap processing is enabled, the GAP feature is added to rules when they are defined, as described in Natural Language Understanding, 2nd ed . Basically, gaps propagate from mother constituent to their head constituent when they are non-lexical, and to the other subconstituents when the head constituent is a lexical constituent.

Since this is a bottom-up parser, some effort has to be made to restrict the arbitrary bottom-up insertion of gaps. To help in this, the user must declare what constituents can participate in gaps. For each constituent type that you wish to participate as gaps, you must call the following function:

(declare-gap-cat <category name> <list of features>)
This declares that the category will be used in GAPs, and the indicate list of features are all the features that will be relevant for unification with these gaps. This defaults just to NP constituents with features AGR, CASE and SEM.

(reset-gap-cats)
Removes all previous declarations concerning categories that can participate in gaps.

Rules that introduce gaps specify the constituent needed using an embedded constituent as the value of the GAP feature. For example, here is a rule for WH questions, which consist of an NP with the WH feature Q, followed by an inverted S with the GAP feature value (% np (agr ?a)). Note that the AGR feature of the gap must agree with the AGR feature of the WH NP.

    ((s)
      -5-8-3>
      (np (wh q) (gap -) (agr ?a))
      (head (s (inv +) (gap (% np (agr  ?a))))))
  

9 Debugging Grammars

One nice feature of bottom up algorithms is that they allow for some effective debugging strategies. If you find that a sequence of words doesn't parse how you think it should, try each of the constituents one at a time and see what the parser produces. If you don't get the right analysis, then try additional subparts of the sentence until you find the answer. For example, say you try

(start-bu-parse '(the angry man ate the pizza))

and it doesn't produce a complete interpretation. You might then try

(start-bu-parse '(the angry man))

and see if this produces an appropriate NP analysis. Say it does. Then try

(start-bu-parse '(ate the pizza))

ands see if this produces the appropriate VP analysis. If it doesn't, then there's probably a problem with your VP -> V NP rule, or your lexical entry for "ate". If it does produce the right interpretation, then the problem must be with your S -> NP VP rule (e.g., maybe the rule is missing, or maybe a feature equation is wrong, etc.).

You can also inspect the chart after each word is entered by simply calling the parser incrementally one word at a time and then using the standard chart access functions.

10 Hierarchical Features

The parser supports hierarchical features, where the values are defined in a hierarchy, and two values unify if one is a specialization of the other. Features that use hierarchical values must be declared.

(declare-hierarchical-features <list of features>).
This declares the indicated features as having hierarchical values. For instance,
declare-hierarchical-features '(SEM AGR))
would declare that only SEM and AGR features take hierarchical values.

The unifier is generalized for hierarchical features so that two values match if one is a specialization of the other according to a pre-defined type hierarchy. This hierarchy is a tree that is declared in a simple list format. Before you can define an actual hierarchy, you must initialize the hierarchy structure:

(init-type-hierarchy)
This initializes the type hierarchy, clearing it if it was previously defined.

(compile-hierarchy <tree in lisp form>)
This extends the existing type hierarchy (or empty hierarchy) with the hierarchical relationships specified as the argument.
For example, the call
  (compile-hierarchy
    '(PHYS-OBJ
      (FIXED-OBJ 
        (CITY) 
        (LAKE)
        (COUNTRY)
        (RIVER))
      (MOVABLE-OBJ
        (COMMODITY
          (LIQUID-COMMODITY)
          (SOLID-COMMODITY)
        (CONTAINER))
    ))
    
would define the hierarchy as indicated by the list structure.

Note that in matching hierarchical features, the matching process is not symmetric between the constituent being sought for a rule, and the constituent being matched against in the chart. If a rule needs a constituent with a SEM feature of FIXED-OBJ, then it can unify with an existing constituent with a SEM feature that is a specialization of FIXED-OBJ, such as CITY. But if a rule needs a constituent with a SEM feature of CITY, it will not unify with an existing constituent with SEM FIXED-OBJ, because not all FIXED-OBJs are necessarily CITYs. This is exactly parallel to the use of type hierarchies in knowledge representation systems, where the constituent being sought for the rule is the goal, and the chart is the knowledge base. Given the hierarchy above, Table 2 shows some results of unifying various values. Note that in the last two examples, a new variable is created as the substitution as it draws information from both the value needed and the value in the chart.

  
  value needed for rule   value in chart       result 
     FIXED-OBJ                 CITY               success, since a CITY is a FIXED-OBJ  
     CITY                      FIXED-OBJ fail,    since a FIXED-OBJ is not necessarily a CITY
     (? d FIXED-OBJ)           CITY               success, ?d bound to CITY 
     (? d FIXED-OBJ)          (? e CITY)          success, ?d bound to (? e  CITY)
     (? d CITY)               (? e FIXED-OBJ)     fail 
     (? d CITY COMMODITY)     CONTAINER           success, ?d bound to (? f  COMMODITY) 
     (? d CITY COMMODITY)     (? e CITY CONTAINER) success, ?d and ?e bound to (? f CITY COMMODITY) 
  

Table 2: Examples of feature unification with hierarchical values

11 Enhanced Lexicon Input Capabilities

The parser provides a facility that allows lexicons to be specified in hierarchies with inheritance of features, and which can automatically generate lexical variants (such as plural forms of nouns and the regular verb forms). It also inserts default values for the features LEX, LF and VAR, and other features related to morphological variants of verbs, namely AGR, and VFORM. A function expand is provided that takes a hierarchical specification and generates the standard input format for each entry.

Defining a Hierarchical Lexicon

A hierarchical lexicon is a tree of partial lexical entries, where each leaf node inherits feature values from its ancestor nodes. When multiple values for a feature are defined in the ancestors, the value declared closest to the leaf node (or at the leaf node) is used. The tree is specified as a list structure consisting of nodes and leaf nodes. A node is of the form

(:node <list of feature specs> <list of subnodes>)

and a leaf node is specified as

(:leaf <lexical item> <list of feature specs>).

The following default values are added for features if they are not specified:

LEX - set to the word
LF - set to the base form of the word
VAR - set to a new variable

Additional entries are created based on the MORPH feature as follows:

-S-3p - create a plural form by adding an "s", set AGR to 3p
-vb - create the different verb forms using regular morphology, i.e.,
add "s" for AGR 3s
add "ing" for VFORM ING
add "ed" for VFORM PAST and PASTPART

To invoke the enhanced lexical entry facility, use the following function:

(expand <category> <node>)
This creates a list of lexical entries of the indicated category as defined by the tree rooted at the specified node. This includes generating morphological variants as defined by the MORPH feature. The entries can be added to the lexicon by mapping make-lex over the result.

For example, here is a small tree defining a few lexical entries.

  (expand
    '(:node
       ((AGR 3s) (MORPH -S-3P) (ARGSEM PHYS-OBJ))   ;; the feature values
        ((:node                                     ;; first subnode
          ((SEM WEIGHT))
          ((:leaf ton)
           (:leaf pound)
        ))
       (:leaf gallon (SEM VOLUME) (ARGSEM LIQUID))    ;;  second subnode
  )))
  

This returns the following lexical entries

  ((ton (LEX ton) (LF ton) (VAR V11) (AGR 3s) (MORPH -S-3p) (ARGSEM PHYS-OBJ) (SEM WEIGHT))
   (tons (LEX tons) (LF ton) (VAR V12) (AGR 3p) (MORPH -S-3p) (ARGSEM PHYS-OBJ) (SEM WEIGHT))
   (pound (LEX pound) (LF pound) (VAR V13) (AGR 3s) (MORPH -S-3p) (ARGSEM PHYS-OBJ) (SEM WEIGHT))
   (pounds (LEX pounds) (LF pound) (VAR V14) (AGR 3p) (MORPH -S-3p) (ARGSEM PHYS-OBJ) (SEM WEIGHT))
   (gallon (LEX gallon) (LF gallon) (VAR 15) (AGR 3s) (MORPH -S-3p) (ARGSEM LIQUID) (SEM VOLUME))
   (gallons (LEX gallons) (LF gallon) (VAR 16) (AGR 3p) (MORPH -S-3p) (ARGSEM LIQUID) (SEM VOLUME)))
       

Morphological Variants

A very limited morphological expansion capabilities simple variants as shown in table 3, where C is any consonant and V any vowel. Note that these are not hard and fast rules. The automatic derivations are a matter of convenience only. Words that do not follow the general rules must be marked as exceptions.

  
  Root                   Suffix           Action                   Example 
  ends in "Cy"           "s"              replace "y" with "ie"    cities 
ends in "Cy" "ed" replace "y" with "i" carried
ends in "e" begins with "e" drop final "e" cared
ends in "h", "s" or "x" "s" insert "e" finishes
ends in "Vb","Vg" begins with "i" or "Vp" or "e" double final letter bagged

Table 3: Simple morphological variants

Morphological derivations are triggered by the MORPH features. So one way to deal with exceptions is to omit the relevant MORPH feature and define the entries by hand. For example, the entry for the word plenty , which has no plural form, would not have the MORPH feature -S-3P and thus the variant "plenties" would not be constructed. Similarly, irregular verbs could be defined by not adding the -vb MORPH feature and defining each entry by hand. There are enough irregular verb forms, however, that this would be quite cumbersome, so an additional mechanism is provided. A table of verb exceptions is defined that is checked for any entry with the MORPH feature -VB. This table may list any irregular forms of the verb. The format of an entry in this table is

  (<root form> <vb-feature>1 <form>1 ... <vb-feature>n <form>n
  
).

For example, the entry

  (bring :past brought)
  

indicates that bring has an irregular past form "brought", but the 3s form (brings) and the ing form (bringing) are formed regularly. Unless explicitly indicated, the pastpart form is always taken to be identical to the past form, so the pastpart form here is "brought". An example where the past and pastpart differ is "come"

  (come :past came :pastpart come)
  

To define exceptions, you call the function

(init-verb-exception-table <list of entries>)
This function defines the set of verbs which have at least one form that is not derivable by the standard methods, e.g.,
  (init-verb-exception-table
    '((come :past came :pastpart come)
      (bring :past brought)))
   
would define entries for "come" and "bring".

12 Procedural Attachment

This parser also allows you to attach arbitrary LISP procedures to the parser. You declare constituent patterns using the ANNOUNCE function, and whenever a constituent is about to be added that matches the pattern, your function is called first. You may then modify the constituent and return it back to the parser. The constituent patterns use the same format as in specifying grammars. Here is an example function that traps all complete NPs, prints them out, and adds a new binary feature, +SEEN.

  (announce '(np (gap -)) #'testfn)
  (defun testfn (entry)
     (Format t "~% Found the NP: ~s~%" entry)
     (setFvalue entry 'SEEN '+)
     ;;  must return the entry if it is to be added to the chart
     entry)

Note that if you subsequently edit the definition of TEST, you may need to clear the old announcements and make a new one. The function INIT-ATTACHMENTS removes all previous announced patterns, e.g.,

    (init-attachments)
    (announce '(np (gap -)) #'testfn)
  

In general, you will have to dig into the code if you want to modify parts of a constituent. But here are a few of the more common functions.

(GetFvalue <entry> <featurename>)
This returns a feature value, e.g., (getFvalue entry 'SEEN) would return the value of the feature SEEN.

(SetFvalue <entry> <featurename> <value>)
This sets a feature value, e.g., (setFvalue entry 'SEEN '+) sets the feature value SEEN to +

(SetProbValue <entry> <number>)
This sets the probability of the entry, e.g., (setProbValue entry .5) sets the probability to .5.

Note that if you reduce the probability of a constituent so that it is not now the highest ranked constituent on the agenda, it will be placed back onto the agenda to be added to the chart later. This means you will see the same constituent again if it returns to the top of the stack.

If you want to stop the parser from within an attached function, call the function:

(suspendParse)
This will cause the parser to stop after it processes the current entry. In other words, if your function returns the entry, it is added to the chart or back to the agenda as normal, and then the parser stops. The parser can be resumed simply by calling continue-BU-parse with nil as an argument since the agenda is not cleared.

13. Tricks and Tips

This section contains various bits of information that may be useful for certain applications.

Multiple Matching of Features

The parser allows you to specify the same feature multiples times in a rule, and such a rule will succeed only if all the values unify. This can be useful in some cases. For instance, if you want a feature F to match some part of a complex value, but also want a variable that records the entire value, you can do this by matching a feature multiple times. For instance, say we needed a rule for a verb class that only allowed singular NP complements:

         ((vp (subj ?np)) -4-> 
  	   (v (subcat (% NP (AGR 3s)))
                (subcat ?np))
             (np (AGR 3s)))
   
The first SUBCAT match would make sure that the verb subcategorized for a singular NP. The second would bind the variable ?np to the full specification of the SUBCAT feature in the verb (and allow us to set the SUBJ feature in the VP).

14. Obtaining the System

The parser code is available via anonymous ftp from ftp.cs.rochester.edu in the directory pub/u/james/TRAINSparser4.0.tar.gz.

15. References

Allen, J.F. Natural Language Understanding Second Edition, Benjamin-Cummings Pub Co., 1994.