Language Technologies Institute
11-712: Self-Paced Laboratory

Algorithms for NLP:
Chart Parsing Data Spec

• Grammar Rules
  The rule defstruct is used to store grammar rules; a rule struct has two fields, lhs (a symbol denoting a non-terminal) and rhs (a list of symbols denoting non-terminals or lexical categories).

  (defstruct rule lhs rhs)

• Agenda/Chart Entries
  The entry defstruct is used to store entries on the agenda and chart.

  (defstruct (entry (:print-function print-entry))
    start end category children lexeme id)

  An entry struct has the following fields:
  1. start: the starting position in the input (integer)
  2. end: the ending position in the input (integer)
  3. category: the lexical or non-terminal category (symbol)
  4. children: the list of child node ids (symbols; non-terminals only)
  5. lexeme: the input symbol (lexical categories only)
  6. id: a unique identifier for each entry (integer)

  Note that there is a predefined print function for entries; when Lisp tries to print an entry structure, it will use this function instead of the default:

  (defun print-entry (s stream depth)
    (declare (ignore depth))
    (prin1 (list (entry-start s) 
  	       (entry-end s) 
                 (entry-category s)
  	       (or (entry-lexeme s)
                     (entry-children s)) 
                 (entry-id s))
  	 stream))

  This has the effect of printing entries as list containing start, end, category, either the lexeme or child list, and the id.
• Arcs
  The arc defstruct is used to store active arcs during parsing.

  (defstruct arc start end index lhs rhs children)

  An arc struct has the following fields:
  1. start: the starting position for the arc
  2. end: the ending position for the arc
  3. index: the offset (0-based) into the set of RHS symbols, equivalent to the position of Allen's circle mark
  4. lhs: the LHS of the original rule
  5. rhs: the RHS of the original rule
  6. children: a list of entry ids (integers)
• The Grammar and Lexicon
  The format and contents of the grammar and lexicon are fixed. You will not need to modify them for this assignment (although you may wish to experiment with them in the future). If you're interested in the details, look at the given code file.

  When you need to lookup an input symbol to determine its set of lexical categories, use the function lookup-word, which takes a single argument (an input symbol) and returns a list of symbols denoting lexical categories.

• Positions
  Positions in the chart start with 1. The end-of-sentence position is an integer whose value is one greater than the length of the input.
• The Agenda
  The agenda should be implemented as a list of entry structures. You should add new entries to the front of the agenda list or to the end of the agenda list, to implement different search methods as per Allen.
• The Active Arcs List
  The active arcs list should be implemented as a list of arc structures. You should add new arcs to the front of the list or to the end of the list, to implement different search methods as per Allen.
• The Chart
  The chart should be implemented as a list of entry structures. When entries are added to the list, they are always added at the beginning (if you don't implement this properly, you won't get the correct results!).