Ling/CSE 472: Assignment 4: Parsing

Due May 12th (Part 1) and May 18th (Parts 2 & 3)

For this assignment, you will be using the LKB grammar development environment. The LKB is installed on the machines in the Treehouse. It is open source software, and runs on linux. If you want to run it on a Mac or Windows machine, you can set up Linux as a virtual machine using VirtualBox. (Instructions for installing KNOPPIX+LKB as a VB appliance) In fact, even for linux users, we recommend installing the virtual machine as the most reliable way to get the LKB running.

For this assignment, you will be asked to turn in typed answers (Parts 1, 2 and 3) and working grammars (Parts 2 and 3). Here are template answer files for Part 1 and Parts 2 and 3. Recall that we are looking for complete sentences/paragraphs in answer to these questions.

Be sure to get an early start so that you have time to ask questions on Canvas.

Part 1. CFGs and the LKB Parse Chart

Start the LKB, and load the grammar

Log into one of the Treehouse machines, or start up VirtualBox on your local machine, and start emacs by typing emacs & in a terminal window.
In emacs, start the LKB by typing M-x lkb (where M is the esc or alt key).
Download the grammar for this assignment, by saving the file linked here: grammar1.tgz.
Move the downloaded file to your home directory or somewhere else suitable.
Unpack the tar archive by executing this command in the directory containing the file you downloaded:
```
tar xzf grammar1.tgz
```
Load the grammar by selecting Load > Complete Grammar in the Lkb Top window. In the dialogue that pops up, navigate to "grammar1" and select "script". Then click the "open" button.
(Note: If the dialogue box isn't doing what you expect, try typing the complete path to the "script" file e.g., /home/ebender/grammar1/script into the "selection" box and then clicking "open".)

A. Charts and trees, edges and nodes

Familiarize yourself with the contents of rules.tdl and lexicon.tdl. These define the phrase structure rules and lexicon of a baby CFG. Note the funny syntax (rule forms) and make sure you understand how it corresponds to `ordinary' CFG syntax:
```
rule1 := A & [ ARGS < B , C > ].
```
Is equivalent to:
```
A -> B C  (rule1)
```
Where "rule1" is just a name for the rule. (The reason for the funny syntax is that the LKB expects typed feature structure grammars, not CFGs. This is a way of coding up a CFG in TFS format, developed by Stephan Oepen. If you're curious about how it works, take a look in types.tdl.)
Parse Kim snores (In the Lkb Top window, select "Parse > Parse input ...") The LKB should return a tree. You can also view the parse chart by selecting "Parse > Show parse chart" from the Lkb Top window. Compare the tree and the parse chart. In the chart, you can also get small trees for each edge (from the pop-up menu that comes up when you click on an edge). Look at the trees for each edge, and convince yourself that they fit together to form the complete tree.
Note: The edges should have meaningful labels on them (e.g., S, VP). If you see "NIL" instead, it means you're running the alternate user interface called the LUI. To turn it off, in the *common-lisp* buffer of emacs, at the LKB prompt, type (lui-shutdown).
Parse Kim snores in Oslo, and examine the parse chart. Why are there more edges in the chart than nodes in the tree? Are the `extra' edges warranted? Why or why not?
Parse Kim adores snow, and examine the parse chart. Why are there more edges in the chart than nodes in the tree? Are the `extra' edges warranted? Why or why not?
Parse Kim adores snow in Oslo. The LKB returns two trees (the sentence is ambiguous), with a total of 18 non-terminal nodes between them. The chart shows only 15 edges. Why?

B. Start symbols

Parse In Oslo, Kim adores snow, and examine the chart. There are two edges with category S. Why doesn't the parser return either of them?
Find three other strings made up of the vocabulary in the grammar (see lexicon.tdl) that the grammar won't accept.
Now change the start symbol from just S to S or NP. You can do this by selecting "Options > Set options..." from the Lkb Top window, and then changing the value for *start-symbol* from (S) to (S NP). The LKB will ask you for a file to save the parameters in. Select globals.lsp, and say okay when it asks about overwriting the existing file. Alternatively, you can accomplish the same thing by editing the file globals.lsp. Change this:
```
(defparameter *start-symbol* '(s))
```
to this:
```
(defparameter *start-symbol* '(s np))
```
and reload the grammar.
Show that the parser now accepts a string that it didn't before. (For your write up, state which string it is.)

Part 2. Feature structures

In order to give you some experience with feature structures and unification, this part of the assignment asks you to do some grammar engineering, using the LKB. In particular, you will implement the feature-based analysis of agreement (subject-verb and determiner-noun) described in the chapter, and a simple feature-based version of subcategorization.

Getting started

Download the starter grammar: grammar2.tgz, move it to a suitable directory, and unpack it:
```
tar xzf grammar2.tgz
```
For part 2 of this assignment, you'll be editing rules.tdl and lexicon.tdl. For part 3, you'll be editing those files again, plus types.tdl.
As before, we've provided a text file with some prompts to create your write-up: parts-2-3.txt

Background: the LKB, types, and tdl syntax

grammar1 (used in part 1 above) looked like a CFG, but in fact, it, like grammar2, is a typed feature-structure (TFS) grammar, since that is what the LKB can parse. (The CFGs are just CFGs coded up as TFS grammars.) Furthermore, they are stated in Type Description Language (TDL), with the following syntax:

typename := supertype1 & supertype2 & ... & supertype3 &
 [ FEATURE_1 value_1,
   FEATURE_2 value_2,
      ...
   FEATURE_N value_n ].

Features with complex values look like this:

typename := supertype &
  [ FEATURE_1 [ FEATURE_2 value_2,
                FEATURE_3 value_3 ],
    FEATURE_4 value_4 ].

If you just want to talk about one feature inside the value of another, you can write it like this: (Note the period in between the feature names.)

typename := supertype &
   [ FEATURE_1.FEATURE_2 value2 ].

NB: The following is not equivalent to the above:

typename := supertype &
   [ FEATURE_2 value2 ].

Reentrancy is indicated with variables beginning with #. For example:

typename := supertype &
 [ FEATURE_2 #same,
   FEATURE_3.FEATURE_4 #same ].

Lists are represented as feature structures with two features, FIRST and REST. The value of FIRST is the first element on the list. The value of REST is another list, or *null*. (The relevant types are defined at the bottom of types.tdl.) You can use these features to constrain particular members of lists, or you can use the following notation:

typename := supertype &
  [ LIST_FEATURE < [ FEATURE_1 value_1 ] , ... > ].

typename := supertype &
  [ LIST_FEATURE < othertype , [ FEATURE_1 value_1 ] > ].

The first example above involves a list with at least one element on it. The second involves a list with exactly two elements on it.

The LKB requires that all features be declared for exactly one type (they can be inherited and further constrained by subtypes). If you try to introduce features with the same name on different types (and one is not a subtype of the other) it will complain.

The LKB distinguishes between types and instances, the latter to be found (in this grammar) in rules.tdl and lexicon.tdl. It is only because of this that we can 'overload' symbols like s and use them as both rule names and type names.

Here is a partial LKB/Grammar Engineering FAQ, which may be helpful.

Feature-based analyses of agreement and valence

Start the LKB and load the grammar.
Batch parse the file test.items, by choosing "Parse > Batch Parse..." from the LKB top menu. (It will ask you to specify and input file and an output file. Select test.items and test.out, respectively.)
Examine the contents of test.out. You'll see one line for each test item, followed by some numbers. These numbers represent the number of complete parses found, the number of edges created during parsing, and the time it took. Note that *s indicate ungrammatical sentences. These should have 0 parses when you're finished.
Add constraints on the value of HEAD.AGREEMENT.NUMBER to lexical entries and grammar rules. (These features have been declared already on appropriate types, in types.tdl. The possible values of NUMBER are sg and pl. The starting grammar includes a feature PERSON under AGREEMENT, but as this assignment only considers 3rd person forms, it won't be needed.)
Reload the grammar, paying attention to the LKB Top window in case it prints any error messages. (It's worthwhile to scroll up in the window to check higher up.)
Test your changes by rerunning the batch file (and, if you like, parsing individual sentences), and refine as necessary.
Using the feature VAL (appropriate for the type v, with possible values tr and itr) refine your grammar to rule out the two remaining unaccounted for ungrammatical sentences, without ruling out any others.
Once again, use the batch parsing utility to test your work.

To turn in your grammar for this part, create a tar archive, and upload it to Canvas. You can create the tar archive by running the following command in the directory above `grammar2'.

tar czf grammar2.tgz grammar2/

Part 3: Using types to capture generalizations

Make a copy of grammar2 to modify for this part of the assignment:

cp -r grammar2 grammar3

For this part of the assignment, you should modify grammar3.

You may have noticed that you were typing the same thing over and over again in Part 1. This part of the assignment asks you to make use of the types to state each constraint exactly once, and make any instance or type that needs it inherit from that supertype.

Hints:

Types can inherit from multiple supertypes.
Instances should not. (So you might need to define some more types that do the multiple inheritance, which the instances can then inherit from.)
The LKB Top menu has options for exploring the type hierarchy you've defined. Select "View > Type Hierarhcy". Clicking on any type in a window should bring up a menu with options including "Type Definition" (exactly what you've typed in to the file) and "Expanded Type" (all of the constraints on the type, including those inherited from supertypes).
As you make changes, load the grammar into the LKB to make sure there aren't any syntax errors, and test its behavior with the batch parse function.

When you have a grammar that doesn't have any repeated constraints and that accounts for all of the data (both positive and negative) in test.items, create a tar archive of it, and turn it in!

Don't forget to answer the questions in the file parts-2-3.txt for your write up.

Back to main course page