CYK algorithm: Difference between revisions

Revision as of 15:10, 26 February 2014

Revision as of 22:02, 26 February 2014

Line 78:

==Extensions==

===Generating a parse tree===

The above algorithm is a [[recognizer]] that will only determine if a sentence is in the language. It is simple to extend it into a [[parser]] that also construct a [[parse tree]], by storing parse tree nodes as elements of the array, instead of booleans. Since the parsing process generates also unneeded subtrees that cannot be immediately known as suchuseless, it is necessary to store a list of roots of potentialsubtrees subtreealready rootsfound (at listleast omeone for each possible non-terminal, even if one wishes to only pick only one of the possible parse trees); the end result is then a shared-forest of possible parse trees. This shared forest can conveniently be read as a grammar generating only the sentence parsed, with any of the parse-trees corresponding to the original grammar, up to a very simple renaming of non-terminals, as shown by {{harvtxt|Lang|1994}}.

An alternative formulation employs a second table B[n,n,r] of so-called ''backpointers''.