Content deleted Content added
Unicodifying |
m →The algorithm: wfy |
||
Line 8:
==The algorithm==
The CYK algorithm is a [[bottom-up parsing|bottom up]] algorithm and is important theoretically, since it can be used to constructively prove that the [[membership problem]] for context-free languages is [[decision problem|decidable]].
The CYK algorithm for the membership problem is as follows:
Line 52:
===Algorithm extension===
It is simple to extend the above algorithm to not only determine if a sentence is in a language, but to also construct a [[parse tree]], by storing parse tree nodes as elements of the array, instead of booleans. Since the grammars being recognized can be ambiguous, it is necessary to store a list of nodes (unless one wishes to only pick one possible parse tree); the end result is then a forest of possible parse trees.
An alternative formulation employs a second table B[n,n,r] of so-called ''backpointers''.
| |||