James F. Allen
Dept. of Computer Science
University of Rochester
Rochester, NY 14627
james@cs.rochester.edu
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
1 The Format of Constituents and Grammatical Rules
3 Compiling and Using Grammars and Lexicons
6 Tracing and Other Control Options
11 Enhanced Lexicon Input Capabilities
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.
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.
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:
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)))))
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.
Compiles the specified grammar rules and adds them to the GL-structure, or creates a new GL-structure if not is specified.
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:
For the lexicon, a similar pair of functions is provided.
There are several functions for accessing lexical entries
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.
A simple but useful facility is provided that takes string input and expands contractions
and punctuation:
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
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.,
"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
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:
where the optional modifiers are indicated in keyword format
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.
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).
Global Tracing
There are two global levels of tracing provided:
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.
The default trace message prints all features in every constituent. You can change
this by specifying which features you would like to see.
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.
There are several ways to view the chart built from the last parse:
(defstruct constit cat feats head)which means the following functions are defined:
(defstruct entry constit start end rhs name rule-id prob)which means the following functions are defined:
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))
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.
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:
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))))))
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.
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.
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:
(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
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:
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 '((come :past came :pastpart come) (bring :past brought)))would define entries for "come" and "bring".
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.
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:
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).
The parser code is available via anonymous ftp from
ftp.cs.rochester.edu in the directory
pub/u/james/TRAINSparser4.0.tar.gz.
Allen, J.F. Natural Language Understanding Second Edition, Benjamin-Cummings Pub Co., 1994.