Lecture 4 min.
Context-free grammar (CF grammar, CFG) is a special case of a formal grammar (type 2 in the Chomsky hierarchy) in which the left-hand sides of all productions are single nonterminals (objects denoting some entity of the language (for example: a formula, an arithmetic expression, a command) and having no specific symbolic value). The meaning of the term "context-free" is that a production can be applied to a nonterminal regardless of the context of that nonterminal (unlike the general case of Chomsky's unrestricted grammar).
A language that can be generated by a CF grammar is called a context-free language, or CF language.
In essence, a CF grammar is another form of BNF.
CF grammars are widely used in computer science. They define the grammatical structure of most programming languages, structured data, and so on (see parsing).
A pushdown automaton is sufficient for parsing a CF grammar, whereas parsing non-CF grammars may require a full Turing machine.
There are two different classes of recognizers, whose names are related to the order in which the derivation tree is built. As a rule, all recognizers read the input string of symbols from left to right, since that notation is assumed in writing program source text.
Top-down recognizers produce leftmost derivations and build the derivation tree from the top down.
They use modifications of the algorithm with trial of alternatives. In building them, a method is applied that makes it possible to choose one and only one alternative unambiguously at each step of the pushdown automaton (the "pop" step in this automaton is always performed unambiguously).
Bottom-up recognizers produce rightmost derivations and build the derivation tree from the bottom up.
Bottom-up recognizers use modifications of the shift-reduce algorithm. In building them, methods are applied that make it possible to choose unambiguously between performing a "shift" or a "reduce" at each step of the extended pushdown automaton, and, when performing a reduce, to choose unambiguously the rule by which the reduction will be made. The shift-reduce algorithm.
Examples of CF grammars and the corresponding CF languages:
Defined by the formula 
;
;
.
and 
;;
;.This grammar generates the language of nested parentheses 
.
<expression> → <expression> + <term>, <expression> → <expression> - <term>, <expression> → <term>, <term> → <term> * <factor>, <term> → <term> / <factor>, <term> → <factor>, <factor> → ( <expression> ), <factor> → x,
This grammar generates an arithmetic expression containing the simplest arithmetic operations on the variable x. If the terminal 'x' is replaced by the nonterminal <number>, the result is a grammar generating an arithmetic expression consisting of addition, subtraction, multiplication and division operations on integers.
Not all languages can be generated by CF grammars. The easiest way to prove this is as follows: CF grammars form a countable set, whereas the cardinality of the set of all languages is the continuum. A constructive proof of the same fact can be obtained, for example, from the fact that the language {anbncn | n≥1} is not context-free; however, a short proof of the latter statement apparently does not exist: the published proofs rely on the pumping lemma for context-free languages.
Tree-adjoining grammar generalizes context-free grammar in that the elementary unit in the derivation rules is trees rather than individual symbols.
Comments