Case Study: Understanding Natural Language - Thinking as Computation - page 157

Figure 8.1. A grammar for declarative sentences

S → NP VP

VP → copula_verb Mods

VP → transitive_verb NP Mods

VP → intransitive_verb Mods

Mods →

→

Mods PP Mods

→

PP preposition NP

→

NP proper_noun

→

NP article NP2

→

NP2 adjective NP2

→

NP2 common_noun Mods

Figure 8.2. A sample parse tree

S

VP

copula Mods

NP PP Mods

article NP2 preposition NP

adjective NP2 article NP2

noun Mods noun Mods

The fat cat is on the mat.

8.1.3 Parsing and ambiguity

The process of taking a sequence of words and determining how they are structured
by the rules of a grammar is called parsing . This is done by producing a parse tree ,
with the sequence of words at the leaves (usually at the bottom) and the desired
nonterminal category at the root (usually at the top). A sample parse tree appears in
figure 8.2. For any of the categories that appear in the tree, the leaves below them are