Editing Context-free grammar

{{Short description|Type of formal grammar}}
{{Use American English|date=January 2019}}
{{CS1 config|mode=cs1}}
{{more citations needed|date=February 2012}}
[[File:C grammar stmt2 svg.svg|thumb|250px|Simplified excerpt of the formal grammar<ref>{{cite book | isbn=0131103628 | author=Brian W. Kernighan and Dennis M. Ritchie | title=The C Programming Language | edition=2nd | location=Englewood Cliffs/NJ | publisher=Prentice Hall | series=Prentice Hall Software Series | date=Apr 1988 |chapter=Appendix A}}</ref> for the [[C (programming language)|C programming language]] (left), and a derivation of a piece of C code (right) from the nonterminal symbol <math>\langle\text{Stmt}\rangle</math>. Nonterminal symbols are blue and terminal symbols are red.]]
In [[formal language]] theory, a '''context-free grammar''' ('''CFG''') is a [[formal grammar]] whose [[Production (computer science)|production rules]] 
can be applied to a [[Terminal and nonterminal symbols|nonterminal symbol]] regardless of its context.
In particular, in a context-free grammar, each production rule is of the form
: <math>A\ \to\ \alpha</math>
with <math>A</math> a ''single'' nonterminal symbol, and <math>\alpha</math> a string of terminals and/or nonterminals (<math>\alpha</math> can be empty). Regardless of which symbols surround it, the single nonterminal <math>A</math> on the left hand side can always be replaced by <math>\alpha</math> on the right hand side. This  distinguishes it from a [[context-sensitive grammar]], which can have production rules in the form <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math> with <math>A</math> a nonterminal symbol and <math>\alpha</math>, <math>\beta</math>, and <math>\gamma</math> strings of terminal and/or nonterminal symbols.

A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture,
: <math>\langle\text{Stmt}\rangle \to \langle\text{Id}\rangle = \langle\text{Expr}\rangle ;</math>
replaces <math>\langle\text{Stmt}\rangle</math> with <math>\langle\text{Id}\rangle = \langle\text{Expr}\rangle ;</math>. There can be multiple replacement rules for a given nonterminal symbol. The language generated by a grammar is the set of all strings of terminal symbols that can be derived, by repeated rule applications, from some particular nonterminal symbol ("start symbol").
Nonterminal symbols are used during the derivation process, but do not appear in its final result string.

