context-free grammar

Quick Reference

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 → α1 | α2 | .. | αn to indicate the separate productions A → α1, A → α2, .,., 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.

A → α

A → α1 | α2 | .. | αn

A → α1, A → α2, .,., A → αn

E → T | T + E | (E)

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

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.

Subjects: Computing.

Reference entries