What's really meant by context-free in the term context-free grammar?

Question

I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result.

So can anyone help with this ?

Answer 1

The context can be explained with regards to the production rules allowed for different grammars in Chomsky hierarchy.

If you consider context-free grammars, their production rules have the following form:

$$ A \rightarrow \alpha$$

So, you can observe that the left part of this kind of rules is made up of only one non-terminal symbol; thus, the substitution of the non-terminal symbol takes place without considering its "context", that is the other symbols it is surrounded by.

On the other hand, if you consider production rules of context-sensitive grammars, they have the following form:

$$ \beta A \gamma \rightarrow \beta \alpha \gamma$$

where $A$ is a non-terminal and $\alpha$, $\beta$, $\gamma$ are sequences of non-terminals and terminals.

In this case the "context" (i.e., $\beta$ and $\gamma$) of the non-terminal symbol to be substituted influences the effect of the substitution and it is part of the rule itself.

You can find more details in this answer on mathematics and in this answer on software engineering.

Answer 2

"Context" is surrounding text. Context-free grammars are context-free in the sense that the rules look like $A\to\text{things}$, rather than $\text{stuff}\,A\,\text{more-stuff}\to\text{things}$. The left-hand side of a rule is always a single non-terminal symbol. That is, the rules for expanding a non-terminal symbol don't depend on what text appears around that symbol (its context), but only depend on the symbol itself. For example, in the grammar for a programming language, the term $\mathrm{Expr}$ expands to the same kind of expression whether you're writing an assignment (e.g., x:=y+z), passing arguments to a function (e.g., f(y+z)) or returning a value from a function (e.g., return y+z).

Answer 3

Generically speaking, even regular languages may have context dependencies, meaning that you can determine - to some extent - in what ways symbols can appear in the vicinity of other symbols in a string that belongs to that language.

What is specific to context-free grammars is that when there are multiple ways of substituting a non-terminal symbol, by applying different rules with the same non-terminal on the right side, the choice of which rule to apply is never dependent on what is happening around this symbol during the derivation process.

You can think of them as context-free derivation languages, context-free languages for short.

Answer 4

What's meant by "Context Free"? Ultimately that the applicability of a phrase structure rule, for a grammar, should be independent of the surrounding context, where it is applied. The fact that this should go hand-in-hand with the requirement that phrase structure rules for such a grammar should each have only a single non-terminal on the left-hand side, is actually not a trivial result. As far as I know, the term "context-free" is just defined as a grammar that has just single non-terminal on the left-hand side, rather than being defined as a grammar whose derivations have the above-mentioned "context-freeness" property, so the issue is evaded ... and your question is actually a valid question.

First, let's generalize this a little (actually: a lot), and I'll show you how the "context-freeness" comes about - in the way, alluded to above, that speaks directly to this attribute; and then call out a result that actually speaks to the equivalence of the two senses of "context-freeness".

Word Algebras As Monoids
Suppose you want to write a grammar for a set of words. The words may (or may not) be composed of fundamental constituents drawn from a set $X$. Or, they may actually be taken from two sets $X$ and $Y$, if you want to talk about "languages" over two or more channels. An example of that is what are known as "translations", which are formalized as sets of word pairs $(v,w)$, where $v$ is a word formed from constituents in the set $X$, and $w$ from those in the set $Y$.

