Given the amount of material that tries to explain what a context-free grammar (CFG) is, I found it surprising that very few (in my sample, less than 1 in 20) give an explanation on why such grammars are called "context-free". And, to my mind, none succeeds in doing so.

My question is, why are context-free grammars called context-free? What is "the context"? I had an intuition that the context could be other language constructs surrounding the currently analyzed construct, but that seems not to be the case. Could anyone provide a precise explanation?

  • 4
    look up "most vexing parse" for C++ that will teach you why context-freeness is handy Aug 15, 2014 at 18:28
  • 6
    I thought I knew what a context-free grammar was until I just read some Googled definitions. Now I wish I had an etch-a-sketch and a soft blanky...maybe I'll just go outside... +1 for a good question. Looking forward to some intelligible answers!
    – BrianH
    Aug 15, 2014 at 18:29
  • Your intuition is what I understand it to be, even if the formal definition of "other language constructs surrounding the currently analyzed construct" is suitably arcane. But I'm not sure enough to post that as an answer.
    – Telastyn
    Aug 15, 2014 at 18:39
  • 1
    See wikipages on Context-free grammar and Chomsky hierarchy. In practice programming language parsing has some context, often handled "outside" of "context-free" (LR or LL) parsing, e.g. by some symbol table, attributes, or environment Aug 15, 2014 at 19:07
  • 1
    Here, have an xkcd reference: xkcd.com/1090 Aug 16, 2014 at 12:09

6 Answers 6


It means all of its production rules have a single non-terminal on their left hand side.

For example, this grammar which recognizes strings of matched parentheses ("()", "()()", "(())()", ...) is context-free:

S → SS
S → (S)
S → ()

