• Formal grammar that generates all possible patterns of strings in Finite Language.

• It is denoted using 4-tuple G=(V,T,P,S)

1. V→Finite set of symbols - non terminals or variables

2. T→Set of symbols - terminals

3. P→Set of productions 

4. S→Start symbol

• Every language has a grammar

• Tokens generated by Lexical Analyzer are considered as terminals.

• Parser obtains a string of tokens from Lexical Analyzer and verifies whether it can be generated by the grammar for the source language or not

Example:

G=({s}, {a,b}, P, S)
P={S→aSa, S→bSb, S→∈}
Perform syntax analysis of abba

Solution:

If this string can be generated by the grammar then it is syntactically correct
S→aSa
→abSba
→abba

Example1:

Construct CFG for the language having  any no of a’s over the set Σ ={a}
Σ  = {a}
L={∈,aa,aaa,aaaa,.....}
R.E =a*

Production rule
S→aS
S→∈

Now, Derive aaaaaa for this production
S→aS
S→aaS
S→aaaS
S→aaaaS
S→aaaaaS
S→aaaaaaS
S→aaaaaa

Example 2:

Construct a CFG for the language having L={w cwR | w∈(a,b)}
L={aacaa, bcb, aabcabb, abbcbba,......}
S→aSsa
S→bSb
S→c

Example 3:

Construct a CFG for the lang L=anb2n where n ≥1
n=3
L={abb, aabbbb, aaabbbbbb,......}
S→aSbb
S→abb

Grammar for Arithmetic Expressionx:

expr→expr+term
expr→expr - term
expr →term
term→term*factor
term→term/factor
term→factor
factor→(expr) 
factor→id

This can be simplified and represented as,

E→E+T|E-T|T
T→T*F| T/F |F
F→(E)|id

This can be further represented as E→E+E| E*E |(E) | id