Building a syntax tree from a chart
BuildTree(Chart,Words[0 .. K])
{ N := make a node for the root of the tree;
ExpandTree("S",Chart,Words,N,0,K)
}
ExpandTree(Symbol,Chart,Words,N,START,END)
{ label node N with Symbol;
if (Symbol is a part of speech)
then { make a leaf node labelled WORDS[END];
make an arc from N to the leaf node;
]
else { find an edge E in Chart of the form
[START, END, Symbol -> Sym[1], Sym[2] ... Sym[p] *];
for (j := p downto 1) do {
find two edges E1 and E2 in Chart such that
(E1 == [SS1, END, Sym[j] -> String]) and
(E2 == [START,SS1, Symbol ->
Sym[1] ... Sym[j-1] * Sym[j] ... Sym[p]);
/* That is, E was formed by applying the extender to E2, E1 */
make a new leftmost child NC of N;
/* Note that the tree is built from right to left */
ExpandTree(Sym[j],Chart,Words,NC,SS1,END);
END := SS1;
} /* end for loop */
}
}
To find all the parse trees, you have to consider all the options at the
two statements "find an edge" and "find two edges" above.