[[formal language|Language]]s generated by context-free grammars are known as [[context-free language]]s (CFL). Different context-free grammars can generate the same context-free language. It is important to distinguish the properties of the language (intrinsic properties) from the properties of a particular grammar (extrinsic properties). The [[#Language equality|language equality]] question (do two given context-free grammars generate the same language?) is [[Decidability (logic)|undecidable]].

Context-free grammars arise in [[linguistics]] where they are used to describe the structure of sentences and words in a [[natural language]], and they were invented by the linguist [[Noam Chomsky]] for this purpose. By contrast, in [[computer science]], as the use of recursively-defined concepts increased, they were used more and more. In an early application, grammars are used to describe the structure of [[programming language]]s. In a newer application, they are used in an essential part of the [[Extensible Markup Language]] (XML) called the [[document type definition]].{{sfn|Hopcroft|Motwani|Ullman|2006|p=191}}

In linguistics, some authors use the term [[phrase structure grammar]] to refer to context-free grammars, whereby phrase-structure grammars are distinct from [[dependency grammar]]s. In computer science, a popular notation for context-free grammars is [[Backus–Naur form]], or BNF.

== 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.

== Formal definitions ==
A context-free grammar {{mvar|G}} is defined by the 4-[[tuple]] <math>G = (V, \Sigma, R, S)</math>, 
where{{efn|The notation here is that of {{harvtxt|Sipser|1997|p=94}}. {{harvtxt|Hopcroft|Ullman|1979|p=79}} define context-free grammars as 4-tuples in the same way, but with different variable names.}}
# {{mvar|V}} is a finite set; each element <math> v\in V</math> is called ''a nonterminal character'' or a ''variable''. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories. Each variable defines a sub-language of the language defined by {{mvar|G}}.
# {{math|Σ}} is a finite set of ''terminal''s, disjoint from {{mvar|V}}, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar {{mvar|G}}.
# {{mvar|R}} is a finite [[Binary relation|relation]] in <math>V\times(V\cup\Sigma)^{*}</math>, where the asterisk represents the [[Kleene star]] operation. The members of {{mvar|R}} are called the ''(rewrite) rule''s or ''production''s of the grammar. (also commonly symbolized by a {{mvar|P}})
# {{mvar|S}} is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of {{mvar|V}}.

=== Production rule notation ===
A [[Formal grammar#The syntax of grammars|production rule]] in {{mvar|R}} is formalized mathematically as a pair <math>(\alpha, \beta)\in R</math>, where <math>\alpha \in V</math> is a nonterminal and <math>\beta \in (V\cup\Sigma)^{*}</math> is a [[string (computer science)|string]] of variables and/or terminals; rather than using [[ordered pair]] notation, production rules are usually written using an arrow operator with <math>\alpha</math> as its left hand side and {{math|''β''}} as its right hand side:
<math>\alpha\rightarrow\beta</math>.

It is allowed for {{math|''β''}} to be the [[empty string]], and in this case it is customary to denote it by {{math|ε}}. The form <math>\alpha\rightarrow\varepsilon</math> is called an ε-production.{{sfn|Hopcroft|Ullman|1979|pp=90–92}}

It is common to list all right-hand sides for the same left-hand side on the same line, using | (the [[vertical bar]]) to separate them. Rules <math>\alpha\rightarrow \beta_1</math> and <math>\alpha\rightarrow\beta_2</math> can hence be written as <math>\alpha\rightarrow\beta_1\mid\beta_2</math>. In this case, <math>\beta_1</math> and <math>\beta_2</math> are called the first and second alternative, respectively.

=== Rule application ===
For any strings <math>u, v\in (V\cup\Sigma)^{*}</math>, we say {{mvar|u}} directly yields {{mvar|v}}, written as <math>u\Rightarrow v\,</math>, if <math>\exists (\alpha, \beta)\in R</math> with <math>\alpha \in V</math> and <math>u_{1}, u_{2}\in (V\cup\Sigma)^{*}</math> such that <math>u\,=u_{1}\alpha u_{2}</math> and <math>v\,=u_{1}\beta u_{2}</math>. Thus, {{mvar|v}} is a result of applying the rule <math>(\alpha, \beta)</math> to {{math|''u''}}.

=== Repetitive rule application ===
For any strings <math>u, v\in (V\cup\Sigma)^{*}, </math> we say {{mvar|u}} ''yields'' {{mvar|v}} or {{mvar|v}} is ''derived'' from {{mvar|u}} if there is a positive integer {{mvar|k}} and strings <math>u_{1}, \ldots, u_{k}\in (V\cup\Sigma)^{*}</math> such that <math>u = u_{1} \Rightarrow u_{2} \Rightarrow \cdots \Rightarrow u_{k} = v</math>.  This relation is denoted <math>u ~\stackrel{*}{\Rightarrow}~ v</math>, or <math>u\Rightarrow\Rightarrow v</math> in some textbooks.  If <math>k\geq 2</math>, the relation <math>u ~\stackrel{+}{\Rightarrow}~ v</math> holds. In other words, <math>(\stackrel{*}{\Rightarrow})</math> and <math>(\stackrel{+}{\Rightarrow})</math> are the [[reflexive transitive closure]] (allowing a string to yield itself) and the [[transitive closure]] (requiring at least one step) of <math>(\Rightarrow)</math>, respectively.

=== Context-free language ===
The language of a grammar <math>G = (V, \Sigma, R, S)</math> is the set
: <math>L(G) = \{ w\in\Sigma^{*} : S ~\stackrel{*}{\Rightarrow}~ w\}</math>
of all terminal-symbol strings derivable from the start symbol.

A language {{mvar|L}} is said to be a context-free language (CFL), if there exists a CFG {{mvar|G}}, such that <math>L=L(G)</math>.

[[Pushdown automaton#PDA and context-free languages|Non-deterministic pushdown automata]] recognize exactly the context-free languages.

== Examples ==

{{more citations needed section|date=July 2018}}

=== Words concatenated with their reverse ===

The grammar <math>G = (\{S\}, \{\mathrm{a}, \mathrm{b}\}, P, S)</math>, with productions
: {{math|''S'' → a''S''a}},
: {{math|''S'' → b''S''b}},
: {{math|''S'' → ε}},
is context-free. It is not proper since it includes an {{math|ε}}-production. A typical derivation in this grammar is
: {{math|''S'' → a''S''a → aa''S''aa → aab''S''baa → aabbaa}}.
This makes it clear that <math>L(G) = \{ww^R:w\in\{a,b\}^*\}</math>. 
The language is context-free; however, it can be proved that it is not [[Regular language|regular]].

If the productions
: {{math|''S'' → a}},
: {{math|''S'' → b}},
are added, a context-free grammar for the set of all [[palindrome]]s over the alphabet {{math|{{mset|a, b}}}} is obtained.{{sfn|Hopcroft|Ullman|1979|loc=Exercise 4.1a| p=103}}

=== Well-formed parentheses ===
The canonical example of a context-free grammar is parenthesis matching, which is representative of the general case. There are two terminal symbols {{math|(}} and {{math|)}} and one nonterminal symbol {{math|''S''}}. The production rules are
: {{math|''S'' → ''SS''}},
: {{math|''S'' → (''S'')}},
: {{math|''S'' → ()}}

The first rule allows the {{math|''S''}} symbol to multiply; the second rule allows the {{math|''S''}} symbol to become enclosed by matching parentheses; and the third rule terminates the recursion.{{sfn|Hopcroft|Ullman|1979|loc=Exercise 4.1b|p=103}}

=== Well-formed nested parentheses and square brackets ===

A second canonical example is two different kinds of matching nested parentheses, described by the productions:
: {{math|''S'' → ''SS''}}
: {{math|''S'' → ()}}
: {{math|''S'' → (''S'')}}
: {{math|''S'' → []}}
: {{math|''S'' → [''S'']}}
with terminal symbols {{math|[}}, {{math|]}}, {{math|(}}, {{math|)}} and nonterminal {{math|''S''}}.

The following sequence can be derived in that grammar:
: {{math|([ [ [ ()() [ ][ ] ] ]([ ]) ])}}

=== Matching pairs ===
In a context-free grammar, we can pair up characters the way we do with [[bracket]]s. The simplest example:
: {{math|''S'' → a''Sb''}}
: {{math|''S'' → ab}}

This grammar generates the language {{math|{{mset|a<sup>''n''</sup>b<sup>''n''</sup> : ''n'' ≥ 1}}}}, which is not [[regular language|regular]] (according to the [[pumping lemma for regular languages]]).

The special character {{math|ε}} stands for the empty string. By changing the above grammar to
: {{math|''S'' → a''S''b}}
: {{math|''S'' → ε}}
we obtain a grammar generating the language {{math|{{mset|a<sup>''n''</sup>b<sup>''n''</sup> : ''n'' ≥ 0}}}} instead. This differs only in that it contains the empty string while the original grammar did not.

=== Distinct number of as and bs ===

A context-free grammar for the language consisting of all strings over {{mset|a, b}} containing an unequal number of {{math|a}}s and {{math|b}}s:
: {{math|''S'' → ''T'' {{pipe}} ''U''}}
: {{math|''T'' → ''V''a''T'' {{pipe}} ''V''a''V'' {{pipe}} ''T''a''V''}}
: {{math|''U'' → ''V''b''U'' {{pipe}} ''V''b''V'' {{pipe}} ''U''b''V''}}
: {{math|''V'' → a''V''b''V'' {{pipe}} b''V''a''V'' {{pipe}} ε}}
Here, the nonterminal {{math|''T''}} can generate all strings with more as than {{math|b}}s, the nonterminal {{math|''U''}} generates all strings with more {{math|b}}s than {{math|a}}s and the nonterminal {{math|''V''}} generates all strings with an equal number of {{math|a}}s and {{math|b}}s. Omitting the third alternative in the rules for {{math|''T''}} and {{math|''U''}} does not restrict the grammar's language.

=== Second block of bs of double size ===

Another example of a non-regular language is <math> \{ \text{b}^n \text{a}^m \text{b}^{2n} : n \ge 0, m \ge 0 \} </math>. It is context-free as it can be generated by the following context-free grammar:
: {{math|''S'' → b''S''bb {{!}} ''A''}}
: {{math|''A'' → a''A'' {{!}} ε}}

=== First-order logic formulas ===

The [[First-order logic#Formation rules|formation rules]] for the terms and formulas of formal logic fit the definition of context-free grammar, except that the set of symbols may be infinite and there may be more than one start symbol.

== Examples of languages that are not context free ==

In contrast to well-formed nested parentheses and square brackets in the previous section, there is no context-free grammar for generating all sequences of two different types of parentheses, each separately balanced ''disregarding the other'', where the two types need not nest inside one another, for example:
: {{math|[ ( ] )}}
or
: {{math|[ [ [ [(((( ] ] ] ]))))(([ ))(([ ))([ )( ])( ])( ])}}

The fact that this language is not context free can be proven using [[pumping lemma for context-free languages]] and a proof by contradiction, observing that all words of the form <math>{(}^n {[}^n {)}^n {]}^n</math> should belong to the language. This language belongs instead to a more general class and can be described by a [[conjunctive grammar]], which in turn also includes other non-context-free languages, such as the language of all words of the form {{math|a<sup>''n''</sup>b<sup>''n''</sup>c<sup>''n''</sup>}}.

== Regular grammars ==
{{main|Regular grammar}}
Every [[regular grammar]] is context-free, but not all context-free grammars are regular.<ref>{{cite book |last1=Aho |first1=Alfred Vaino |last2=Lam |first2=Monica S. |last3=Sethi |first3=Ravi |last4=Ullman |first4=Jeffrey David |author-link1=Alfred Aho |author-link2=Monica S. Lam |author-link3=Ravi Sethi |author-link4=Jeffrey Ullman |title=Compilers: Principles, Techniques, & Tools |date=2007 |publisher=Pearson Addison-Wesley |location=Boston, MA USA |isbn=9780321486813 |pages=[https://archive.org/details/compilers00alfr_0/page/205 205–206] |edition=2nd |chapter-url=https://www.pearson.com/us/higher-education/program/Aho-Compilers-Principles-Techniques-and-Tools-2nd-Edition/PGM167067.html |language=en |chapter-format=print |chapter=4.2.7 Context-Free Grammars Versus Regular Expressions |quote=Every construct that can be described by a regular expression can be described by a [context-free] grammar, but not vice-versa. |url=https://archive.org/details/compilers00alfr_0/page/205 }}</ref> The following context-free grammar, for example, is also regular.
: {{math|''S'' → a}}
: {{math|''S'' → a''S''}}
: {{math|''S'' → b''S''}}

The terminals here are {{math|a}} and {{math|b}}, while the only nonterminal is {{math|''S''}}.
The language described is all nonempty strings of {{math|a}}s and {{math|b}}s that end in {{math|a}}.

This grammar is [[regular grammar|regular]]: no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.

Every regular grammar corresponds directly to a [[nondeterministic finite automaton]], so we know that this is a [[regular language]].

Using vertical bars, the grammar above can be described more tersely as follows:
: {{math|''S'' → a {{!}} a''S'' {{!}} b''S''}}

== Derivations and syntax trees ==
<!-- This section is linked from [[LR parser]] -->

A ''derivation'' of a string for a grammar is a sequence of grammar rule applications that transform the start symbol into the string.
A derivation proves that the string belongs to the grammar's language.

A derivation is fully determined by giving, for each step:
* the rule applied in that step
* the occurrence of its left-hand side to which it is applied
For clarity, the intermediate string is usually given as well.

For instance, with the grammar:
# {{math|''S'' → ''S'' + ''S''}}
# {{math|''S'' → 1}}
# {{math|''S'' → a}}
the string
: {{math|1 + 1 + a}}
can be derived from the start symbol {{math|''S''}} with the following derivation:
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1. on {{math|''S''}})
: {{math|→ ''S'' + ''S'' + ''S''}} (by rule 1. on the second {{math|''S''}})
: {{math|→ 1 + ''S'' + ''S''}} (by rule 2. on the first {{math|''S''}})
: {{math|→ 1 + 1 + ''S''}} (by rule 2. on the second {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 3. on the third {{math|''S''}})

Often, a strategy is followed that deterministically chooses the next nonterminal to rewrite:
* in a ''leftmost derivation'', it is always the leftmost nonterminal;
* in a ''rightmost derivation'', it is always the rightmost nonterminal.

Given such a strategy, a derivation is completely determined by the sequence of rules applied. For instance, one leftmost derivation of the same string is
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1 on the leftmost {{math|''S''}})
: {{math|→ 1 + ''S''}} (by rule 2 on the leftmost {{math|''S''}})
: {{math|→ 1 + ''S'' + ''S''}} (by rule 1 on the leftmost {{math|''S''}})
: {{math|→ 1 + 1 + ''S''}} (by rule 2 on the leftmost {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 3 on the leftmost {{math|''S''}}),
which can be summarized as
: rule 1
: rule 2
: rule 1
: rule 2
: rule 3.

One rightmost derivation is:
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + ''S'' + ''S''}} (by rule 1 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + ''S'' + a}} (by rule 3 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + 1 + a}} (by rule 2 on the rightmost {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 2 on the rightmost {{math|''S''}}),
which can be summarized as
: rule 1
: rule 1
: rule 3
: rule 2
: rule 2.

The distinction between leftmost derivation and rightmost derivation is important because in most [[parsing|parser]]s the transformation of the input is defined by giving a piece of code for every grammar rule that is executed whenever the rule is applied. Therefore, it is important to know whether the parser determines a leftmost or a rightmost derivation because this determines the order in which the pieces of code will be executed. See for an example [[LL parser]]s and [[LR parser]]s.

A derivation also imposes in some sense a hierarchical structure on the string that is derived. For example, if the string "{{math|1 + 1 + a}}" is derived according to the leftmost derivation outlined above, the structure of the string would be:
: {{math|{{mset|{{mset|1}}<sub>''S''</sub> + {{mset|{{mset|1}}<sub>''S''</sub> + {{mset|a}}<sub>''S''</sub>}}<sub>''S''</sub>}}<sub>''S''</sub>}}
where {{math|{{mset|...}}<sub>''S''</sub>}} denotes a substring recognized as belonging to {{math|''S''}}. This hierarchy can also be seen as a tree:

[[File:Simple Parse Tree 1.svg|x260px|Rightmost derivation of {{math|1 + 1 + a}}]]

This tree is called a ''[[parse tree]]'' or "concrete syntax tree" of the string, by contrast with the [[abstract syntax tree]]. In this case the presented leftmost and the rightmost derivations define the same parse tree; however, there is another rightmost derivation of the same string
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + a}} (by rule 3 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + ''S'' + a}} (by rule 1 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + 1 + a}} (by rule 2 on the rightmost {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 2 on the rightmost {{math|''S''}}),
which defines a string with a different structure
: {{math|{{mset|{{mset|{{mset|1}}<sub>''S''</sub> + {{mset|1}}<sub>''S''</sub>}}<sub>''S''</sub> + {{mset|a}}<sub>''S''</sub>}}<sub>''S''</sub>}}
and a different parse tree:

[[File:Simple Parse Tree 2.svg|x260px|Leftmost derivation of {{math|1 + 1 + a}}]]

Note however that both parse trees can be obtained by both leftmost and rightmost derivations.  For example, the last tree can be obtained with the leftmost derivation as follows:
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1 on the leftmost {{math|''S''}})
: {{math|→ ''S'' + ''S'' + ''S''}} (by rule 1 on the leftmost {{math|''S''}})
: {{math|→ 1 + ''S'' + ''S''}} (by rule 2 on the leftmost {{math|''S''}})
: {{math|→ 1 + 1 + ''S''}} (by rule 2 on the leftmost {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 3 on the leftmost {{math|''S''}}),

If a string in the language of the grammar has more than one parsing tree, then the grammar is said to be an ''[[ambiguous grammar]]''. Such grammars are usually hard to parse because the parser cannot always decide which grammar rule it has to apply. Usually, ambiguity is a feature of the grammar, not the language, and an unambiguous grammar can be found that generates the same context-free language. However, there are certain languages that can only be generated by ambiguous grammars; such languages are called ''[[inherently ambiguous language]]s''.

== Normal forms ==
Every context-free grammar with no {{math|ε}}-production has an equivalent grammar in [[Chomsky normal form]], and a grammar in [[Greibach normal form]]. "Equivalent" here means that the two grammars generate the same language.

The especially simple form of production rules in Chomsky normal form grammars has both theoretical and practical implications. For instance, given a context-free grammar, one can use the Chomsky normal form to construct a [[polynomial-time]] algorithm that decides whether a given string is in the language represented by that grammar or not (the [[CYK algorithm]]).

== Closure properties ==
Context-free languages are [[Closure (mathematics)|closed]] under the various operations, that is, if the languages {{math|''K''}} and {{math|''L''}} are 
context-free, so is the result of the following operations:
* [[set union|union]] {{math|''K'' ∪ ''L''}}; [[string concatenation#Concatenation of sets of strings|concatenation]] {{math|''K'' ∘ ''L''}}; [[Kleene star]] ''L''<sup>*</sup>{{sfn|Hopcroft|Ullman|1979|p=131}}
* [[string substitution|substitution]] (in particular [[string homomorphism|homomorphism]]){{sfn|Hopcroft|Ullman|1979|p=131-132|loc=Theorem 6.2}}
* [[string homomorphism|inverse homomorphism]]{{sfn|Hopcroft|Ullman|1979|p=132-134|loc=Theorem 6.3}}
* [[set intersection|intersection]] with a [[regular language]]{{sfn|Hopcroft|Ullman|1979|p=135-136|loc=Theorem 6.5}}

They are not closed under general intersection (hence neither under [[set complement|complementation]]) and set difference.{{sfn|Hopcroft|Ullman|1979|p=134-135|loc=Theorem 6.4}}

== Decidable problems ==

The following are some decidable problems about context-free grammars.

=== Parsing ===

The parsing problem, checking whether a given word belongs to the language given by a context-free grammar, is decidable, using one of the general-purpose parsing algorithms:
* [[CYK algorithm]] (for grammars in [[Chomsky normal form]])
* [[Earley parser]]
* [[GLR parser]]
* [[LL parser]] (only for the proper subclass of LL(''k'') grammars)
Context-free parsing 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.3728639</sup>).<ref>{{cite tech report| author=Leslie Valiant| title=General context-free recognition in less than cubic time|date=Jan 1974| pages=11| institution=Carnegie Mellon University| url=http://repository.cmu.edu/cgi/viewcontent.cgi?article=2751&context=compsci}}</ref><ref>{{cite journal| author=Leslie G. Valiant| title=General context-free recognition in less than cubic time| journal=Journal of Computer and System Sciences| year=1975| volume=10| number=2| pages=308–315| doi=10.1016/s0022-0000(75)80046-8| doi-access=free}}</ref>{{efn|In Valiant's papers, ''O''(''n''<sup>2.81</sup>) is given, the then best known upper bound. See [[Matrix multiplication#Computational complexity]] for bound improvements since then.}} 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| author=Lillian Lee|author-link=Lillian Lee (computer scientist)|title=Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication| journal=J ACM| year=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>

=== Reachability, productiveness, nullability ===

{| style="border: 1px solid grey; float: right; margin: 1em 1em;"
!- COLSPAN=4 | Example grammar:
|-
| | ''S'' → ''B''b | ''C''c | ''E''e
|-
| | ''B'' → ''B''b | b
|-
| | ''C'' → ''C''
|-
| | ''D'' → ''B''d | ''C''d | d
|-
| | ''E'' → ''E''e
|}

A nonterminal symbol <math>X</math> is called ''productive'', or ''generating'', if there is a derivation <math>X ~\stackrel{*}{\Rightarrow}~ w</math> for some string <math>w</math> of terminal symbols. <math>X</math> is called ''reachable'' if there is a derivation <math>S ~\stackrel{*}{\Rightarrow}~ \alpha X \beta</math> for some strings <math>\alpha,\beta</math> of nonterminal and terminal symbols from the start symbol. <math>X</math> is called ''useless'' if it is unreachable or unproductive. <math>X</math> is called ''nullable'' if there is a derivation <math>X ~\stackrel{*}{\Rightarrow}~ \varepsilon</math>. A rule <math>X \rightarrow \varepsilon</math> is called an ''ε-production''. A derivation <math>X ~\stackrel{+}{\Rightarrow}~ X</math> is called a ''cycle''.

Algorithms are known to eliminate from a given grammar, without changing its generated language,
* unproductive symbols,{{sfn|Hopcroft|Ullman|1979|loc=Lemma 4.1|p=88}}{{efn|For [[regular tree grammar]]s, Aiken and Murphy give a fixpoint algorithm to detect unproductive nonterminals.<ref>{{cite conference|first1=A.|last1=Aiken|first2=B.|last2=Murphy|title=Implementing Regular Tree Expressions|book-title=ACM Conference on Functional Programming Languages and Computer Architecture|pages=427–447|year=1991|citeseerx=10.1.1.39.3766}}; Sect.4</ref>}}
* unreachable symbols,{{sfn|Hopcroft|Ullman|1979|loc=Lemma 4.2|p=89}}{{sfn|Hopcroft|Motwani|Ullman|2006|loc=Theorem 7.2, Section 7.1 |p=255}}
* {{math|ε}}-productions, with one possible exception,{{efn|If the grammar can generate {{math|ε}}, a rule <math>S \rightarrow \varepsilon</math> cannot be avoided.}}{{sfn|Hopcroft|Ullman|1979|loc=Theorem 4.3|p=90}} and
* cycles.{{efn|This is a consequence of the unit-production elimination theorem in {{harvtxt|Hopcroft|Ullman|1979|p=91|loc=Theorem 4.4}}}}.

In particular, an alternative containing a useless nonterminal symbol can be deleted from the right-hand side of a rule.
Such rules and alternatives are called ''useless''.{{sfn|Hopcroft|Motwani|Ullman|2006|p=256|loc=Section 7.1.1}}

In the depicted example grammar, the nonterminal {{math|''D''}} is unreachable, and {{math|''E''}} is unproductive, while {{math|''C'' → ''C''}} causes a cycle.
Hence, omitting the last three rules does not change the language generated by the grammar, nor does omitting the alternatives "{{math|{{!}} ''C''c {{!}} ''E''e}}" from the right-hand side of the rule for {{math|''S''}}.

A context-free grammar is said to be ''proper'' if it has neither useless symbols nor {{math|ε}}-productions nor cycles.<ref>{{citation
 | last = Nijholt | first = Anton
 | isbn = 978-3-540-10245-8
 | mr = 590047
 | page = 8
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Context-free grammars: covers, normal forms, and parsing
 | volume = 93
 | year = 1980
}}</ref> 
Combining the above algorithms, every context-free grammar not generating {{math|ε}} can be transformed into a [[weak equivalence (formal languages)|weakly equivalent]] proper one.

=== Regularity and LL(''k'') checks ===

It is decidable whether a given ''grammar'' is a [[regular grammar]],{{efn|This is easy to see from the grammar definitions.}} as well as whether it is an [[LL grammar|LL(''k'') grammar]] for a given {{math|''k'' ≥ 0}}.<ref name="Rosenkrantz.Stearns.1970">{{cite journal  | author=D.J. Rosenkrantz and R.E. Stearns | title=Properties of Deterministic Top Down Grammars | journal=Information and Control | volume=17 | issue=3 | pages=226&ndash;256 | year=1970 | doi=10.1016/S0019-9958(70)90446-8 | doi-access=free }}</ref>{{rp|233}} If ''k'' is not given, the latter problem is undecidable.<ref name="Rosenkrantz.Stearns.1970"/>{{rp|252}}

Given a context-free grammar, it is not decidable whether its language is regular,<ref>{{harvtxt|Hopcroft|Ullman|1979|loc=Exercise 8.10a|p=214}} The problem remains undecidable even if the language is produced by a "linear" context-free grammar (i.e., with at most one nonterminal in each rule's right-hand side, cf. Exercise 4.20, p.&nbsp;105).</ref> nor whether it is an LL(''k'') language for a given ''k''.<ref name="Rosenkrantz.Stearns.1970"/>{{rp|254}}

=== Emptiness and finiteness ===

There are algorithms to decide whether the language of a given context-free grammar is empty, as well as whether it is finite.{{sfn|Hopcroft|Ullman|1979|p=137-138|loc=Theorem 6.6}}

== Undecidable problems ==
Some questions that are undecidable for wider classes of grammars become decidable for context-free grammars; e.g. the [[emptiness problem]] (whether the grammar generates any terminal strings at all), is undecidable for [[context-sensitive grammar]]s, but decidable for context-free grammars.

However, many problems are [[Undecidable problem|undecidable]] even for context-free grammars; the most prominent ones are handled in the following.

=== Universality ===
Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?{{sfn|Sipser|1997|loc=Theorem 5.10|p=181}}{{sfn|Hopcroft|Ullman|1979|p=281}}

A reduction can be demonstrated to this problem from the well-known undecidable problem of determining whether a [[Turing machine]] accepts a particular input (the [[halting problem]]). The reduction uses the concept of a ''[[computation history]]'', a string describing an entire computation of a [[Turing machine]]. A CFG can be constructed that generates all strings that are not accepting computation histories for a particular Turing machine on a particular input, and thus it will accept all strings only if the machine does not accept that input.

=== Language equality ===
Given two CFGs, do they generate the same language?{{sfn|Hopcroft|Ullman|1979|p=281}}<ref name="eom"/>

The undecidability of this problem is a direct consequence of the previous: it is impossible to even decide whether a CFG is equivalent to the trivial CFG defining the language of all strings.

=== Language inclusion ===
Given two CFGs, can the first one generate all strings that the second one can generate?{{sfn|Hopcroft|Ullman|1979|p=281}}<ref name="eom"/>

If this problem was decidable, then language equality could be decided too: two CFGs <math>G_1</math> and <math>G_2</math> generate the same language if <math>L(G_1)</math> is a subset of <math>L(G_2)</math> and <math>L(G_2)</math> is a subset of <math>L(G_1)</math>.

=== Being in a lower or higher level of the Chomsky hierarchy ===
Using [[Greibach's theorem]], it can be shown that the two following problems are undecidable:
* Given a [[context-sensitive grammar]], does it describe a context-free language?
* Given a context-free grammar, does it describe a [[regular language]]?{{sfn|Hopcroft|Ullman|1979|p=281}}<ref name="eom">{{citation|title=Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia"|first=Michiel|last=Hazewinkel|publisher=Springer|year=1994|isbn=978-1-55608-003-6|at=Vol. IV, p. 56|url=https://books.google.com/books?id=s9F71NJxwzoC&pg=PA56}}.</ref>

=== Grammar ambiguity ===
Given a CFG, is it [[Ambiguous grammar|ambiguous]]?

The undecidability of this problem follows from the fact that if an algorithm to determine ambiguity existed, the [[Post correspondence problem]] could be decided, which is known to be undecidable.{{sfn|Hopcroft|Ullman|1979|loc=Theorem 8.9|pp=200–201}} This may be proved by [[Ogden's lemma#Undecidability|Ogden's lemma]].<ref>{{Cite journal |last=Ogden |first=William |date=September 1968 |title=A helpful result for proving inherent ambiguity |url=http://dx.doi.org/10.1007/bf01694004 |journal=Mathematical Systems Theory |volume=2 |issue=3 |pages=191–194 |doi=10.1007/bf01694004 |s2cid=13197551 |issn=0025-5661}}  Here: p.4</ref>

=== Language disjointness ===
Given two CFGs, is there any string derivable from both grammars?

If this problem was decidable, the undecidable [[Post correspondence problem]] (PCP) could be decided, too: given strings <math>\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N</math> over some alphabet <math>\{a_1, \ldots, a_k\}</math>, let the grammar {{tmath|G_1}} consist of the rule
:<math>S \to \alpha_1 S \beta_1^{rev} | \cdots | \alpha_N S \beta_N^{rev} | b</math>;
where <math>\beta_i^{rev}</math> denotes the [[String (computer science)#Reversal|reversed]] string <math>\beta_i</math> and <math>b</math> does not occur among the <math>a_i</math>; and let grammar {{tmath|G_2}} consist of  the rule
:<math>T \to a_1 T a_1^{rev} | \cdots | a_k T a_k^{rev} | b</math>;
Then the PCP instance given by <math>\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N</math> has a solution if and only if {{tmath|L(G_1)}} and {{tmath|L(G_2)}} share a derivable string. The left of the string (before the <math> b </math>) will represent the top of the solution for the PCP instance while the right side will be the bottom in reverse.

== Extensions ==
An obvious way to extend the context-free grammar formalism is to allow nonterminals to have arguments, the values of which are passed along within the rules. This allows natural language features such as [[Agreement (linguistics)|agreement]] and [[reference]], and programming language analogs such as the correct use and definition of identifiers, to be expressed in a natural way. E.g. we can now easily express that in English sentences, the subject and verb must agree in number. In computer science, examples of this approach include [[affix grammar]]s, [[attribute grammar]]s, [[indexed grammar]]s, and Van Wijngaarden [[two-level grammar]]s. Similar extensions exist in linguistics.

An '''extended context-free grammar''' (or '''regular right part grammar''') is one in which the right-hand side of the production rules is allowed to be a [[regular expression]] over the grammar's terminals and nonterminals. Extended context-free grammars describe exactly the context-free languages.<ref>{{cite web | url=http://www.engr.mun.ca/~theo/Courses/fm/pub/context-free.pdf |archive-url=https://web.archive.org/web/20050324113326/http://www.engr.mun.ca/~theo/Courses/fm/pub/context-free.pdf |archive-date=2005-03-24 |url-status=live | title=A Short Introduction to Regular Expressions and Context-Free Grammars | access-date=August 24, 2012 | author=Norvell, Theodore | pages=4}}</ref>

Another extension is to allow additional terminal symbols to appear at the left-hand side of rules, constraining their application. This produces the formalism of [[context-sensitive grammar]]s.

== Subclasses ==
There are a number of important subclasses of the context-free grammars:
* [[LR parser|LR(''k'')]] grammars (also known as [[deterministic context-free grammar]]s) allow [[parsing]] (string recognition) with [[deterministic pushdown automaton|deterministic pushdown automata]] (PDA), but they can only describe [[deterministic context-free language]]s.
* [[SLR grammar|Simple LR]], [[LALR parser|look-ahead LR]] grammars are subclasses that allow further simplification of parsing. SLR and LALR are recognized using the same PDA as LR, but with simpler tables, in most cases.
* [[LL parser|LL(''k'') and LL(''*'')]] grammars allow parsing by direct construction of a leftmost derivation as described above, and describe even fewer languages.
* [[Simple grammar]]s are a subclass of the LL(1) grammars mostly interesting for its theoretical property that language equality of simple grammars is decidable, while language inclusion is not.
* [[Bracketed grammar]]s have the property that the terminal symbols are divided into left and right bracket pairs that always match up in rules.
* [[Linear grammar]]s have no rules with more than one nonterminal on the right-hand side.
* [[Regular grammar]]s are a subclass of the linear grammars and describe the [[regular language|regular]] languages, i.e. they correspond to [[finite automaton|finite automata]] and [[regular expression]]s.

LR parsing extends LL parsing to support a larger range of grammars; in turn, [[GLR parser|generalized LR parsing]] extends LR parsing to support arbitrary context-free grammars.  On LL grammars and LR grammars, it essentially performs LL parsing and LR parsing, respectively, while on [[nondeterministic grammar]]s, it is as efficient as can be expected.  Although GLR parsing was developed in the 1980s, many new language definitions and [[parser generator]]s continue to be based on LL, LALR or LR parsing up to the present day.

== Linguistic applications ==
[[Noam Chomsky|Chomsky]] initially hoped to overcome the limitations of context-free grammars by adding [[transformational grammar|transformation rules]].<ref name="chomsky1956"/>

Such rules are another standard device in traditional linguistics; e.g. [[grammatical voice|passivization]] in English. Much of [[generative grammar]] has been devoted to finding ways of refining the descriptive mechanisms of phrase-structure grammar and transformation rules such that exactly the kinds of things can be expressed that natural language actually allows. Allowing arbitrary transformations does not meet that goal: they are much too powerful, being [[Turing complete]] unless significant restrictions are added (e.g. no transformations that introduce and then rewrite symbols in a context-free fashion).

Chomsky's general position regarding the non-context-freeness of natural language has held up since then,<ref name="shieber1985">{{citation | title=Evidence against the context-freeness of natural language | year=1985 | last=Shieber | first=Stuart | journal=Linguistics and Philosophy | volume=8 | pages=333–343 | url=http://www.eecs.harvard.edu/~shieber/Biblio/Papers/shieber85.pdf |archive-url=https://web.archive.org/web/20040415200116/http://www.eecs.harvard.edu/~shieber/Biblio/Papers/shieber85.pdf |archive-date=2004-04-15 |url-status=live | doi=10.1007/BF00630917 | issue=3| s2cid=222277837 }}.</ref> although his specific examples regarding the inadequacy of context-free grammars in terms of their weak generative capacity were later disproved.<ref name="pullum-gazdar1982">{{citation | title=Natural languages and context-free languages | year=1982 | last=Pullum | first=Geoffrey K. | author2=Gerald Gazdar | journal=Linguistics and Philosophy | volume=4 | pages=471–504 | doi=10.1007/BF00360802 | issue=4| s2cid=189881482 }}.</ref> [[Gerald Gazdar]] and [[Geoffrey Pullum]] have argued that despite a few non-context-free constructions in natural language (such as [[cross-serial dependencies]] in [[Swiss German]]<ref name="shieber1985"/> and [[reduplication]] in [[Bambara language|Bambara]]<ref name="culy1985">{{citation | title=The Complexity of the Vocabulary of Bambara | year=1985 | last=Culy | first=Christopher | journal=Linguistics and Philosophy | volume=8 | pages=345–351 | doi=10.1007/BF00630918 | issue=3| s2cid=189881984 }}.</ref>), the vast majority of forms in natural language are indeed context-free.<ref name="pullum-gazdar1982"/>

== See also ==
* [[Parsing expression grammar]]
* [[Stochastic context-free grammar]]
* [[Context-free grammar generation algorithms|Algorithms for context-free grammar generation]]
* [[Pumping lemma for context-free languages]]

== References ==
{{reflist|30em}}

== Notes ==
{{notelist}}

== Further reading ==
* {{Hopcroft and Ullman 1979|author-link=no |title-link=no}} Chapter 4: Context-Free Grammars, pp.&nbsp;77–106; Chapter 6: Properties of Context-Free Languages, pp.&nbsp;125–137. {{sfn whitelist|CITEREFHopcroftUllman1979}}
* <!-- Both version are in use in referencing, don't remove this without changing the refs.--> {{Hopcroft, Motwani, and Ullman 2006}} {{sfn whitelist|CITEREFHopcroftMotwaniUllman2006}}
* {{Sipser 1997}} Chapter 2: Context-Free Grammars, pp.&nbsp;91–122; Section 4.1.2: Decidable problems concerning context-free languages, pp.&nbsp;156–159; Section 5.1.1: Reductions via computation histories: pp.&nbsp;176–183. {{sfn whitelist|CITEREFSipser1997}}
* {{cite book| author=J. Berstel, L. Boasson| title=Context-Free Languages| year=1990| volume=B| pages=59–102| publisher=Elsevier| editor=Jan van Leeuwen| series=Handbook of Theoretical Computer Science}}

== External links ==
* Computer programmers may find the [https://stackoverflow.com/questions/6713240/what-is-a-context-free-grammar stack exchange answer] to be useful.
* [https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/ CFG Developer] created by Christopher Wong at Stanford University in 2014; modified by Kevin Gibbons in 2015.

{{Formal languages and grammars}}

{{DEFAULTSORT:Context-Free Grammar}}
[[Category:1956 in computing]]
[[Category:Compiler construction]]
[[Category:Formal languages]]
[[Category:Programming language topics]]
[[Category:Wikipedia articles with ASCII art]]