You are here: irt.org | FOLDOC | context-free grammar
<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.
(2014-11-24)
Nearby terms: context « context clash « COntext Dependent Information Language « context-free grammar » context-sensitive menu » context switch » Contextually Communicating Sequential Processes
FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL