5.1.2 The Tree Admissibility Interpretation

While the rewrite interpretation of CFGs is important, there is a more fundamental way of thinking about CFGs, namely as tree admissibility rules.

While the rewrite interpretation of CFGs is important, there is a more fundamental way of thinking about CFGs, namely as tree admissibility rule s.

A parse tree is a finite tree all of whose interior nodes (that is, nodes with daughters) are licensed (admitted) by a grammar rule. What does this mean? Let's look at an example:

A Parse Tree

This tree is licensed by our grammar --- that is, the presence of every node with daughters can be justified by some rule. For example. the top node is ok, because under the tree admissibility interpretation we read as saying: A tree node labelled can have exactly three daughters, labelled (reading left to right) , , and . The node labelled A is ok, because under the tree admissibility interpretation we read the rule as saying: A tree node labelled can have exactly one daughter which is labelled . Similarly, all the other nodes with daughters are `justified' or `admitted' by other rules (the terminal nodes of the tree don't need to be justified).

If you think about it, you will see that there is a close correspondence between parse trees and derivations: every derivation corresponds to a parse tree, and every parse tree corresponds to (maybe many) derivations. For example, the tree above corresponds to both our earlier derivations of `aabb'.

The tree admissibility interpretation is important for two reasons. First, it is the linguistically most fundamental interpretation. We don't think of natural language as a bunch of strings that need rewriting --- we think of natural language sentences, and noun phrases and so on as having structure, tree structure. Thus we think of CFG rules as telling us which tree structures we have.

Ambiguity

Second, the idea of parse trees brings us to an important concept: ambiguity . A string is ambiguous if it has two distinct parse trees. Note: We said `parse trees', not `derivations'. For example, we derived the string `aabb' in two different ways from our little grammar --- but both ways correspond to the same derivation tree. That is, the string `aabb' is not ambiguous in this grammar. And in fact, no string this grammar generates is ambiguous. But we will see that some grammars do generate ambiguous strings.