patternMajor
What's really meant by context-free in the term context-free grammar?
Viewed 0 times
meantreallythewhatfreetermgrammarcontext
Problem
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 ?
So can anyone help with this ?
Solution
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.
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.
Context
StackExchange Computer Science Q#68231, answer score: 31
Revisions (0)
No revisions yet.