Assignment 5

Due Thursday, May 20^th in class. This homework only has two problems, each with two parts, a and b. As always, email your code to the TA and hand in the written portions in class, by the beginning of lecture.

Semantics

1. In conceptual dependency (CD), we have the 11 primitives discussed in class, but also have representations for state and causality. For state we have the following primitive notions:
   • HEALTH (dead, gravely ill, under the weather, tolerable, feelin' rosy)
   • ANTICIPATION (terrified, nervous, hoping, confident)
   • MENTAL STATE (broken, depressed, all right, happy, ecstatic)
   • PHYSICAL STATE (end of existence, damaged, just peachy)
   • AWARENESS (dead, unconscious, asleep, awake, alert)

   If you want to be concrete, we can scale these from -10 through 0, up to 10. So, someone in the picture of health would have state HEALTH(10).

   For example, we could start with the English sentence, John told Mary that Bill was happy. Encoding this with the states we've defined, we have:

   John MTRANS(Bill BE MENTAL.ST(5)) to Mary

   Another MTRANS example would be the fairly common action of reading: Sally read a Web page.

   Sally MTRANS(Information) to LTM(Sally) from WebPage inst(Sally ATTEND eyes to WebPage)

   Rendered back into English, this says:

   Sally transferred mental information to her own long-term memory from a Web page by focusing her eyes on the Web

   For causality, we have the arrow symbol () to depict causality, and several classes of causality. We can break down the causality classes as follows:

   Description	Representation
   Actions can result in state changes	ACTION
   	r
   	STATE
   States can enable actions	STATE
   	E
   	ACTION
   States can disable actions	State
   	dE
   	ACTION
   States/acts can initiate mental states	STATE (or ACTION)
   	I
   	MENTAL.ST
   Mental states can be reasons for actions	MENTAL.ST
   	R
   	ACTION

   Suppose we have the sentence John healed Mary. In this case, we don't know what action John performed, so we use the action "placeholder" DO.

   John DO

   E

   Mary HEALTH(6)

   a) Given this, your job is to represent the following story in CD:

   John needed money. He read the want ads. He found found the job for him, polished his resume and bought a suit. The next day at the interview, John spit twice in the face of the interviewer. The interviewer was very upset. John was not hired.

   b) Can you think of an example from everyday language that can't be represented in CD? Give an example, and how you would change CD to allow for it.

Bottom-up chart parsing

1. You'll find the code for the bottom-up chart parser we discussed in class in the directory: /export/classes/archive/1999/spring/CS251/NLU/PARSER1.1
   To use the parser follow these steps (these are written for using ACL on the Classes server, but the steps are similar for Mac and ACL for Windows)¹:
   1. Change to the directory /export/classes/archive/1999/spring/CS251/NLU/PARSER1.1
   2. Run ACL (using "acl" from the Unix prompt).
   3. Enter (load "loadp.lisp") at the Lisp prompt. This will load the code for the parser and support files, but no grammar or lexicon.
   4. Enter (LoadChapter4) to load the grammar and lexicon from Chapter 4 (which you don't have, but that's okay, you don't need it).
   5. The function LoadChapter4() returns a list of words defined in the lexicon (which you can recall at any time by invoking the function defined-words().)
   6. To parse a sentence, call the function bu-parse() with a list of words as symbols. For example:

      (bu-parse '(Jack saw the man cry +ing))

      Notice that the parser won't work with the sentence "Jack saw the man crying", because it doesn't have a morphology package loaded. Instead you have to give the base form (cry) plus the inflected ending (-ing). The parser will then recognize the progressive nature of the verb tense.

   7. You can see the interaction with the chart in detail by entering (verboseon) to increase the trace information. The trace would look something like this:

      		
      
      			
      
      				
      Verbose Trace of Bottom-up Parser
      			
      			
      
      				
      
      					
      Entering constituent name48 from 0 to 1
           <name ((lex jack) (agr 3s) (root jack1))>
      
      Entering constituent v51 from 1 to 2
           <v ((lex is) (root be1) (vform pres) (subcat (? s3 _adjp _np)) (agr 3s))>
      
      Adding active arc: 
      <vp ((vform pres) (agr 3s) (1 v51))> 
          -5> 
              (<v ((subcat _np) (vform pres) (agr 3s))>) 
              *
               (<np nil>) from 1 to 2
      
      					
      	:
      				
      			
      		
      

   1. Use the parser to parse a sentence of four or more words, and annotate the verbose output. Your annotation should mention why an operation was performed and what data was used (i.e. a grammar rule, lexical entry, etc...). The parser output includes feature information, which we discussed in general but not the specifics of the features actually used with this grammar, so don't focus on the features themselves, but on the lexical types. A good way to tackle this question would be to create a figure from the trace similar to that in Figure 3.12 in the reading..
   2. As we discussed in class, parsers can be either bottom-up or top-down, with or without a chart. (We didn't discuss top-down chart parsers, but they exist, and are described in Section 3.6 in your reading.) In addition, parsers can search depth-first or breadth-first for a successful parse. Examine the code for the bottom-up parser, and determine whether it searches depth-first or breadth-first, and explain your reasoning. Modify the code so that it searches using the alternative technique, i.e. make it depth-first if it's already breadth-first and vice versa. For the code portion of this assignment you should submit only those functions you needed to rewrite to change from one strategy to another.