Assignment 1 LISP problem solution

Here is the modified version of chapter5.lisp that handles topicalization. Note that this is not a "model writeup", you would have to provide better testing data and conclusions.

Topicalization

Here is the grammar I made for topicalization

  (setq *grammar-topicalization*
    '((headfeatures
       (s vform)    
       )
      ;; S -> NP S[-inv,/NP]
      ((S)
       -T1>
       (NP  (wh -) (gap -) (agr ?a))
       (head (S  (wh -) (inv -) (vform (? v pres past)) 
  	      (gap (% np (wh -) (agr ?a))))))
      ;; S -> PP S[-inv, /PP]
      ((S)
       -T2>
       (PP  (wh -) (gap -) (pform ?pf) (ptype ?pt))
       (head (S (wh -) (inv -) (vform (? v pres past)) 
  	      (gap (% pp (wh -) (pform ?pf) (ptype ?pt))))))
      ))    
  
There are 2 rules, one for topicalized NP's and another fro topicalized PP's. The grammar does not cover topicalized ADJP's and VP's since the parser cannot handle other gaps except for NP and PP gaps.

Note the combination of features set on the topicalized phrase

   (wh -) (gap -)
  
It ensures that we do not topicalize noun phrases and that we do not allow to topicalize out of already topicalized sentence, so that the following weird constructs are excluded
   What you see NP/NP         - analyzed as  NP[wh] S[/NP]
   Mary to John gave a book   - analyzed as  NP (S/NP: PP/NP S[/PP])
  
In addition,
  (wh -) (inv -) (vform (? v pres past))
  
on S ensures that we follow wh-island constraint and do not topicalize sentences with wh word in them, and also inverted and non-finite sentences.

