Context Free Grammar/Grammar consists of terminals,
non-terminals, a start symbol and productions
A Context Free Grammar(CFG) is used to generate patterns of
strings
A Context Free Grammar G is a quadruple (V,T,P,S) where
V is
set of non-terminals
T is
set of Terminals (V ∩∑= Ø)
P is
Production rules (P: V→(V∪∑)*)
S is A
start symbol
It is a set of recursive rewriting rules (or Productions)
A CFG is defined by a set of productions, each production is
of the form
X
→
β
Where
X is a
single non-terminal symbol, representing a set of phrases in the language
β is a sequence of terminal and non-terminal
symbols
A CFG Consists of the following components
- A set of terminal symbols. They are the characters of alphabet which appear in the strings that are generated by the grammar
- A set of non-terminal symbols: They are the place holders for patterns of terminal symbols which can be generated by the non-terminal symbols
- A set of productions: They are the rules for replacing or rewriting, the non-terminal symbols that are present on the left side of the production in a string, with other non-terminal or terminal symbols present on the right side of the production
- A Start symbol: It is a special non-terminal symbol that appears in the initial string which is generated by the grammar
Example of CFG
Strings of Terminals
|
Lower case letters, digits, punctuation
|
Non Terminals
|
Upper Case Letters
|
Arbitary Terminasls / Non-Terminasls
|
X,Y,Z
|
Strings of Terminals
|
u,v,w
|
Strings of Terminasls/non-terminals
|
µ,β,Ƴ
|
Start Symbol
|
S
|
To generate a string of terminal symbols from a CFG,
- Start with a string that consists the start symbol;
- Apply one of the productions with the start symbol on the left hand side, replacing the start symbol with the right hand side of the production;
- The process of selecting non-terminal symbols in the string has to be repeated, and they have to be replaced with the right hand side of some corresponding production. The process has to be repeated until all non-terminals are replaced by terminal symbols
