Linguistics 581

Context-Free grammars

Homework assignment


A. End of chapter 12. Exercises 12.1, 12.2.

For exercises 12.1 and 12.2 you should start with the ATIS Grammar, which is given in slightly fuller form in Chapter 13, in Figure 13. 1.

You will need to make some changes to the grammar in Fig. 13.1 to handle everything in 12.1 and 12.2, especially 12.2:

  1. First, you will need to add some words to the grammar.
  2. Then you will need to adds some rules.
Keep track of the additions you have to make to the grammar to draw adequate trees for the phrases and sentences in 12.1 and 12.2. You will hand those in as hard copies as part of the assignment.

B. Part 1. Next consider the next two sentences:

    (a) I would like a flight to the capital from Boston
    (b) I would like a steak with a side of fries
      Pronoun Aux Verb Det Noun Preposition Det Noun Preposition Noun
These two sentences have exactly the same parts of speech but they do not have the same syntactic analysis (trees). In (b), the Det Noun Preposition Noun sequence a side of fries is an NP. In (a), the corresponding words the capital from Boston is not an NP. See if you can draw the right trees. There are various choices you can make, but see if you can draw trees that make both a flight to the capital from Boston and a steak with a side of fries NPs. You will certainly have to add words to the grammar. But the interesting question is: Do you have to add other kinds of rules to the grammar?

Draw the right trees by hand. Report any changes you had to make to the grammmar to get the right trees. When you're done we'll call this the context-free grammar treatment. B. Part 2. Next consider the next two sentences: Then, finally, consider the following standard finite-state treatment of prepositional phrases inside Noun Phrases which we'll cast in XFST.

    define Noun [{flight}|{meal}|{capital}|{fries}|{Boston}|{side}|{steak}];
    define Det [{the}|{a}];
    define Prep [{to}|{with}|{from}|{of}];
    define nounphrase [(Det " ") Noun (" " Prep " " (Det " ") Noun)* ];
    # End Grammar Part
    # Some tricks to give you bracketed output.
    define npbracket 0:%< nounphrase 0:%> ;
    define r1 [npbracket.u @-> "{{{" ... "}}}"] ; 
    define r2 [\"{{{"* [ "{{{":[] npbracket "}}}":[] \"{{{"* ]*] ;
    define MaxMatch r1 .o. r2 ;
    push MaxMatch;
    # End tricks
This little transducer wraps brackets around the input if it is recognized as a noun phrase. The parts involving r1 and r2 are just to make sure that only a maximal matching np gets brackets. So in "a flight to the capital from Boston", there are a number of NPs inside the phrase: a flight , a flight to the capital , the capital, and Boston are NPs according to the nounphrase rule defined above. The second half the script guarantees that only the largest one gets bracketed (primarily through the use of directed replacement "@-→"). To simplify life, the finite-state treatment ignores the distinction between Noun and ProperNoun. Assume this is not important. Try loading this into a file called compling_exercise.script and then staring xfst and doing:
source compling_exercise.script
Then do
xfst[12]: apply down
And try the two sentences above. Does the finite-state treatment capture the same facts as the context-free grammar treatment? Can you imagine an application in which the context-free grammar treatment would be better than this finite-state treatment? A final thought. You may be better able to see the difference between the two NPs a flight to the capital from Boston and a steak with a side of fries by just looking at the parts of speech, ignoring the determiners, and thinking of the prepositions as operators, a bit like the operator '+' and '*'' in arithmetic, with the nouns acting as the arguments (or numbers) those operators are acting on.
      N1   N2   N3
    (a) steak with side of fries
    (b) flight from capital to boston
        +   *  
Then this situation creates an ambiguity. Which "operator" gets to act on the Noun to its left first. If "from" goes first in (b), we get "flight from capital", that is, a particular kind of flight, combining with "to" and "boston". So what goes to Boston is a flight, and that's right. That corresponds to this way of parenthesizing the operators
    (flight from capital) to Boston [Right!]
So when we say this is right,. we mean it's right for the meaning the phrase. to Boston is specifying what kind of flight this is (we say it's modifying flight)

On the other hand, if "to" goes first, it combines with "capital" on its left and we get this parenthetization.

    flight from (capital to Boston) [Wrong!]
This is wrong because from Boston shouldn't be modifying capital. It's not the captial that's from Boston; it's the flight.

On the other hand, the other phrase works the other way, We want the second preposition to go first:

    steak with (side of fries) [Right!]
because fries is tellng us what kind of side dish this is, so of fries is modifying side.

And its very wrong to do

    (steak with side) of fries [Wrong!]