June 10, 2004
Discussion of Lang paper
In our discussion of the and/or graph interpretation of parse forests from
Bernard Lang's paper, we attempted to construct the and/or graph of the parse
forest of the string "aaaa" from this grammar:
There are five possible trees that can be constructed from these rules that
have the desired yield:
We began by constructing the CKY table for this parse forest. The contents of
each cell correspond to our implementation of the algorithm. Each cell
contains a list of pairs whose first element is the label of the root node, and
whose second element is a list of links to possible children (i.e. pairs in
other cells). Because of the grammar we are working with, each cell only has
one such pair. Arrows were used to represent the links.
To construct the and/or graph, we put a label on each "A" to keep track of the
differences. We gave each "A" a two-digit subscript which reperesents its
column and row number from the CKY table respectively. The graph we came up
with looked like this:
It was realized that we could deduce the set of grammar rules from the and/or
graph by labeling the "A"s in the parse forest the same way we did in the
and/or graph. Then we can pull out every unique local tree. These local trees
are our grammar rules. We also noticed that the number of rules in the grammar
was equal to the number of nodes in the and/or graph, and this number was also
equal to the number of cells in the CKY table.
Finally, the and/or graph and CKY table are actually just two different
notations representing the exact same graph. The CKY table can be turned into
the and/or graph by simply making each cell a node and splitting the list of
links into the "or" choices of the graph.