Generate a syntax tree from the CYK algorithm

Question

I use an algorithm CYK(already implemented in Java) to find out if a string is recognized according to a specific grammar. Now I need to generate a parse tree for a row, is there a way to generate a tree from the matrix that I use when using the algorithm CYK?

Answer 1

When introducing CYK as a recognizer only, the fields in the diagram, as a rule, are only a set of bits (or other logical values) that correspond to the products that can be applied at this point. This does not leave you enough information to restore the parsing tree.

If you instead store a collection of objects, these objects include a non-terminal and track two shared works. When you are done, you will check if your last block contains an object that represents the beginning of the character. If so, you can follow the back signs to restore the parse tree.