Editing Context-free language (section)

===Context-free parsing===
{{main|Parsing}}

The context-free nature of the language makes it simple to parse with a pushdown automaton.

Determining an instance of the [[membership problem]]; i.e. given a string <math>w</math>, determine whether <math>w \in L(G)</math> where <math>L</math> is the language generated by a given grammar <math>G</math>; is also known as ''recognition''. Context-free recognition for [[Chomsky normal form]] grammars was shown by [[Leslie Valiant|Leslie G. Valiant]] to be reducible to Boolean [[matrix multiplication]], thus inheriting its complexity upper bound of [[Big O notation|''O'']](''n''<sup>2.3728596</sup>).<ref>{{cite journal |first=Leslie G. |last=Valiant |title=General context-free recognition in less than cubic time |journal=Journal of Computer and System Sciences |date=April 1975 |volume=10 |number=2 |pages=308–315 |doi=10.1016/s0022-0000(75)80046-8 |doi-access=free |url=https://figshare.com/articles/journal_contribution/General_context-free_recognition_in_less_than_cubic_time/6605915/1/files/12096398.pdf }}</ref><ref group=note>In Valiant's paper, ''O''(''n''<sup>2.81</sup>) was the then-best known upper bound. See [[Matrix multiplication#Computational complexity]] for bound improvements since then.</ref>
Conversely, [[Lillian Lee (computer scientist)|Lillian Lee]] has shown ''O''(''n''<sup>3−ε</sup>) Boolean matrix multiplication to be reducible to ''O''(''n''<sup>3−3ε</sup>) CFG parsing, thus establishing some kind of lower bound for the latter.<ref>{{cite journal |first=Lillian |last=Lee |author-link=Lillian Lee (computer scientist) |title=Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication |journal=J ACM |date=January 2002 |volume=49 |number=1 |pages=1–15 |url=http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf |archive-url=https://web.archive.org/web/20030427152836/http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf |archive-date=2003-04-27 |url-status=live |doi=10.1145/505241.505242 |arxiv=cs/0112018|s2cid=1243491 }}</ref>

Practical uses of context-free languages require also to produce a derivation tree that exhibits the  structure that the grammar associates with the given string. The process of producing this tree is called ''[[parsing]]''. Known parsers have a time complexity that is cubic in the size of the string that is parsed.

Formally, the set of all context-free languages is identical to the set of languages accepted by pushdown automata (PDA). Parser algorithms for context-free languages include the [[CYK algorithm]] and [[Earley parser|Earley's Algorithm]].

A special subclass of context-free languages are the [[deterministic context-free language]]s which are defined as the set of languages accepted by a [[deterministic pushdown automaton]] and can be parsed by a [[LR parser|LR(k) parser]].<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | author-link = Donald Knuth | title = On the translation of languages from left to right | doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | doi-access =  }}</ref>

See also [[parsing expression grammar]] as an alternative approach to grammar and parser.