In some of the exercises below you are asked to use the Python module nltk to build and use phrase structure grammars. All necessary modules and helpers can be obtained via coursepy. You can directly use nltk itself if you like.

The imports needed:

from coursepy.lang.parsing import make_parser, make_cfg

Here is an example grammar:

grammar = make_cfg("""
S  -> NP VP
NP -> Det N
VP -> V
VP -> V NP

Det -> 'every' | 'a' | 'the' | 'some'
N   -> 'student' | 'professor' | 'dog'
V   -> 'walks' | 'saw' | 'talks'
""")

You build a parser based on the grammar you defined:

parser = make_parser(grammar)

Now you can map any expression to the list of its parse trees using the parser:

trees = parser("every student walks")

You can print the trees to the console to see their structure:

[t.pretty_print() for t in trees]

Tree objects also have a .draw() method that opens a separate window with a graphical representation of the tree.

You are given the following grammar:

S  -> NP VP
NP -> Det N | Det N PP
VP -> V NP | VP PP
PP -> P NP
Det -> 'the' | 'a'
N  -> 'dog' | 'owner' | 'leash'
V  -> 'found'
P  -> 'with'

Draw all the possible parse trees for the sentence The owner found the dog with the leash.

🗝️

You are given the following grammar:

S  -> NP VP
NP -> Det N
VP -> V
VP -> V NP

Det -> 'every' | 'a' | 'the' | 'some'
N   -> 'student' | 'professor' | 'dog'
V   -> 'walks' | 'saw' | 'talks'
  1. Extend your grammar so that you can parse sentences like Every student saw a dog with a telescope, with its two readings (i.e., the one in which the dog has a telescope, and the one in which the student has a telescope).
  2. Your grammar generates ungrammatical sentences like *Every student saw (English requires an explicit object in this case). Modify your grammar so that it does not generate such sentences. But, be careful, both Every student walks and Every student walks a dog are grammatical, you should do justice to this fact as well.
  3. Extend your grammar so that your grammar accepts sentences like Every student talks to a professor and rejects *Every student talks a professor.

Feel free to introduce new non-terminal symbols to your grammar.

🗝️

Consider simple arithmetic expressions involving addition and multiplication, such as:

3 + 4
3 + 4 * 2
( 3 + 4 ) * 2

Write a CFG over the terminals \(\lbrace +, *, (, ),2,3,4\)} that generates such expressions. Your grammar should assign more than one phrase structure to ambiguous expressions like 3 + 4 * 2.

🗝️