The left-hand side of every rule consists of a single non-terminal (in this case it's always S, but there could be more.)

Now consider this other grammar which recognizes strings of the form {a^n b^n c^n : n >= 1} (e.g. "abc", "aabbcc", "aaabbbccc"):

S  → abc
S  → aSBc
cB → WB
BX → Bc
bB → bb

If the non-terminal B is preceded by the terminal/literal character c, you rewrite that term to WB but if it's preceded by b, you expand to bb instead. This is presumably what the context-sensitivity of context-sensitive grammars is alluding to.

A context-free language can be recognized a push-down automaton. Whereas a finite state machine makes use of no auxiliary storage, i.e. its decision is based only on its current state and input, a push-down automaton also has a stack at its disposal and can peek at the top of the stack for taking decisions.

To see that in action, you can parse nested parentheses by moving left to right and pushing a left parentheses onto a stack each time you encounter one, and popping each time you encounter a right parentheses. If you never end up trying to pop from an empty stack, and the stack's empty at the end of the string, the string is valid.

For a context-sensitive language, a PDA isn't enough. You'll need a linear-bounded automaton which is like a Turing Machine whose tape isn't unlimited (though the amount of tape available is proportional to the input). Note that that describes computers pretty well - we like to think of them as Turing Machines but in the real world you can't grab arbitrarily more RAM mid-program. If it's not obvious to you how an LBA is more powerful than a PDA, an LBA can emulate a PDA by using part of its tape as a stack, but it can also choose to use its tape in other ways.

(If you're wondering what a Finite State Machine can recognize, the answer is regular expressions. But not the regexes on steroids with capture groups and look-behind/look-ahead you see in program languages; I mean the ones you can build with operators like [abc], |, *, +, and ?. You can see that abbbz matches regex ab*z just by keeping your current position in the string and regex, no stack required.)

  • 16
    Very nice explanation. Although, a Turing machine's tape does not need to be infinite, only unlimited. There can be a tape-factory at either end that, when the machine bumps into it, simply makes more tape. That way, at any point in time, it is finite. Aug 15, 2014 at 19:36
  • 2
    @MikeDunlavey Thanks for the clarification, fixed it.
    – Doval
    Aug 15, 2014 at 19:41
  • 10
    But the tape factory would need infinite tape making materials, or infinite tape making materials making materials, or ... [stack overflow] Aug 15, 2014 at 22:08
  • 9
    @Mehrdad: You can simulate any number of stacks using two stacks: keep all the stacks stacked on top of each other on one stack and when you need to access some stack further down pop the upper stacks off and push them onto the second stack. This proves that n>2 stacks are not more powerful than 2 stacks. Now, whether 2 stacks are more powerful than 1 stack, that I don't know. My intuition says no, but that might depend on exactly what the stack primitives are. Aug 16, 2014 at 8:58
  • 11
    @JörgWMittag: two stacks is as good as a tape. Hand-wavily: use one stack as the left hand side of the tape and the other stack as the right hand side, relative to your current position. So a 2-PDA is a Turing machine. For primitives you just need to be able to pop a value from one stack and push it on the other, which is how you move along your tape. Aug 16, 2014 at 13:07

The other answers are quite long, even if accurate and correct. This is the short version.

If you have a string of characters (terminals and nonterminals) and you wish to replace a nonterminal in the string, a context-free grammar allows you to do that regardless of the characters surrounding the nonterminal.

Consider the following rules (lowercase are terminals, uppercase are nonterminals):

A -> a
AB -> a

In the first rule, you can replace an A regardless of what appears around it (context). In the second rule, you cannot replace A unless it is followed by B. While both nonterminals will be replaced in that case, the important point is that the nonterminals surrounding the A matter. One cannot replace BA with a, or B with a: only an A followed by a B because the order, the context of the nonterminals is important. This means the context of a nonterminal matters in the second rule, making it context-sensitive, while the first rule is context-free.

  • 1
    This is a really good explanation, though I'm not qualified to vouch for its accuracy or completeness. Is it all there is to it?
    – rick
    Aug 19, 2014 at 2:57
  • 1
    Computer grammars are part of the Chomsky hierarchy. That article is a good place to start. Also, this topic should be part of any baccalaureate program in computer science. At the very least, universities should teach regular and context-free grammars since those comprise the overwhelming majority of languages that we programmers are likely to encounter.
    – user22815
    Aug 19, 2014 at 4:17
  • @Snowman:Very crisp.It would be better if you say that "you can't derive to a from AB unless A is followed by B instead of saying "you can't replace A" which might not be possible because actually you're replacing AB isn't it?
    – justin
    Oct 20, 2015 at 10:41
  • @justin correct. I updated my answer to be more clear on this.
    – user22815
    Oct 20, 2015 at 16:06
  • @Snowman:Do you mean to replace A or AB in the second rule(context-sensitive)?I think you're still trying to replace A as said from your answer.
    – justin
    Oct 26, 2015 at 6:34

To understand the distinction and the terminology better, it's a good idea to contrast a context-free language like anbn with a context-sensitive one like anbncn. (Notation: a, b, and c are literals here and the exponent n means repeating the literal n times, n>0, say.) For instance, aabbc or aabbbcc is not in the latter language, whereas aabbcc is.

An acceptor for the context-free language anbn can contract a pair of a and b regardless what's around it (i.e. regardless of the context in which ab appears) and it will function correctly, accepting only strings in the language and rejecting anything else, i.e. the grammar is S -> aSb | ab. Note that there are no terminals on the left side of the production(s). (There are two production rules, but we're just writing them compactly.) The acceptor can basically make a local, context-free decision.

In contrast, you can't do something like that for the context-sensitive language anbncn, because for latter you must remember somehow the context you were in, i.e. how many contractions of ab you do to match them with contractions of bc. A grammar for the latter language is

S -> abc | aBSc
Ba -> aB
Bb -> bb

Note that you have both terminals and non-terminals on the left in the last two rules. The terminals on the left are the context in which the non-terminals can be expanded.

Bootnote regarding "contract" vs. "expand" terminology etc.: although the formal grammars are [formally, hah] generative, the way they're actually implemented in parsers is actually reductionist, i.e. you contact everything to a non-terminal, basically applying the rules "in reverse", which is why even the first grammar given above is not practical in a program (it would give you the famous shift-reduce conflict because you can't decide which rule to apply), but the above two grammars suffice for illustrating the distinction between context-free and context-sensitive. The issue of ambiguity in context-free grammars is rather complicated, and not really the topic of this question so I'm not going to say more here, especially since it turns out that Wikipedia has a decent article on that. In contrast its articles on context-free and especially the one on context-sensitive language are !@#$@!#$ especially if you are new to the topic... I guess that's more on my TODO list.


