Grammars for Programming Languages

Of the four grammar types, context-free grammars (CFG) represent the best compromise between power of expression and ease of implementation.

Regular languages are obviously too weak, since they can't even describe situations such as checking that the number of "begin" and "end" statements in a text are equal (this would be a variant of the language $a^nb^n$)

However, there are some structures which even context-free languages cannot describe.

For example, the language (a|b)*c(a|b)* is regular and thus context-free. However, if we add in the condition that the string before the `c' must be the same as the string after the `c', we get the language $\{\alpha c \alpha\; \mid\; \alpha\; \in\; {\tt (a\vert b)*}\}$, which is not even context-free.

This language abstracts the problem of having a declaration of a variable name before its use (with $\alpha$ being the variable name and `c' the intervening program text).

In situations such as these, we would usually formulate a context-free grammar for the language in so far as it is possible, and leave details such as declaration/usage checking to the "semantic" phase.