Content deleted Content added
mNo edit summary |
→Algorithm extension: +subheaders |
||
Line 50:
|}
===Algorithm
====Generating a parse tree====
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''.
====Parsing weighted context-free grammars====
It is also possible to extend the CYK algorithm to parse strings using [[weighted context-free grammar|weighted]] and [[stochastic context-free grammar]]s. Weights (probabilities) are then stored in the table P instead of booleans, so P[i,j,A] will contain the minimum weight (maximum probability) that the substring from i to j can be derived from A. Further extensions of the algorithm allow all parses of a string to be enumerated from lowest to highest weight (highest to lowest probability).
| |||