The answers above give a pretty good definition of what it is. Let's see if I can put it in my own words, so that you will have 23 explanations instead of 20. The whole purpose of a grammar, any grammar, is to figure out if a particular sentence is a sentence in the given language. However, what we really use grammars and parsing for is to figure out what the sentence means. It's like the old diagramming of a sentence you may or may not have done back in English class back in school. A sentence is made of a subject part and a predicate part, a subject part has a noun and maybe some adjectives, a predicate part has a verb and perhaps an object noun, with some more adjectives, etc.

If there were a grammar for English (and I don't think there is, not in the computer science sense) then it would have rules of the following form, called productions.

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun


You could then write a program and hand it any sentence, and the program could use the grammar to figure out which part of the sentence each word is, and what relation they have to each other.

If in every production, there is only one thing on the left side, then that means that whenever you see the right side in the sentence, you are allowed to substitute in the left side. For instance whenever you saw adjective noun, you could say "That's a SubjectPart" without paying any attention to anything outside of that phrase.

However, English (even the simplified description of English I gave above) is context-sensitive. "Adjective noun" isn't always a SubjectPart, it could be a NounPhrase in a PredicatePart. It depends on the context. Let's expand our pseudo-English grammar a bit:

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun
PredicatePart -> VerbPhrase ObjectNounPhrase
VerbPhrase ObjectNounPhrase -> VerbPhrase Adjective Noun

You can only make an "adjective noun" into an ObjectNounPhrase if it comes right after a VerbPhrase.

Basically, if you have a production and you can apply it any time you want, no matter what surrounds it, it is context-free.

You can always tell if a grammar is context free easily. Just check if there is more than one symbol on the left side of the arrows.

Any language might be described by more than one grammar. If some grammar for a language is context-free, the language is context free. It can be proven for some languages that there is no context-free grammar possible. I suppose there might be a context-free grammar for the simplified pseudo-English subset I am describing above.

As for why it matters, it requires a simpler kind of program to parse a context-free grammar. As noted in the other answers, it doesn't require the full power of a Turing machine to parse a context-free grammar. A lookahead LR(1) parser (which is a kind of pushdown machine) for a particular context-free grammar can parse any sentence in that grammar in time and space linear to the length of the sentence. If the sentence is in the language, the parser will produce a structure tree identifying what each symbol in the sentence means (or at least what part it plays in the structure). If the sentence is not in the grammar, the parser will notice and stop on the first symbol which is impossible to reconcile with the grammar and preceding symbols (on the first "error").

What's even better is that there are programs which you can give a description of a grammar, and a list of instructions about what to do with each part (in a sense attaching a "meaning" to each production) and the program will write the parser for you. The program will parse the sentence, find the structure, and run your instructions on each part of the structure. This kind of program is called a parser-generator or compiler-compiler.

This kind of language analysis was invented for automatic analysis of natural language (such as English) but it turns out that this is most useful for analyzing computer languages. A language designer can write a grammar which captures his new language, then run it through the parser-generator to get a program which parses his language, and translates, interprets, compiles, executes, etc if he wants.

In fact, in most cases you can't really do this. For instance, balanced parentheses are a context-free language, but a language where it is required to declare all variables before you use them is context-sensitive. The parser is a part of the compiler, but additional logic is required to enforce these other requirements. What you then have to do is write a grammar which captures as much of your language as possible, run that through a parser-generator, then write code which enforces the rest of the requirements (symbol table handler, etc).

We don't generally use context-sensitive grammars because they are much more poorly supported. I don't know if there is an equivalent to an LR(k) parser-generator for context-sensitive languages. Yes, a Turing machine (or linear bound machine) can parse one, but I don't know if there is a general algorithm for turning a context-sensitive grammar into a program for a Turing machine, in the sense that an LR(1) generator makes parse tables for a pushdown machine. My guess is that the tables which underlie the parser would be exponentially larger. In any case, CS students (like myself, back in the day) are usually taught context-free grammars and LR(1) parser generators such as YACC.


There are two senses of the term "context-free", as I alluded to in this earlier reply What Is Meant By 'Context-Free':

"algebraic": relating to the property that the left-hand sides of phrase structure rules contain only a single non-terminal and that the grammar can be collated into a fixed-point system,


"separable", or "context-free" in the more direct sense: that the question of whether a phrase structure rule applies at a given location should be independent of the context surrounding that location.

These two senses are equivalent. This equivalence is not a trivial result. Moreover, the equivalence applies in a setting much more broad than what is normally covered by the classical treatment of grammars. I'll lay out the basics of the equivalence result here.

That, in turn, will answer the question in a more substantial way than you may see otherwise.

Grammars Over Monoids
First, a brief review: the response is issued in the general setting of grammars over monoids M. The usual senses of a grammar are for languages, where the monoid M = X* is the free monoid generated by a set X that is deemed the "alphabet" of the language, and for translations, where the monoid X* × Y* is for word pairs, drawn from an input alphabet X and output alphabet Y. But the term "grammar", and almost everything discussed relating to this concept, can be applied generically to monoids.

If Q denotes the set of non-terminals for the grammar, then they may be conceived of as a set of variables that are affixed to the underlying monoid M to yield the free extension M[Q]. Its words have the form mqm⋯qm, where the number of q ∈ Q in it is the "degree" of the word, and they are interspersed with words m ∈ M. Words in M[Q] of degree 0 are those drawn from M, itself, thereby making M a sub-monoid of M[Q]. Similarly, Q may be considered a subset of M[Q] consisting of all degree 1 words of the form 1q1, where 1 ∈ M is the monoid identity (i.e. empty word) and q ∈ Q.

A grammar over M consists of a finite set H ⊆ M[Q] × M[Q] and a distinguished "start configuration" S ∈ M[Q], which is normally (but unnecessarily) restricted to S ∈ Q. The set H generates a derivation relation → over M[Q] consisting of 0 step derivations α → α, where α ∈ M[Q], 1 step derivations λαρ → λβρ, where (α,β) ∈ H and n step derivations α_0 → α_n, for n > 1, from a set of 1-step derivations α_i → α_{i+1}, where 0 ≤ i < n.

The "derive set" [α] for each configuration α ∈ M[Q] is given by [α] = { m ∈ M: α → m }. The derive set [S] for the top-level configuration is the subset of M generated by the grammar.

Algebraic Versus Separable
A grammar may be called "algebraic" if the phrase structure rules are restricted to have only a single non-terminal on the left-hand side, i.e. if H ⊆ Q × M[Q]. A grammar may be called "separable" if its derive sets satisfy the properties: [m] = {m}, for m ∈ M and [αβ] = [α][β], for α, β ∈ M[Q]. This entails the property that the derivations of α ∈ M[Q] should be independent of what context they are applied in. In particular if λ, ρ ∈ M describe left and right word contexts for α, then [λαρ] = {λ}[α]{ρ}.

More precisely, we can call a grammar "separable" if (1) m → β implies m = β, and (2) αβ → γ implies that there is a factoring γ = α'β' such that α → α' and β → β'.

It might be possible to combine these two conditions directly into a strict left-right context condition that (3) λαρ → γ (where λ, ρ ∈ M are respectively left and right word contexts) implies a factoring γ = λα'ρ, where α → α'. I haven't checked into it (yet): whether (3) is equivalent to (1) and (2) taken together. You might also need the condition [1] = {1}, where 1 ∈ M[Q] is the monoid identity inherited from 1 ∈ M.

There were two results alluded to in the previous reply.

Algebraic Grammars Are Separable
First, the following property

if α → α' and β → β' then αβ → α'β'

is easy to establish by an inductive argument from the definition given for the "→" relation. This shows that [α][β] ⊆ [αβ]. This applies generically to all grammars over monoids.

To show the opposite inclusion, we take γ ∈ [αβ], i.e. αβ → γ. If the derivation is length 0, then γ = αβ ∈ [α][β]. If it is of length 1 or more, than it may be decomposed into αβ → λqρ → λδρ ∈ M, with the last step being a length 1 derivation with (q, δ) ∈ H and λ, ρ ∈ M. By the "separability" property (2), there is a factoring α'β' = λqρ, such that α → α' and β → β'. By the way the free extension M[Q] is defined, the element q ∈ Q is prime, so it must appear in either α' or β', but not both.

In the first case, the result is the factoring α' = λqε, ρ = εβ', with α → α' = λqε → λδε and β → β', resulting in (λδε)β' = λδ(εβ') = λδρ ... thereby showing that λδρ ∈ [α][β].

