Parsing Complexity

[User's Manual]
[Code]
All textbook bottom-up Prolog parsers copy edges out of the chart once for every attempt to match an edge to a daughter category. Carpenter's algorithm--which traverses the string breadth-first, right-to-left and matches rule daughters rule depth-first left-to-right in a failure-driven loop--can in the worst case make $\mathcal{O}(n^{b-1})$ copies, where $b$ is the maximum rule branching factor. The worst-case time complexity of Carpenter's algorithm is $\mathcal{O}(n^{b+1})$. A fixed CFG based on atomic categories can be converted off-line to Chomsky Normal Form in which $b=2$, thus resulting in the cubic-time recognition, $\mathcal{O}(n^3)$. The EFD-closure algorithm, as mentioned in the beginning of this chapter, reduces the number of copying to 2 per non-empty edge. Like Carpenter's algorithm, however, its worst-case time complexity is $\mathcal{O}(n^{b+1})$.