A Context-Free Grammar (CFG) is a formal grammar that describes the syntax of a programming language or other formal languages. It was introduced by Noam Chomsky and is a type of phrase structure grammar. A CFG consists of a set of production rules that define how strings of symbols can be generated.
A context-free grammar is defined by four components:
A set of terminal symbols (Σ):
- These are the basic symbols of the language that appear in the strings that are generated. Terminal symbols are the actual symbols of the language.
A set of non-terminal symbols (N):
- These are placeholders for patterns of terminal symbols. Non-terminal symbols represent syntactic categories.
A set of production rules (P):
- These rules specify how the non-terminal symbols can be replaced by sequences of terminal and/or other non-terminal symbols. Each production rule is of the form A → β, where A is a non-terminal symbol, and β is a sequence of terminal and/or non-terminal symbols.
A start symbol (S):
- This is a special non-terminal symbol from which the derivation of the language's strings begins.