Context-free grammar

related topics
{math, number, function}
{language, word, form}
{company, market, business}

In formal language theory, a context-free grammar (CFG), sometimes also called a phrase structure grammar, is a grammar that naturally generates a formal language in which clauses can be nested inside clauses arbitrarily deeply, but where grammatical structures are not allowed to overlap. CFG are expressed by Backus–Naur Form, or BNF. In terms of production rules, every production of a context free grammar is of the form

where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). These rewriting rules applied successively produce a parse tree, where the nonterminal symbols are nodes, the leaves are the terminal symbols, and each node expands by the production into the next level of the tree. The tree describes the nesting structure of the expression. V can therefore change while w is fixed (can't change).

In a context free grammar the left hand side of a production rule is always a single nonterminal symbol. In a general grammar, it could be a string of terminal and/or nonterminal symbols. The grammars are called context free because – since all rules only have a nonterminal on the left hand side – one can always replace that nonterminal symbol with what is on the right hand side of the rule. The context in which the symbol occurs is therefore not important.

Context-free languages are exactly those which can be understood by a finite state computer with a single infinite stack. In order to keep track of nested units, one pushes the current parsing state at the start of the unit, and one recovers it at the end.

Context-free grammars play a central role in the description and design of programming languages and compilers. They are also used for analyzing the syntax of natural languages. Noam Chomsky has posited that all human languages are based on context-free grammars at their core, with additional processes that can manipulate the output of the context-free component (the transformations of early Chomskyan theory)[citation needed].


Full article ▸

related documents
Linear independence
Probability density function
Glossary of topology
Euclidean algorithm
Heine–Borel theorem
Axiom schema of replacement
Type theory
Homology (mathematics)
Goldbach's conjecture
Pushdown automaton
Presentation of a group
Breadth-first search
Chaitin's constant
Binary relation
Abstract interpretation
Random variable
Wiener process
E (mathematical constant)
Euclidean space
Algebraic structure
Linear combination
Natural number
Dijkstra's algorithm
Ideal class group
Euler characteristic
IEEE 754-1985
Elliptic curve