The parser already enforces the A over A complex NP constraints, and since we don't have a grammar for coordinate structure, we don't have to deal with it. However, since the parser supports propagation of head features, the double gap propagation would be accounted for in the coordinate structure by declaring both of the coordinated phrases heads. Since heads will have to share head features with their mother, the both phrases will have to have the same gap or otherwise the extraction won't be possible. Here is an example, with irrelevant features deleted

  USER(14): (bu-parse '(the dog jack saw he want +s))
  USER(15): (show-answers)
   THE BEST PARSES FOUND
  S739: S ((VFORM PRES) (1 NP710) (2 S737))  from 0 to 7 from rule -T1 
    NP710: NP ((GAP -) (WH -) (AGR 3S) (1 DET687) (2 CNP709))                       
      DET687: DET ((GAP -) (AGR 3S) (1 ART678))                                     The
        ART678: ART ((LEX THE) (AGR (? A325 3P 3S))) 
      CNP709: CNP ((AGR 3S) (1 CNP688) (2 REL707))  
        CNP688: CNP ((GAP -) (AGR 3S) (1 N679))                                     dog
          N679: N ((LEX DOG) (AGR 3S))  
        REL707: REL ((GAP -) (1 S706))                                              Jack 
          S706: S ((GAP  NP ((AGR ?AGR693)) ) (WH -) (INV -) 
  	         (VFORM PAST) (AGR 3S) (1 NP690) (2 VP703))  
            NP690: NP ((GAP -) (AGR 3S) (1 NAME680))  
              NAME680: NAME ((LEX JACK) (AGR 3S))  
            VP703: VP ((GAP NP ((AGR ?AGR693)) ) (VFORM PAST) (AGR 3S)              saw
                       (1 V681) (2 GAP694))  
              V681: V ((LEX SAW) (VFORM PAST) (SUBCAT _NP)
                       (AGR ?A324))  
              GAP694: NP ((EMPTY +) (GAP  NP ((AGR ?AGR693)) )                      NP/NP
                          (AGR ?AGR693)) 
    S737: S ((GAP  NP ((AGR 3S)) ) (WH -) (INV -) (VFORM PRES) (AGR 3S) 
             (1 NP711) (2 VP736))  
      NP711: NP ((GAP -) (WH -) (POSS -) (AGR 3S) (1 PRO684))                       He
        PRO684: PRO ((LEX HE) (ROOT HE1) (AGR 3S))  from 4 to 5 from rule NIL
      VP736: VP ((GAP  NP ((AGR 3S)) ) (VFORM PRES) (AGR 3S) (1 V729)                
                 (2 GAP733))  
        V729: V ((AGR 3S) (VFORM PRES) (ROOT WANT1) (SUBCAT _NP) (1 V685)           wants
                 (2 +S686))  
          V685: V ((LEX WANT) (ROOT WANT1) (VFORM BARE)
                   (SUBCAT (? S326 _NP_VP-INF _VP-INF _NP)))  
          +S686:<+S ((LEX +S))  
        GAP733: NP ((EMPTY +) (GAP  NP ((AGR 3S)) ) (AGR 3S))                       NP/NP
  
You can check that that the parser doe not allow sentence analyses in which a question or an already topicalized sentence is topicalized again.

We could easily add the rule

  ;; S -> ADJP S[-inv,/ADJP]
      ((S)
       -T3>
       (ADJP  (wh -) (gap -) (agr ?a))
       (head (S  (wh -) (inv -) (vform (? v pres past)) 
  	      (gap (% adjp))))
  
that would allow us to handle gaps if the parser was able to produce ADJP gaps.

Generating VP rules from subcategorization patterns

You can get the solutions to grads only LISP problem here.

The heart of the program is the function (parse-subcat  subcat) which, given the subcategorization value, such as _NP_PP produces the list of verbs complements in Allen's parser format.

To do that, it converts the symbol to string and breaks it on the "_" symbols, producing the list of strings that describe verb complements. After that, each string is broken on "-", producing the complement type and the complement restriction, for example ("vp"  "inf") . Then it calls the helper function (make-complement-with-features) which, given the phrase and he restriction, generates the proper constituent, such as (VP  (vform  inf)) . If the function does not know how to generate restriction for a given phrase, e.g NP, it just ignores the complement description. If it sees an unknown phrase name, it simply transforms it into a symbol trusting that the parser will know how to handle that type of constituent. In preparation to handle semantic interpretation rules it calls separate functions to generate feature sets for PP and VP. It expects that the subcats can be of the form _pp-dest-pred, meaning that the verb subcategorizes for predicative destination PP, or _vp-inf-obj, meaning that the verb is an object control verb that takes _vp-inf as a complement.

In order to generate rules one has to call

  (generate-subcat-rules lexicon)
  
The function first traverses the lexicon, finding all possible values of verb SUBCAT feature. This is done with the function (get-subcats  lexicon) . It makes sure that there are no duplicates in the subcat list. Then we call (generate-vp-rule  subcat) on every element of the subcats list, which in turn calls (parse-subcat  subcat) in order to produce the list of complements in the rule. To make a unique identifier for each rule, we use the subcategorization name. This is not the best possible solution, a slightly better idea would be to use gensym to ensure that the identifiers are truly unique.

Here's the output of the function on the lexicon used in Chapter5.lisp.

  
  USER(8): :4
  (SETQ *CHAPTER5-LEXICON*
        (APPEND *LEXICON4-6* (APPEND *LEXICON5-2* (APPEND *LEXICON5-6* *LEXICON-ADDITIONS*))))
  ((A (ART (AGR 3S) (ROOT A1)))
   (BE (V (ROOT BE1) (VFORM BARE) (SUBCAT (? S _ADJP _NP)) (IRREG-PRES +) (IRREG-PAST +)))
   (CRY (V (ROOT CRY1) (VFORM BARE) (SUBCAT _NONE))) (DOG (N (ROOT DOG1) (AGR 3S)))
   (FISH (N (ROOT FISH1) (AGR (? A 3S 3P)) (IRREG-PL +)))
   (HAPPY (ADJ (SUBCAT _VP-INF) (ROOT HAPPY1))) (HE (PRO (ROOT HE1) (AGR 3S)))
   (IS (V (ROOT BE1) (VFORM PRES) (SUBCAT (? S _ADJP _NP)) (AGR 3S)))
   (JACK (NAME (AGR 3S) (ROOT JACK1))) (MAN (N (ROOT MAN1) (AGR 3S))) (MEN (N (ROOT MAN1) (AGR 3P)))
   (SAW (N (ROOT SAW1) (AGR 3S))) (SAW (V (ROOT SAW2) (VFORM BARE) (SUBCAT _NP)))
   (SAW (V (ROOT SEE1) (VFORM PAST) (SUBCAT _NP) (AGR ?A)))
   (SEE (V (ROOT SEE1) (VFORM BARE) (SUBCAT _NP) (IRREG-PAST +) (EN-PASTPRT +)))
   (SEED (N (ROOT SEED1) (AGR 3S))) (THE (ART (ROOT THE1) (AGR (? A 3S 3P)))) (TO (TO (VFORM INF)))
   (WANT (V (ROOT WANT1) (VFORM BARE) (SUBCAT (? S _NP _VP-INF _NP_VP-INF))))
   (WAS (V (ROOT BE1) (VFORM PAST) (AGR (? A 1S 3S)) (SUBCAT (? S _ADJP _NP))))
   (WERE (V (ROOT BE1) (VFORM PAST) (AGR (? A 2S 1P 2P 3P)) (SUBCAT (? S _ADJP _NP)))) (+S (+S))
   (+ED (+ED)) (+EN (+EN)) (+ING (+ING))
   (CAN (AUX (MODAL +) (ROOT CAN1) (VFORM PRES) (AGR ?A) (COMPFORM BARE)) CAN1)
   (COULD (AUX (MODAL +) (ROOT COULD1) (VFORM (? V PRES PAST)) (AGR ?A) (COMPFORM BARE)))
   (DO (AUX (MODAL +) (ROOT DO1) (VFORM PRES) (AGR (? A 1S 2S 1P 2P 3P)) (COMPFORM BARE)))
   (DOES (AUX (MODAL +) (ROOT DO1) (VFORM PRES) (AGR 3S) (COMPFORM BARE)))
   (DID (AUX (MODAL +) (ROOT DO1) (VFORM PAST) (AGR ?A) (COMPFORM BARE)))
   (HAVE (AUX (VFORM BARE) (ROOT HAVE-AUX) (COMPFORM PASTPRT)))
   (HAVE (AUX (VFORM PRES) (ROOT HAVE-AUX) (AGR (?A 1S 2S 1P 2P 3P)) (COMPFORM PASTPRT)))
   (HAS (AUX (VFORM PRES) (ROOT HAVE-AUX) (AGR 3S) (COMPFORM PASTPRT)))
   (HAD (AUX (VFORM PAST) (ROOT HAVE-AUX) (AGR ?A) (COMPFORM PASTPRT)))
   (HAVING (AUX (VFORM ING) (ROOT HAVE-AUX) (COMPFORM PASTPRT)))
   (BE (AUX (ROOT BE-AUX) (VFORM BARE) (COMPFORM -)))
   (IS (AUX (ROOT BE-AUX) (VFORM PRES) (COMPFORM -) (AGR 3S)))
   (AM (AUX (ROOT BE-AUX) (VFORM PRES) (COMPFORM -) (AGR 1S)))
   (ARE (AUX (ROOT BE-AUX) (VFORM PRES) (COMPFORM -) (AGR (?A 2S 1P 2P 3P))))
   (WAS (AUX (ROOT BE-AUX) (VFORM PAST) (AGR (? A 1S 3S)) (COMPFORM -)))
   (WERE (AUX (ROOT BE-AUX) (VFORM PAST) (AGR (? A 2S 1P 2P 3P)) (COMPFORM -)))
   (BEEN (AUX (ROOT BE-AUX) (VFORM PASTPRT) (COMPFORM -)))
   (BEING (AUX (ROOT BE-AUX) (VFORM ING) (COMPFORM -)))
   (WHAT (PRO (WH Q) (ROOT WHAT) (AGR (? A 3S 3P))))
   (WHAT (QDET (WH Q) (ROOT WHAT) (AGR (? A 3S 3P))))
   (WHICH (QDET (WH Q) (ROOT WHICH) (AGR (? A 3S 3P))))
   (WHICH (PRO (WH R) (ROOT WHICH) (AGR (? A 3S 3P))))
   (WHEN (PP-WRD (WH (? W Q R)) (ROOT WHEN) (PTYPE TIME)))
   (WHOSE (PRO (WH (? W Q R)) (ROOT WHOSE) (POSS +) (AGR (? A 3S 3P))))
   (WHO (PRO (WH (? W Q R)) (ROOT WHO) (AGR 3S)))
   (WHERE (PP-WRD (WH (? W Q R)) (ROOT WHERE) (PTYPE (? P LOC MOT))))
   (PUT (V (SUBCAT _NP_PP-LOC) (ROOT PUT) (VFORM BARE) (IRREG-PAST +)))
   (PUT (V (SUBCAT _NP_PP-LOC) (ROOT PUT) (VFORM PAST) (AGR ?A)))
   (PUT (V (SUBCAT _NP_PP-LOC) (ROOT PUT) (VFORM PASTPRT) (AGR ?A)))
   (IN (P (PTYPE LOC) (PFORM IN) (ROOT IN1))) (BAG (N (ROOT BAG1) (AGR  3S))))
  
  USER(27): (LOADVPTEST) 
  ;; Loads the *non-vp-grammar* that doesn't have VP rules in it
  
  USER(28): (SETF *VP-GRAMMAR* (GENERATE-SUBCAT-RULES *CHAPTER5-LEXICON*))
  ((HEADFEATURES (VP VFORM AGR))
   ((VP (MAIN +) (PASSGAP -)) -VP-AUTO_NONE  (HEAD (V (SUBCAT _NONE))))
   ((VP (MAIN +) (PASSGAP -)) -VP-AUTO_VP-INF  (HEAD (V (SUBCAT _VP-INF))) (VP (VFORM INF)))
   ((VP (MAIN +) (PASSGAP -)) -VP-AUTO_NP_VP-INF  (HEAD (V (SUBCAT _NP_VP-INF))) (NP)
    (VP (VFORM INF)))
   ((VP (MAIN +) (PASSGAP -)) -VP-AUTO_ADJP  (HEAD (V (SUBCAT _ADJP))) (ADJP))
   ((VP (MAIN +) (PASSGAP -)) -VP-AUTO_NP  (HEAD (V (SUBCAT _NP))) (NP))
   ((VP (MAIN +) (PASSGAP -)) -VP-AUTO_NP_PP-LOC  (HEAD (V (SUBCAT _NP_PP-LOC))) (NP)
    (PP (PTYPE LOC))))
  USER(29): (AUGMENT-GRAMMAR *VP-GRAMMAR*)
  
  USER(30): (BU-PARSE '(HE SAW JACK))
  
  USER(31): (SHOW-ANSWERS)
  
   THE BEST PARSES FOUND
  S624: S ((GAP -) (WH -) (INV -) (VFORM PAST) (AGR 3S) (1 NP602)
           (2 VP621))  from 0 to 3 from rule -5-8-1 
    NP602: NP ((GAP -) (WH -) (POSS -) (AGR 3S) (1 PRO597))  from 0 to 1 from rule -5-7-1 
      PRO597: PRO ((LEX HE) (ROOT HE1) (AGR 3S))  from 0 to 1 from rule NIL
    VP621: VP ((GAP -) (PASSGAP -) (MAIN +) (VFORM PAST) (AGR 3S) (1 V598)
               (2 NP620))  from 1 to 3 from rule -VP-AUTO_NP 
      V598: V ((LEX SAW) (ROOT SEE1) (VFORM PAST) (SUBCAT _NP)
               (AGR ?A451))  from 1 to 2 from rule NIL
      NP620: NP ((GAP -) (AGR 3S) (1 NAME601))  from 2 to 3 from rule -B6 
        NAME601: NAME ((LEX JACK) (AGR 3S) (ROOT JACK1))  from 2 to 3 from rule NIL
  
The example demonstrates that the functions generates the set of rules for all possible subcat values and that those rules can be later applied and produce appropriate parses of the test sentences.