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 “(” and “)” and one nonterminal symbol S. The production rules are
S → SS
S → (S)
S → ()
The first rule allows Ss to multiply; the second rule allows Ss to become enclosed by matching parentheses; and the third rule terminates the recursion.
Well-formed nested parentheses and square brackets
A second canonical example is two different kinds of matching nested parentheses, described by the productions:
S → SS
S → ()
S → (S)
S → []
S → [S]
with terminal symbols [ ] ( ) and nonterminal S.
The following sequence can be derived in that grammar:
([ [ [ ()() [ ][ ] ] ]([ ]) ])
A regular grammar
Every regular grammar is context-free, but not all context-free grammars are regular. The following
context-free grammar, however, is also regular.
S → a
S → aS
S → bS
The terminals here are a and b, while the only non-terminal is S. The language described is all nonempty strings of s and s that end in .
This grammar is 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 pipe symbols, the grammar above can be described more tersely as follows:
S → a | aS | bS
Matching pairs
In a context-free grammar, we can pair up characters the way we do with brackets. The simplest example:
S → aSb
S → ab
This grammar generates the language , which is not regular (according to the Pumping Lemma for regular languages).
The special character ε stands for the empty string. By changing the above grammar to
S → aSb | ε
we obtain a grammar generating the language instead. This differs only in that it contains the empty string while the original grammar did not.
Algebraic expressions
Here is a context-free grammar for syntactically correct infix algebraic expressions in the variables x, y
and z:
S → x
S → y
S → z
S → S + S
S → S – S
S → S * S
S → S / S
S → ( S )
This grammar can, for example, generate the string
( x + y ) * x – z * y / ( x + x )
as follows:
S (the start symbol)
→ S – S (by rule 5)
→ S * S – S (by rule 6, applied to the leftmost S)
→ S * S – S / S (by rule 7, applied to the rightmost S)
→ ( S ) * S – S / S (by rule 8, applied to the leftmost S)
→ ( S ) * S – S / ( S ) (by rule 8, applied to the rightmost S)
→ ( S + S ) * S – S / ( S ) (etc.)
→ ( S + S ) * S – S * S / ( S )
→ ( S + S ) * S – S * S / ( S + S )
→ ( x + S ) * S – S * S / ( S + S )
→ ( x + y ) * S – S * S / ( S + S )
→ ( x + y ) * x – S * y / ( S + S )
→ ( x + y ) * x – S * y / ( x + S )
→ ( x + y ) * x – z * y / ( x + S )
→ ( x + y ) * x – z * y / ( x + x )
Note that many choices were made underway as to which rewrite was going to be performed next. These
choices look quite arbitrary. As a matter of fact, they are, in the sense that the string finally generated is
always the same. For example, the second and third rewrites
→ S * S – S (by rule 6, applied to the leftmost S)
→ S * S – S / S (by rule 7, applied to the rightmost S)
could be done in the opposite order:
→ S – S / S (by rule 7, applied to the rightmost S)
→ S * S – S / S (by rule 6, applied to the leftmost S)