The words form an algebra, with the fundamental elements being the empty word, which we'll call $1$, and an operation $w, w' ↦ ww'$ called "concatenation". These satisfy the properties: $$1 w = w = w 1,\quad (w w') w'' = w (w' w''),$$ that define an the algebra known as a Monoid. The cardinal example of this, which you normally see in the setting of "formal languages" is the monoid $X^*$ consisting of all sequences of elements drawn from $X$, each sequence representing the spelling of a word, including the length-zero sequence, denoted by $1$. That's the "Free Monoid" generated by $X$. It's "free" because its elements satisfy no properties other than those given by the fundamental axioms of a monoid.

For the case where we have two channels, we speak, instead, of the direct product $X^* × Y^*$ of the free monoids $X^*$ and $Y^*$. It may, itself, be regarded as a free monoid $(X ∪ Y)^*$, but subject to the conditions that $vw = wv$ if $v ∈ X^*$ and $w ∈ Y^*$ ... provided that we write the elements of $X$ and $Y$ so that $X^*$ and $Y^*$ themselves do not overlap; e.g. by tagging them as $(v,1_Y)$ for $v ∈ X^*$ and $(1_X,w)$ for $w ∈ Y^*$, with the monoid identities $1_X ∈ X^*$ and $1_Y ∈ Y^*$, and then defining products generally by $(v,w)(v',w') = (vv',ww')$ where $v, v' ∈ X^*$ and $w, w' ∈ Y^*$. So, when dealing with "translations", instead of just with "languages", we use certain non-free monoids.

For communications over three channels, one could also consider a word algebra over $X^* × Y^* × Z^*$, and a similar situation applies for communications over four or more channels.

Grammars Over Monoids
Originally, back in the 1960's people treated grammars as algebraic systems, so that a context-free grammar such as $$S → N V,\quad N → n,\quad N → N P,\quad V → v N,\quad V → V P,\quad P → p N,$$ could just as well be treated as a kind of system of equations $$S = N V,\quad N = n + N P,\quad V = v N + V P,\quad P = p N.$$ In a sense, this is true: that they could be considered as set-theoretic equations over the power set $𝔓M$ of $M$ ... provided that you equip this set with the structure of a monoid, by generalizing the product operation defined over $M$ to a product on subsets in $𝔓M$ with $$A, B ∈ 𝔓M ↦ A B = \{ a b ∈ M: a ∈ A, b ∈ B \} ∈ 𝔓M.$$ This is a monoid, too, with the role of $1$ played by $\{1\}$. It contains $M$ as a sub-algebra, by way of the mapping $m ∈ M ↦ \{m\} ∈ 𝔓M$, so for this reason the convention was adopted that $m$ could be used in place of $\{m\}$ when dealing with $𝔓M$.

The family $𝔓M$ is also equipped with the sum operation $$A, B ∈ 𝔓M ↦ A + B = A ∪ B ∈ 𝔓M$$ and this allows one to literally treat the grammar as a system of set-theoretic equations.

By the 1970's, however, this view was refined in that it came to be understood that the system should be treated as a system of set-theoretic inequalities: $$S ≥ N V,\quad N ≥ n + N P,\quad V ≥ v N + V P,\quad P ≥ p N,$$ with the inequality relation being subset order, $A ≥ B$ if and only if $A ⊇ B$, and that the solution that describes all of the non-terminals as subsets of $M$ would be the least solution to the system.

But in both cases, in the older view, the non-terminals were also called "variables". So, if we collect the variables together into a set, $Q$, we could treat the set of all words formed from both $M$ and $Q$ as an extension of the monoid $M$, itself, obtained by just attaching the set $Q$ to it, subjecting it to no additional relations other than what the basic monoid properties require. The result is $M[Q]$.

The free monoid $X^*$, itself, can be regarded as a free extension of the trivial 1-element monoid $∅^* = \{ 1 \}$ and written as $X^* = ∅^*[X]$.

In formal language texts, $X^*[Q]$ is hacked into play by writing it as just $(X ∪ Q)^*$, subject to the condition that $X^*$ and $Q^*$ have no overlap. The treatment, however, is cumbersome and it gets more complicated when dealing with translation sets, where one wants the free extension $(X^* × Y^*)[Q]$. There, you'd have to define it as $(X ∪ Y ∪ Q)^*$, and subject it to the relation that $v w = w v$, for $v ∈ X^*$ and $w ∈ Y^*$, but also ensure that $X^*$, $Y^*$ and $Q^*$ have no overlap.

So, it's easier - instead - to collate all these special cases together into one generality: that a grammar over a monoid $M$ should be posed as a system of set-theoretic inequations over the free extension $M[Q]$, obtained by adding the set $Q$ of non-terminals to $M$.

The grammar, itself, consists of a finite set $H ⊆ M[Q] × M[Q]$, where each $(α, β) ∈ H$ is considered to be a phrase structure rule. There is, in addition, a distinguished element $S ∈ M[Q]$, that may be treated as the top-level expression. Usually it is assumed to be a non-terminal $S ∈ Q$, but that's an unnecessary restriction which actually (needlessly) complicates everything.

A derivation can be the trivial zero-step derivation $α → α$, where $α ∈ M[Q]$, or a single-step derivation $λαρ → λβρ$, where $(α,β) ∈ H$, that's carried out in a context that has a $λ ∈ M[Q]$ to the left and a $ρ ∈ M[Q]$ to the right, or it can be a multi-step derivation $α_0 → α_n$, obtained from single-step derivations $α_i → α_{i+1}$, for $i ∈ \{0,1,⋯,n-1\}$, for some integer number of steps $n ≥ 2$.

For each $α ∈ M[Q]$, we can define the "derived set" $$[α] = \{ m ∈ M: α → m \},$$ that determines the set of all words in $M$ derived from $α ∈ M[Q]$.

The subset of $M$ generated by the grammar is just $[S]$.

To emphasize: this definition is generic to all monoids. So, it applies not just to give you descriptions of "languages" as subsets of free monoids $X^*$, but "translations" as subsets of product monoids $X^* × Y^*$, and more general monoids besides.

It's one formalism that covers all these cases, rather than a multiplicity of them that you see in the literature, even today.

Context-Freeness & Grammars As Algebraic Systems Of Inequations
From the description just laid out, you don't actually get any characterization - in general - of a grammar as a system of inequalities over a set of variables $Q$. It need not even be "computeable", because, the monoid $M$ need not be.

Instead, in general, all you can say is that if $α → β$ is a derivation, then $[α] ⊇ [β]$, so that the set $H$, itself, may be written as a set of set-theoretic inequalities that is generally non-linear on the left-hand side, as well as on the right-hand side.

However, if you impose the condition that $[α]$ should be independent of left and right word contexts $λ ∈ M$ and $ρ ∈ M$, then it will actually become possible to do so and to rewrite the grammar as a "context-free" grammar in the more familiar sense of the term and to cast it as a set-theoretic system of the kind previously described.

More generally, if you impose two additional conditions: $$[m] = \{m\},\quad m ∈ M,$$ and $$[α β] = [α][β],\quad α, β ∈ M[Q],$$ which together entail the condition $$[λ α ρ] = \{λ\} [α] \{ρ\},\quad λ, ρ ∈ M,\quad α ∈ M[Q],$$ then it actually proves possible to replace the phrase structure rules $H$ by a more refined set $H_0 ⊆ Q × M[Q]$ that permits only single non-terminals from $Q$ on the left-hand sides of its phrase structure rules, but yields the same "derive" sets $[α]$ for $α ∈ M[Q]$, as $H$ did.

I'm not sure the proof of this has actually (yet) been published anywhere, and it is kinda tricky to extract out a finite set of phrase structure rules $H_0$ from $H$, that satisfy the property that their left hand sides all be single non-terminals from $Q$, when no assumption was made on $H$ about what the left-hand sides of its rules should be. But, it can be done.

Once you have a grammar whose phrase structure rules $H_0$ have this property, then each one $(q,β) ∈ H_0$, where $q ∈ Q$ and $β ∈ M[Q]$ can be written as a set-theoretic inequality $[q] ⊇ [β]$, and the right-hand side, itself, can be decomposed into $$[β] = \{m_0\} [q_1] \{m_1\} ⋯ [q_k] \{m_k\}$$ where $v ∈ M[Q]$ is decomposed as $$β = m_0 q_1 m_1 ⋯ q_k m_k,\quad (m_0,m_1,⋯,m_k ∈ M,\quad q_1,⋯,q_k ∈ Q),$$ where $k = 0, 1, 2, ⋯$ is the degree of the word $β ∈ M[Q]$ (i.e. the number of non-terminals in it).

The result is that the rule $q → β$ is rewritten as a set-theoretic inequation $$[q] ⊇ \{m_0\} [q_1] \{m_1\} ⋯ [q_k] \{m_k\},$$ and, together, the set $H_0$ yields a system of such inequations that captures the 1970's view of what a context-free grammar ought to be.

The grammar is "context-free" in the sense that $[αβ] = [α][β]$, precisely when it is either already is or can be equivalently described by a grammar that is "context-free" in the sense that all of its phrase structure rules have a single non-terminal on the left-hand side. The second result, is that all grammars, whose phrase structure rules have single non-terminals on their left-hand sides, are "context-free" in the above sense.

If you refer to such grammars as "algebraic", when the phrase structure rules have single non-terminals on the left, and reserve the term "context-free" when the two properties $[αβ] = [α][β]$ (for $α, β ∈ M[Q]$) and $[m] = \{m\}$ (for $m ∈ M$) hold, then the two results are:

    "Algebraic" Grammars Are "Context-Free".

and

    "Context-Free" Grammars May Be Equivalently Reduced To "Algebraic" Grammars.

To the best of my knowledge, this is still unpublished. We might put up something on ArXiv in the near future.