Context Free Grammar A Simple Grammar

Let's start off by looking at a simple context-free grammar (CFG). By convention, the lefthand side of the first production is the start-symbol of the grammar, typically S, and all well-formed trees must have this symbol as their root label. In NLTK, context-free grammars are defined in the nltk.grammar module. In Example 8-1 we define a grammar and show how to parse a simple sentence admitted by the grammar.

Example 8-1. A simple context-free grammar.

grammarl = nltk.parse_cfg(

V -> "saw" | "ate" | "walked" NP -> "John" | "Mary" | "Bob" | Det N | Det N PP Det -> "a" | "an" | "the" | "my" N -> "man" | "dog" | "cat" | "telescope" | "park" P -> "in" | "on" | "by" | "with" )

>>> sent = "Mary saw Bob".split()

>>> rd_parser = nltk.RecursiveDescentParser(grammarl)

>>> for tree in rd_parser.nbest_parse(sent):

The grammar in Example 8-1 contains productions involving various syntactic categories, as laid out in Table 8-1. The recursive descent parser used here can also be inspected via a graphical interface, as illustrated in Figure 8-3; we discuss this parser in more detail in Section 8.4.

Table 8-1.

Syntactic categories






the man walked


noun phrase

a dog


verb phrase

saw a park


prepositional phrase

with a telescope







Symbol Meaning Example

V verb walked

P preposition in

A production like VP -> V NP | V NP PP has a disjunction on the righthand side, shown by the and is an abbreviation for the two productions VP -> V NP and VP -> V NP PP.

If we parse the sentence The dog saw a man in the park using the grammar shown in Example 8-1, we end up with two trees, similar to those we saw for (3):

Since our grammar licenses two trees for this sentence, the sentence is said to be structurally ambiguous. The ambiguity in question is called a prepositional phrase attachment ambiguity, as we saw earlier in this chapter. As you may recall, it is an ambiguity about attachment since the PP in the park needs to be attached to one of two places in the tree: either as a child of VP or else as a child of NP. When the PP is attached to VP, the intended interpretation is that the seeing event happened in the park.

Parser Demo Tree

Figure 8-3. Recursive descent parser demo: This tool allows you to watch the operation of a recursive descent parser as it grows the parse tree and matches it against the input words.

However, if the PP is attached to NP, then it was the man who was in the park, and the agent of the seeing (the dog) might have been sitting on the balcony of an apartment overlooking the park.

Was this article helpful?

0 0

Post a comment