Language Technologies Institute
11-712: Self-Paced Laboratory

Algorithms for NLP:
Chart Parsing Function Spec

• You should create a file called chart.lisp. At the top of the file, include a statement which loads the given code (see the module instructions for the specific statement).
• Implement the following functions for the chart parser:

  bottom-up-chart(input searchmode quitmode)

  input	A quoted list of symbols to be parsed
  searchmode	Either 'bfs or 'dfs
  quitmode	Either T or NIL

  For example,

  (bottom-up-chart '(the large can) 'dfs t)

  The value returned by bottom-up-chart is the final version of the chart (list of entry structs).

Your code should implement the chart algorithm as described by Allen, with the following modifications:

1. When searchmode is dfs, then new agenda entries are added at the top of the agenda; when bfs, new agenda entries are added at the bottom of the agenda. When searchmode is dfs, then new active arcs are added at the top of the active arc list; when bfs, new active arcs are added at the bottom of the active arc list.
2. When quitmode is T, then the parser should check to see if the latest entry on the chart covers the entire input before it processes another item on the agenda. Since new items are always added at the top of the chart, this has the affect of terminating the algorithm as soon as a possible answer is found. When quitmode is NIL, then the parser should continue processing until the agenda and the input are empty.
3. Your code should keep an integer counter which is incremented each time an item is put on the agenda, put into the chart, or an active arc is created/updated. (You will need this to print the correct trace messages; see below)
4. When global variable *chart-trace* is non-NIL, your code should print a trace message for each of the operations. Each trace message is prefixed by the current entry from the agenda (or EMPTY) if the agenda is empty):
   1. Whenever a word is read from the input:
      

      EMPTY                Reading from input (THE MAN HOLDS THE WATER)

   2. Whenever a new lexical category is added to the agenda:
      

      EMPTY                Entering ART (THE from 1 to 2) [agenda bottom]

   3. Whenever a new non-terminal is added to the agenda:
      

      (5 6 N WATER 7)      Entering NP from 5 to 6 [agenda bottom]

   4. Whenever a rule is completed immediately by the agenda entry:
      

      (2 3 N MAN 2)        Completes rule NP -> (N *) from 2 to 3

   5. Whenever a new active arc is added:
      

      (1 2 ART THE 1)      Starts rule NP -> (ART * ADJ N) from 1 to 2

   6. Whenever an active arc is updated:
      

      (2 3 ADJ LARGE 2)    Continues arc NP -> (ART ADJ * N) from 1 to 2

   7. Whenever a an active arc is completed:
      

      (2 3 N MAN 2)        Completes arc NP -> (ART * N) from 1 to 2

   8. Whenever a covering entry is added to the chart, but parsing continues:
      

      (1 6 S (4 10) 12)    ** Covers the input, continuing...[37 operations]

   9. Whenever a covering entry is added to the chart, and parsing ends:
      

      (1 6 S (4 10) 12)    ** Covers the input, quitting [37 operations]

   10. Whenever the input is exhausted:
       

       (1 6 S (4 10) 12)    No input, quitting [38 operations]

   To simplify this, we've provided a trace macro, chart-trace, which you should use to print out messages during operation:

   (chart-trace format_string &rest args)

   For example:
   

   (chart-trace "~% ~10a Continues arc ~a -> ~a from ~a to ~a"
                item (arc-lhs arc) 
                (insert-index (1+ (arc-index arc)) (arc-rhs arc)) 
                (arc-start arc) end)

   Here's a full-blown example of how a fully-traced example should look.

5. When the parse is finished, and before the contents of the chart are returned, your function should create a Lisp parse tree for each node in the chart that covers the whole input. The variable *parse-value* is set to a list of these trees. When global variable *print-parse-tree* is non-NIL, your code should print the parse trees that it produced before it returns the chart, e.g.,

   > (bottom-up-chart '(the man holds the water in the can) 'dfs nil)
   
   Parse[1]:
   (S (NP (ART THE) (N MAN))
      (VP (VP (V HOLDS)
              (NP (ART THE) (N WATER)))
          (PP (P IN)
              (NP (ART THE) (N CAN)))))
   
   Parse[2]:
   (S (NP (ART THE) (N MAN))
      (VP (V HOLDS)
          (NP (NP (ART THE) (N WATER))
              (PP (P IN)
                  (NP (ART THE) (N CAN))))))
   

   (Hint: The Lisp parse trees should be structured exactly like the ones shown above, then you can use the built-in function pprint to print them.)

   Here's a full-blown example of how a fully-traced example should look.

• The following given functions will save time when coding the algorithm, since they automate certain recurring searches that need to be done against the grammar and active arc list:
  • lookup-word (input_symbol)
    Returns a set of constituent labels (e.g., NP, ART, etc.) for the input symbol, e.g.:
    

    (lookup-word 'large) --> (ADJ)

  • rules-started-by (constituent)
    Will return the list of grammar rule structs whose first RHS symbol matches the constituent, e.g.:
    

    (rules-started-by 'art) --> (#S(RULE LHS NP RHS (ART ADJ N)) #S(RULE LHS NP RHS (ART N)))

  • rules-completed-by (constituent)
    Will return the list of grammar rule structs whose first and only RHS symbol matches the constituent, e.g.:
    

    (rules-completed-by 'N) --> (#S(RULE LHS NP RHS (N)))

  • arcs-continued-by (end constituent arcs)
    Will return the subset of the active arcs currently at end which are continued by an RHS symbol matching the constituent.
  • arcs-completed-by (end constituent arcs)
    Will return the subset of the active arcs currently at end which are completed by an RHS symbol matching the constituent.