# Context-free grammar

In computer science, a **context-free grammar** (**CFG**) is a formal grammar in which every production rule is of the form

- V
`->`*w*

*w*is a string consisting of terminals and/or non-terminals. The term "context-free" comes from the feature that the variable V can always be replaced by

*w*, in no matter what context it occurs. A formal language is

**context-free**if there is a context-free grammar which generates it.

Context-free grammars are important because they are powerful enough to describe the syntax of programming languages; in fact, almost all programming languages are defined via context-free grammars. On the other hand, context-free grammars are simple enough to allow the construction of efficient parsing algorithms which for a given string determine whether and how it can be generated from the grammar. See LR parser and LL parser for examples.

BNF (Backus-Naur Form) is often used to express context-free grammars.

Table of contents |

2 Derivations and Syntax trees 3 Normal forms 4 Properties of context-free languages |

## Examples

### Example 1

A simple context-free grammar is

where | is used to separate different options for the same non-terminal and ε stands for the empty string. This grammar generates the language### Example 2

This grammar can for example generate the string "( x + y ) * x - z * y / ( x + x )".### Example 3

Here, T can generate all strings with the same number of a's as b's, U generates all strings with more a's than b's and V generates all strings with fewer a's than b's.## Derivations and Syntax trees

and the string "1 + 1 + 1" then the left derivation of this string is the list [ (1), (1), (2), (2), (2) ]. Analogously the*rightmost derivation*is defined as the list that we get if we always replace the rightmost nonterminal first. In this case this would be the list [ (1), (2), (1), (2), (2)].

The distinction between leftmost derivation and rightmost derivation is important because in most parsers 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 parsers and LR parsers.

A derivation also imposes in some sense a hierarchical structure on the string that is derived. For example the structure of the string "1 + 1 + 1" would, according to the leftmost derivation, be:

- S->S+S (1)
- S->S+S+S (1)
- S->1+S+S (2)
- S->1+1+S (2)
- S->1+1+1 (2)
- { { { 1 }
_{S}+ { 1 }_{S}}_{S}+ { 1 }_{S}}_{S}

_{S}indicates a substring recognized as belonging to S. This hierarchy can also be seen as a tree:

S /|\\ / | \\ / | \\ S '+' S /|\\ | / | \\ | S '+' S '1' | | '1' '1'This tree is called a

*concrete syntax tree*(see also abstract syntax tree) of the string. In this case the presented leftmost and the rightmost derivation define the same syntax tree, however there is another (leftmost) derivation of the same string possible

- S-> S + S (1)
- S-> 1 + S (2)
- S-> 1 + S + S (1)
- S-> 1 + 1 + S (2)
- S-> 1 + 1 + 1 (2)

S /|\\ / | \\ / | \\ S '+' S | /|\\ | / | \\ '1' S '+' S | | '1' '1'If for certain strings in the language of the grammar there are 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.

## Normal forms

Every context-free grammar which does not generate the empty string can be transformed into an equivalent one in Chomsky Normal Form or Greibach normal form. "Equivalent" here means that the two grammars generate the same language.

Because of the especially simple form of production rules in Chomsky Normal Form grammars, this normal form 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 which decides whether a given string is in the language represented by that grammar or not (the CYK algorithm).

## Properties of context-free languages

- An alternative and equivalent definition of context-free languages employs non-deterministic push-down automata: a language is context-free if and only if it can be accepted by such an automaton.
- The union and concatenation of two context-free languages is context-free; the intersection need not be.
- The reverse of a context-free language is context-free, but the complement need not be.
- Every regular language is context-free because it can be described by a regular grammar.
- The intersection of a context-free language and a regular language is always context-free.
- There exist context-sensitive languages which are not context-free.
- To prove that a given language is not context-free, one employs the pumping lemma for context-free languages.