CYK algorithm: Difference between revisions

Revision as of 22:02, 26 February 2014

Revision as of 18:31, 27 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 booleansthe boolean 1. SinceThe thenode parsingis processlinked generatesto alsothe unneededarray subtreeselements that cannotwere beused immediatelyto knownproduce as uselessit, itso is necessaryas to storebuild athe listtree ofstructure. rootsOnly ofone subtreessuch alreadynode foundin (ateach leastarray oneelement foris eachneeded possibleif non-terminal,only evenone ifparse onetree wishesis to onlybe pickproduced. onlyHowever, oneif of the possibleall parse trees); theare endto resultbe iskept, thenit ais shared-forestnecessary ofto possiblestore parsein trees.the Thisarray sharedelement foresta canlist convenientlyof beall readthe as a grammar generating onlyways the sentencecorresponding parsed,node withcan be anyobtained ofin the parse-treesparsing correspondingprocess. toThis theis originalsometimes grammar,done up towith a verysecond simpletable renamingB[n,n,r] of nonso-terminals, as shown bycalled {{harvtxt|Lang|1994}}''backpointers''.

The end result is then a shared-forest of possible parse trees, where common trees parts are factored between the various parses. This shared forest can conveniently be read as an ambiguous grammar generating only the sentence parsed, but with the same ambiguity as the original grammar, and the same parse trees 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''.

===Parsing non-CNF context-free grammars===