Redirected from Contextfree language
Contextfree grammars are important because they are powerful enough to describe the syntax of programming languages; in fact, almost all programming languages are defined via contextfree grammars. On the other hand, contextfree grammars are simple enough to allow the construction of efficient parsing algorithms which for a given string determine whether and how it can be generated from the grammar. See LR parser and LL parser for examples.
BNF (BackusNaur Form) is often used to express contextfree grammars.

A simple contextfree grammar is
Here is a contextfree grammar for syntactically correct infix algebraic expressions in the variables x, y and z:
A contextfree grammar for the language consisting of all strings over {a,b} which contain a different number of a's than b's is
There are basically two ways to describe how in a certain grammar a string can be derived from the start symbol. The simplest way is to list the consecutive strings of symbols, beginning with the start symbol and ending with the string, and the rules that have been applied. If we introduce a strategy such as "always replace the leftmost nonterminal first" then for contextfree grammars the list of applied grammar rules is by itself sufficient. This is called the leftmost derivation of a string. For example, if we take the following grammar:
The distinction between leftmost derivation and rightmost derivation is important because in most parsers the transformation of the input is defined by giving a piece of code for every grammar rule that is executed whenever the rule is applied. Therefore it is important to know whether the parser determines a leftmost or a rightmost derivation because this determines the order in which the the pieces of code will be executed. See for an example LL parsers and LR parsers.
A derivation also imposes in some sense a hierarchical structure on the string that is derived. For example the structure of the string "1 + 1 + 1" would, according to the leftmost derivation, be:
S /\ /  \ /  \ S '+' S /\  /  \  S '+' S '1'   '1' '1'
This tree is called a concrete syntax tree (see also abstract syntax tree) of the string. In this case the presented leftmost and the rightmost derivation define the same syntax tree, however there is another (leftmost) derivation of the same string possible
S /\ /  \ /  \ S '+' S  /\  /  \ '1' S '+' S   '1' '1'
If for certain strings in the language of the grammar there are more than one parsing trees then the grammar is said to be an ambiguous grammar. Such grammars are usually hard to parse because the parser cannot always decide which grammar rule it has to apply.
Every contextfree grammar which does not generate the empty string can be transformed into an equivalent one in Chomsky Normal Form or Greibach normal form. "Equivalent" here means that the two grammars generate the same language.
Because of the especially simple form of production rules in Chomsky Normal Form grammars, this normal form has both theoretical and practical implications. For instance, one can use the Chomsky Normal Form to construct for every contextfree language a polynomial algorithm which decides whether a given string is in the language or not (the CYK algorithm).
Properties of contextfree languages
An alternative and equivalent definition of contextfree languages employs nondeterministic pushdown automata: a language is contextfree if and only if it can be accepted by such an automaton.
The union and concatenation of two contextfree language is contextfree; the intersection need not be. The reverse of a contextfree language is contextfree, but the complement need not be contextfree. Every regular language is contextfree because it can be described by a regular grammar. The intersection of a contextfree language and a regular language is always contextfree. There exist contextsensitive languages which are not contextfree. To prove that a given language is not contextfree, one employs the pumping lemma for contextfree languages.
Search Encyclopedia

Featured Article
