Editing Top-down parsing (section)

== Time and space complexity of top-down parsing ==
When top-down parser tries to parse an ambiguous input with respect to an ambiguous CFG, it may need exponential number of steps (with respect to the length of the input) to try all alternatives of the CFG in order to produce all possible parse trees, which eventually would require exponential memory space. The problem of exponential time complexity in top-down parsers constructed as sets of mutually recursive functions has been solved by [[Peter Norvig|Norvig]] in 1991.<ref name=" Norvig 1991">Norvig, P. (1991) “[https://aclanthology.info/pdf/J/J91/J91-1004.pdf Techniques for automatic memoisation with applications to context-free parsing].” ''Journal - Computational Linguistics'' Volume 17, Issue 1, Pages: 91 - 98.</ref> His technique is similar to the use of dynamic programming and state-sets in [[Earley parser|Earley's algorithm]] (1970), and tables in the [[CYK algorithm]] of Cocke, Younger and Kasami.

The key idea is to store results of applying a parser <code>p</code> at position <code>j</code> in a memorable and to reuse results whenever the same situation arises. Frost, Hafiz and Callaghan<ref name="FrostHafizCallaghan 2007"/><ref name="FrostHafizCallaghan 2008"/> also use [[memoization]] for refraining redundant computations to accommodate any form of CFG in [[polynomial]] time ([[Big O notation|Θ]](n<sup>4</sup>) for left-recursive grammars and [[Big O notation|Θ]](n<sup>3</sup>) for non left-recursive grammars). Their top-down parsing algorithm also requires polynomial space for potentially exponential ambiguous parse trees by 'compact representation' and 'local ambiguities grouping'. Their compact representation is comparable with [[Masaru Tomita|Tomita]]'s compact representation of [[bottom-up parsing]].<ref name=" Tomita1985">Tomita, M. (1985) “[https://books.google.com/books?id=DAjkBwAAQBAJ Efficient Parsing for Natural Language].” ''Kluwer, Boston, MA''.</ref>

Using PEG's, another representation of grammars, packrat parsers provide an elegant and powerful parsing algorithm. See [[Parsing expression grammar]].