In the second case, the result is the factoring λ = α'ζ, β' = ζqρ, with α → α' and β → β' = ζqρ → ζδρ, resulting in α'(ζδρ) = (α'ζ)δρ = λδρ ... thereby, again, showing that λδρ ∈ [α][β].

Second, the property that [m] = {m}, for m ∈ M is trivial, since the only phrase structure rules in an algebraic grammar have non-terminals on the left-hand side, and m has no non-terminals in it, since it is of degree 0. Therefore, the only derivations m → β are the length-0 derivations where m = β. Thus, [m] = {m}.

Separable Grammars Reduce Equivalently To Algebraic Grammars
This requires replacing the phrase structure rules H by an alternative, finite, set H_0 ⊆ Q × M[Q] of the required indicated form. This set is obtained by selecting out a finite set of H-derivations of this form and using them as a new basis, in such a way as to ensure that the derive sets [α] are all unaffected.

This is done by taking each phrase structure rule (α,β) ∈ H, by decomposing α = m_0 q_1 m_1 ⋯ q_n m_n, where the m's are in M, the q's are in Q, and n is the degree of the word α ∈ M[Q]. This includes the possibility that n = 0! It won't matter. Bear in mind that the factoring of α ∈ M[Q] in this way is unique, since the q's are prime in M[Q].

