A context-free grammar is:
They are the type 2 of the Chomsky grammar hierarchy.
Context-free grammars :
DTD’s taken as a whole, are really CFG’s.
Context-free grammars are used to put a tree structure on strings, typically text strings.
In context-free grammars, all rules are:
These rules can be applied regardless of context.
In a context free grammar, each (production|grammar) rule has :
In context-free grammars, terminal symbols never appear on the left hand side of a production rule
Starting from a sentence consisting of a single distinguished nonterminal, called the goal symbol, a given context-free grammar specifies a language, namely, the (perhaps infinite) set of possible sequences of terminal symbols that can result from repeatedly replacing any nonterminal in the sequence with a right-hand side of a production for which the nonterminal is the left-hand side.
Rules can be applied in reverse to check if a string is grammatically correct according to the grammar.
Syntactic equations of the form defined in EBNF generate context-free languages.
The term context free is due to Chomsky and stems from the fact that substitution of:
is always permitted, regardless of the context in which the symbol is embedded within the sentence.
It has turned out that this restriction to context freedom (in the sense of Chomsky) is quite acceptable for programming languages, and that it is even desirable.
A CFG consists of the following components:
To generate a string of terminal symbols from a CFG, we: