The Tree Admissibility Interpretation
Abstract:
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:
Figure 3: An Example Parse Tree. This tree represents the analysis of the string "aabb" according to the gramar given. |
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 S→ASB as saying: A tree node labelledScan have exactly three daughters, labelled (reading left to right)A, S, andB. The node labelled A is ok, because under the tree admissibility interpretation we read the rule A→a as saying: A tree node labelledAcan have exactly one daughter which is labelleda. 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.
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.