Then we apply separability property (2) to factor β = γ_0 β_1 γ_1 ⋯ β_n γ_n, where m_i → γ_i, for 0 ≤ i ≤ n, and q_i → β_i, for 0 < i ≤ n. Then we use separability property (1) to conclude that γ_i = m_i, for 0 ≤ i ≤ n, thereby yielding the factoring β = m_0 β_1 m_1 ⋯ β_n m_n.

Then, we replace (α,β) by the rules (q_i,β_i), for 0 < i ≤ n. The replacement leaves all the derive sets unaffected.

We carry out the same replacement with each (α,β) ∈ H, one-by-one, thereby ultimately leading to the a new set H_0 of phrase structure rules of the desired form.

The result is that the separable grammar is reduced to algebraic form, such that all the derive sets remain unchanged.

New contributor
NinjaDarth is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • Impressive if you wrote this yourself, a bit less if you got it from ChatGPT :-)
    – Dominique
    2 days ago
  • You might want to try this with ChatGPT to see what happens (3.5 is open access, now, at OpenAI). I just posed the query - Can the concept of "grammar" be defined for arbitrary monoids? - just to probe its current state of knowledge. Based on what I saw, I don't think it's going to be able to make the connections to arrive at a result like this. But you can try it out and see. Maybe it will come up with something. But I wouldn't put any bets on it.
    – NinjaDarth
    2 days ago
  • Actually, you got me curious and the query led to a longer dialogue. Still 3.5. I had to hand-hold it to get it to recognize the use of free extensions, but once that was pointed out, it suggested generalizing to allow the "start symbol" to be an arbitrary element of the free extension, not just a non-terminal. But: it initially wanted no non-terminals on the right. And when posed with the problem of generalizing away from the condition that the left-hand side be a single non-terminal, it went astray: it wanted both sides to have the same non-terminals. I'm running out of hands to hold.
    – NinjaDarth
    2 days ago

Context-free grammars do not consider any context for production rules. Context are either terminals or non-terminals.

So: Context-free grammars only have a single non-terminal on the left side of the production rules.

  • 3
    What does this add to the existing answers? Also, a production rule with two or more non-terminals on the left hand side isn't context free either.
    – user7043
    Aug 18, 2014 at 18:47
  • 1
    I think the given answers are much too long. If one would add a TL;DR, I would delete this one. Aug 18, 2014 at 18:51
  • 2
    Nice! Would you say that the "context" is the extra characters that qualify when each production rule could be applied?
    – rick
    Aug 19, 2014 at 3:02
  • 2
    This answer concisely answers the question, though the other answers explain it further. Jun 27, 2022 at 11:30
  • @rick Exactly that. “Context free” can have a rule “replace A with cBad” for example. “Context sensitive” can have a rule “replace A the same way, but only if A is preceded by abc and followed by xyz”.
    – gnasher729
    2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.