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.