Ling/CSE 472: Assignment 2: Morphology, Parsing

Due October 21st, by the start of class

This assignment does not involve writing any code. As such, please turn in written answers to all of the questions below in class.

1. Morphology and FSTs

(Adapted form of:) Problem 3.2 (p.89)

Give one example of each of the noun, verb and adjective classes in Figure 3.6, and find two stems (noun, verb, or adjective) which are exceptions to the rules, i.e., which fit the apparent definition of the class, but don't in fact have all of the forms that the machine predicts.

Problem 3.4 (p.89)

Write a transducer(s) for the K insertion spelling rule in English. (Be sure to check it with both positive and negative examples, that is, words that it should apply to and words that it shouldn't.)

2. Parsing

Start the LKB, and load the grammar

The LKB System (Copestake 2002) (a parser, generator and grammar development environment) is installed on the machines in Denny 109 as well as the PCs in Denny 112.

Start the LKB by going to "My Computer" in the start menu, and then opening C:\Program Files\lkb_windows\windows. In this directory, you'll find lkb.exe. Double click lkb.exe, to start the LKB. You should see a window entitled "Lkb Top". This window has menus that you will use, as well as some space to print messages that you should pay attention to.

Next, you'll need to download the grammar, which consists of these files:

• rules.tdl
• lexicon.tdl
• types.tdl
• script
• globals.lsp
• user-fns.lsp

Create a directory in My Documents called Grammar, and save the files there. (No need to cut and paste -- just right click the links and select "Save Target As..."). If Windows added the .txt extension to any of the files, use Rename in (available in the right-click pop-up menu in Windows Explorer) to get rid of it.

Load the grammar by selecting Load > Complete Grammar in the Lkb Top window. In the dialogue that pops up, click "My Documents" (on the left hand side), then "Grammar", then "script" then "open" (the button).

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.
• 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 (in WordPad, making sure not to save it as an rtf file). 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.)

C. Parsers and Grammars

For this part of the assignment, you'll need to edit the file rules.tdl. You need to make sure that when you save it, it is still a text file (although without the .txt extension) and not an rtf file or a Word document or anything else. WordPad seems to be okay.

In general, parsers (and grammar development environments) should be written to make as few assumptions about the grammars they parse as possible. For example, the LKB allows the user to define the (set of possible) start symbol(s) for their grammar, rather than assuming it's S (see above). However, parsers (and grammar development environments) do need to define what they will accept as well-formed grammars, check for well-formedness, and anticipate other kinds of user errors.

• Edit the file rules.tdl, and remove the final period from one of the grammar rules, save rules.tdl, and reload the grammar (Grammar > Reload grammar in the LKB menu). What happens? Now go fix it.
• Add the following rule to rules.tdl:

  np := np & [ ARGS < np , pp, pp > ].
  

  Reload the grammar. What happens?
• Parse Kim adores snow in Oslo. Why is there now only one parse for this sentence? (Now remove the extra rule, or find another way to leave it in without causing these problems.)
• Uncomment the two last rules in rules.tdl (remove the semi-colon at the beginning of each line). Reload the grammar. Parse Kim snores.
  • What happens?
  • Look at the parse chart -- what do you see there?
  • What is wrong with those two rules?
  • How is the LKB dealing with the problem?
  • Would you expect a natural language grammar to ever need rules like that? Why or why not?