Generating parse tree from CYK algorithm

Question

I use CYK algorithm (already implemented it in Java) to see if a string recognized according to a specific grammar. Now I need to generate a parse tree for the string, is the a way to generate the tree from the matrix which I use when using the CYK algorithm?

Genvieve

I assume your matrix consists of 0s and 1s or trues and falses. Instead of storing these boolean values you can create parse tree nodes and store them appropriately. – Flaminius

The Matrix contains the non-terminal symbols (From the Grammar). so I just need to generate the parse tree now – Genvieve

Answer 1

When implementing CYK as just a recognizer, then the boxes in the chart are generally just a set of bits (or other boolean values) that correspond to the productions that might apply at that point. That doesn't leave you enough information to reconstruct the parse tree.

If you instead store a set of objects, those objects include the non-terminal and keep track of the two productions that were combined. When you're done, you check if your final box contains an object which represents a start symbol production. If it does, you can follow the pointers back to reconstruct the parse tree.

Fremantle

Can you give an example? – Kiddush