Content deleted Content added
m →Example: avoid confusion: "iff" -> "if and only if" |
Phil Boswell (talk | contribs) m convert dodgy URL to ID using AWB |
||
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 the boolean 1. The node is linked to the array elements that were used to produce it, so as to build the tree structure. Only one such node in each array element is needed if only one parse tree is to be produced. However, if all parse trees of an ambiguous sentence are to be kept, it is necessary to store in the array element a list of all the ways the corresponding node can be obtained in the parsing process. This is sometimes done with a second table B[n,n,r] of so-called ''backpointers''.
Line 91 ⟶ 92:
===Valiant's algorithm===
The [[Analysis of algorithms|worst case running time]] of CYK is <math>\Theta(n^3 \cdot |G|)</math>, where ''n'' is the length of the parsed string and ''|G|'' is the size of the CNF grammar ''G''. This makes it one of the most efficient algorithms for recognizing general context-free languages in practice. {{harvtxt|Valiant|1975}} gave an extension of the CYK algorithm. His algorithm computes the same parsing table
as the CYK algorithm; yet he showed that [[Matrix multiplication#Algorithms for efficient matrix multiplication|algorithms for efficient multiplication]] of [[Boolean matrix|matrices with 0-1-entries]] can be utilized for performing this computation.
Using the [[Coppersmith–Winograd algorithm]] for multiplying these matrices, this gives an asymptotic worst-case running time of <math>O(n^{2.38} \cdot |G|)</math>. However, the constant term hidden by the [[Big O Notation]] is so large that the Coppersmith–Winograd algorithm is only worthwhile for matrices that are too large to handle on present-day computers {{harv|Knuth|1997}}, and this approach requires subtraction and so is only suitable for recognition. The dependence on efficient matrix multiplication cannot be avoided altogether: {{harvtxt|Lee|2002}} has proved that any parser for context-free grammars working in time <math>O(n^{3-\varepsilon} \cdot |G|)</math> can be effectively converted into an algorithm computing the product of <math>(n \times n)</math>-matrices with 0-1-entries in time <math>O(n^{3 - \varepsilon/3})</math>.
Line 102 ⟶ 103:
==References==
{{Reflist}}
*
*
* {{citation | first = Daniel H. | last = Younger
* {{citation |last=Knuth |first=Donald E. |authorlink=Donald E. Knuth |title=The Art of Computer Programming Volume 2: Seminumerical Algorithms |publisher=Addison-Wesley Professional |edition=3rd |date=November 14, 1997 |isbn=978-0-201-89684-8 |pages=501 }}
* {{Citation
Line 116 ⟶ 117:
| volume=8
| url=http://www.informatica-didactica.de/cmsmadesimple/index.php?page=LangeLeiss2009
}}
*{{Citation
Line 141:
}}
*{{citation |last=Valiant |first=Leslie G. |authorlink=Leslie G. Valiant |title=General context-free recognition in less than cubic time |journal=Journal of Computer and System Sciences |volume=10 |issue=2 |year=1975 |pages=308–314 }}
*{{citation |last=Lang|first=Bernard|title=Recognition can be harder than parsing|journal=Computational Intelligence|
==External links==
| |||