context-free grammar from FOLDOC

CFG ⇝

context-free grammar

(CFG) A grammar where the syntax of each constituent (syntactic category or terminal symbol) is independent of the symbols occuring before and after it in a sentence. A context-free grammar describes a context-free language.

Context-free grammars can be expressed by a set of "production rules" or syntactic rules. For example, a language with symbols "a" and "b" that must occur in unequal numbers can be represented by the CFG:

 S → U | V
 U → TaU | TaT | UaT
 V → TbV | TbT | VbT
 T → aTbT | bTaT | ε

meaning the top-level category "S" consists of either a "U" or a "V" and so on. The special category "ε" represents the empty string. This grammar is context-free because each rule has a single symbol on its left-hand side.

Parsers for context-free grammars are simpler than those for context-dependent grammars because the parser need only know the current symbol.

Algol was (one of?) the first languages whose syntax was described by a context-free grammar. This became a common practice for programming languages and led to the notation for grammars called Backus-Naur Form.

Last updated: 2014-11-24

Nearby terms:

COntext Dependent Information Language ♦ context-free grammar ♦ context-sensitive menu

Try this search on Wikipedia, Wiktionary, Google, OneLook.