Context-free grammar
Context-free grammar is a formal grammar that is used to generate all possible strings in a given
formal language.
Context free grammar G can be defined by four tuples as:
1. G= (V, T, P, S)
Where,
G describes the grammar
T describes a finite set of terminal symbols. It is denoted by lowercase letters.
V describes a finite set of non-terminal symbols It is denoted by capital letters.
P describes a set of production rules
S is the start symbol.
In CFG, the start symbol is used to derive the string. You can derive the string by repeatedly replacing
a non-terminal by the right hand side of the production, until all non-terminal have been replaced by
terminal symbols.
Capabilities of CFG
• There are the various capabilities of CFG:
• Context-free grammar is useful to describe most of the programming languages.
• If the grammar is properly designed, then an efficient parser can be constructed
• automatically.
• Using the features of associatively & and precedence information, suitable grammars for
expressions can be constructed.
• Context-free grammar is capable of describing nested structures like balanced parentheses,
matching begin-end, corresponding if-then-else's, and so on.
