context-free grammar

A Dictionary of Computing | 2004 | 700+ words | Copyright

context-free grammar A grammar in which the left-hand side of each production is a single nonterminal, i.e. productions have the form A → α

(read as rewrite A as α), where α is a string of terminals and/or nonterminals. These productions apply irrespective of the context of A. For brevity one writes A → α₁ | α₂ | .. .. | α _n

to indicate the separate productions A → α₁, A → α₂, .., .., A → α_n

As an example, the following generates a simple class of arithmetic expressions typified by (a + b) × c:

E → T | T + E | (E)

T → E | E × T | a | b | c

The BNF notation used in defining the syntax of programming languages is simply a context-free grammar.

Context-free grammars are a class of phrase-structure grammar (PSG). GPSG represents the principal attempt at constructing context-free grammars capable of characterizing the grammars of natural language.

Compare context-sensitive grammar.

Cite this article
Pick a style below, and copy the text for your bibliography.

MLA
Chicago
APA

JOHN DAINTITH. "context-free grammar." A Dictionary of Computing. 2004. Encyclopedia.com. 27 May. 2012 <http://www.encyclopedia.com>.

JOHN DAINTITH. "context-free grammar." A Dictionary of Computing. 2004. Encyclopedia.com. (May 27, 2012). http://www.encyclopedia.com/doc/1O11-contextfreegrammar.html

JOHN DAINTITH. "context-free grammar." A Dictionary of Computing. 2004. Retrieved May 27, 2012 from Encyclopedia.com: http://www.encyclopedia.com/doc/1O11-contextfreegrammar.html

Learn more about citation styles