Editing Context-free grammar (section)

== Background ==

Since at least the time of the ancient Indian scholar [[Pāṇini]], linguists have described the [[grammar]]s of languages in terms of their block structure, and described how sentences are [[recursion|recursively]] built up from smaller phrases, and eventually individual words or word elements. An essential property of these block structures is that logical units never overlap. For example, the sentence:
: John, whose blue car was in the garage, walked to the grocery store.
can be logically parenthesized (with the logical metasymbols '''[ ]''') as follows:
: '''['''John'''[''', '''['''whose '''['''blue car''']]''' '''['''was '''['''in '''['''the garage''']]]''',''']]''' '''['''walked '''['''to '''['''the '''['''grocery store''']]]]'''.
A context-free grammar provides a simple and mathematically precise mechanism for describing the methods by which phrases in some natural language are built from smaller blocks, capturing the "block structure" of sentences in a natural way. Its simplicity makes the formalism amenable to rigorous mathematical study. Important features of natural language syntax such as [[agreement (linguistics)|agreement]] and [[reference]] are not part of the context-free grammar, but the basic recursive structure of sentences, the way in which clauses nest inside other clauses, and the way in which lists of adjectives and adverbs are swallowed by nouns and verbs, is described exactly.

Context-free grammars are a special form of [[semi-Thue system]]s that in their general form date back to the work of [[Axel Thue]].

The formalism of context-free grammars was developed in the mid-1950s by [[Noam Chomsky]],{{sfn|Hopcroft|Ullman|1979|p=106}} and also their [[Chomsky hierarchy|classification as a special type]] of [[formal grammar]] (which he called [[phrase-structure grammar]]s).<ref name="chomsky1956">
{{citation
 | last = Chomsky | first = Noam 
 | title = Three models for the description of language
 | journal = IEEE Transactions on Information Theory
 | volume = 2 | issue = 3 | pages = 113–124
 | date = Sep 1956
 | doi = 10.1109/TIT.1956.1056813| s2cid = 19519474 
}}</ref> Some authors, however, reserve the term for more restricted grammars in the Chomsky hierarchy: context-sensitive grammars or context-free grammars. In a broader sense, [[phrase structure grammar]]s are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of [[dependency grammar]]s. In Chomsky's [[generative grammar]] framework, the syntax of natural language was described by context-free rules combined with transformation rules.<ref>{{Cite web |last1=Jurafsky |first1=Daniel |last2=Martin |first2=James H. |date=29 December 2021 |title=Constituency Grammars |url=https://web.stanford.edu/~jurafsky/slp3/12.pdf |archive-url=https://web.archive.org/web/20170314005849/http://web.stanford.edu/~jurafsky/slp3/12.pdf |archive-date=2017-03-14 |url-status=live |access-date=28 October 2022 |website=Stanford University}}</ref>

Block structure was introduced into computer [[programming language]]s by the [[Algol (programming language)|Algol]] project (1957–1960), which, as a consequence, also featured a context-free grammar<ref name="Backus.1969">
{{cite book
 | last = Backus
 | first = J. W.
 | author-link = John W. Backus
 | year = 1959
 | contribution = The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference
 | contribution-url = http://www.softwarepreservation.org/projects/ALGOL/paper/Backus-Syntax_and_Semantics_of_Proposed_IAL.pdf/view
 | title = Proceedings of the International Conference on Information Processing
 | publisher = UNESCO
 | pages = 125–132
}}</ref> to describe the resulting Algol syntax. This became a standard feature of computer languages, and the notation for grammars used in concrete descriptions of computer languages came to be known as [[Backus–Naur form]], after two members of the Algol language design committee.{{sfn|Hopcroft|Ullman|1979|p=106}} The "block structure" aspect that context-free grammars capture is so fundamental to grammar that the terms syntax and grammar are often identified with context-free grammar rules, especially in computer science. Formal constraints not captured by the grammar are then considered to be part of the "semantics" of the language.

Context-free grammars are simple enough to allow the construction of efficient [[list of algorithms#Parsing|parsing algorithm]]s that, for a given string, determine whether and how it can be generated from the grammar. An [[Earley parser]] is an example of such an algorithm, while the widely used [[LR parser|LR]] and [[LL parser]]s are simpler algorithms that deal only with more restrictive subsets of context-free grammars.