Context-Free Grammar

OUTLINE
• Context-Free Grammar Introduction
• Derivation Tree/Parse Tree
• Sentential Form and Partial Derivation
Tree
• Types of Derivation Tree
• Left and Right Recursive Grammars
• Ambiguity in Context-Free Grammars
• CFG Simplification
 Context-Free Grammar Introduction
Grammar: Grammar is a set of rules which check whether a string belong to a
particular language or not.

Context-Free Grammar:
• It is a notation used to specify the syntax of language.
• Context free grammar are used to design parser.
Definition: A context-free grammar (CFG) consisting of a finite set of grammar rules is
a quadruple (N, T, P, S) where
• N is a set of non-terminal symbols.
• T is a set of terminals where N ∩ T = NULL.
• P is a set of rules, P: N → (N U T)*, i.e., the left-hand side of the production rule P does
have
any right context or left context.
• S is the start symbol.

Example
• The grammar ({A}, {a, b, c}, P, A), P : A → aA, A → abc.
• The grammar ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε
• The grammar ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε
 Derivation Tree/Parse Tree
Generation of Derivation Tree
A derivation tree or parse tree is an ordered rooted tree that graphically represents
the
semantic information a string derived from a context-free grammar.

Representation Technique:
1. Root vertex: Must be labeled by the start symbol.
2. Vertex: Labeled by a non-terminal symbol.
3. Leaves: Labeled by a terminal symbol or ε.
If S → x1x2 …… xn is a production rule in a CFG, then the parse tree / derivation tree
will be as follows:
There are two different approaches to draw a derivation tree:

1. Top-down Approach:
(a) Starts with the starting symbol S
(b) Goes down to tree leaves using productions

2. Bottom-up Approach:
(c) Starts from tree leaves
(d) Proceeds upward to the root which is the starting symbol S
 Derivation or Yield of a Tree
The derivation or the yield of a parse tree is the final string obtained by concatenating
the labels of the leaves of the tree from left to right, ignoring the Nulls. However, if all
the leaves are Null, derivation is Null.
Example
Let a CFG {N,T,P,S} be
N = {S}, T = {a, b}, Starting symbol = S, P = S → SS | aSb | ε
One derivation from the above CFG is “abaabb”
Answer
S → SS
S → aSbS (replace S →aSb)
S →abS (replace S →ε)
S→ (replace S →aSb)
abaSb (replace S
S → abaaSbb →aSb) (replace
S→ abaabb S →ε)
 Sentential Form and Partial Derivation Tree
A partial derivation tree is a sub-tree of a derivation tree/parse tree such that either all
of
its children are in the sub-tree or none of them are in the sub-tree.

Example
If in any CFG the productions are:
S → AB, A → aaA | ε, B →Bb| ε
the partial derivation tree can be the following:

If a partial derivation tree contains the root S, it is called a sentential form. The
 Types of Derivation Tree
Leftmost and Rightmost Derivation of a String
1. Leftmost derivation - A leftmost derivation is obtained by applying production to
the leftmost variable in each step.

2. Rightmost derivation - A rightmost derivation is obtained by applying production

to the rightmost variable in each step.
Example
Let any set of production rules in a CFG
be X → X+X | X*X |X| a
over an alphabet {a}.
Find the leftmost derivation for the string
"a+a*a“.
Answer:
X→
X+X
X→ a+X
X→ a+ X*X
X→a+a*X
X→ a+a*a
Example
Let any set of production rules in a CFG
be X → X+X | X*X |X| a
over an alphabet {a}.
Find the Rightmost derivation for the
string
"a+a*a“.

Answer:

X → X*X
X→ X*a
X → X+X*a
X →X+a*a
X→ a+a*a
Example:
Consider the following grammar
S → bB/Aa
A→b/ bs/ aAA
B → a/ aS/ Bbb
Find:
Leftmost and right most
derivation For string baababa
and Also find derivation tree
 Left and Right Recursive Grammars
In a context-free grammar G, if there is a production in the form X → Xa where X is a non-
terminal and ‘a’ is a string of terminals, it is called a left recursive production. The grammar
having a left recursive production is called a left recursive grammar.

And if in a context-free grammar G, if there is a production is in the form X → aX where X is a

non-terminal and ‘a’ is a string of terminals, it is called a right recursive production. The grammar
having a right recursive production is called a right recursive grammar.
 Ambiguity in Context-Free Grammars
If a context free grammar G has more than one derivation tree for some string w ∈ L(G), it is
called an ambiguous grammar. There exist multiple right-most or left-most derivations for some
string generated from that grammar.
Problem
Check whether the grammar G with production rules:
X → X+X | X*X |X| a
is ambiguous or not.
Solution
Let’s find out the
derivation tree for the
string "a+a*a". It has
two derivations.
Derivation 1: "a+a*a", the grammar G is ambiguous
X → X+X Derivation 2:
X→ a +X X → X*X
X→ a+ X*X X→X+X*X
X →a+a*X X→ a+ X*X
X→ a+a*a X →a+a*X
Parse tree1: X→
a+a*a
Parse tree
2:

Since there are two parse trees for a single

 CFG Simplification
In a CFG, it may happen that all the production rules and symbols are not needed for
the derivation of strings. Besides, there may be some null productions and unit
productions. Elimination of these productions and symbols is called simplification of
CFGs.
Simplification essentially comprises of the following steps:
Reduction of CFG
Removal of Unit Productions
Removal of Null Productions
 Reduction of CFG
CFGs are reduced in two phases:

Phase 1: Derivation of an equivalent grammar, G’, from the CFG, G, such that each variable
derives some terminal string.
Derivation Procedure:
Step 1: Include all symbols, W1, that derive some terminal and initialize i=1.
Step 2: Include all symbols, Wi+1, that derive Wi.
Step 3: Increment i and repeat Step 2, until Wi+1 = Wi.
Step 4: Include all production rules that have Wi in it.
Phase 2:
Derivation of an equivalent grammar, G”, from the CFG, G’, such that each symbol appears in a
sentential form.
Derivation Procedure:
Step 1: Include the start symbol in Y1 and initialize i = 1.
Step 2: Include all symbols, Yi+1, that can be derived from Yi and include all production rules
that have been applied.
Step 3: Increment i and repeat Step 2, until Yi+1 = Yi.
Problem
Find a reduced grammar equivalent to the grammar G, having production rules,
P: S AC | B, A  a, C  c | BC, E  aA | e
Solution
Phase 1:
T = { a, c, e }
W = { A, C, E } from rules A  a, C  c and E 
1

aA W = { A, C, E } U { S } from rule S  AC
2

W = { A, C, E, S } U 
3

Since W = W , we can derive G’ as:

2 3

G’ = { { A, C, E, S }, { a, c, e }, P, {S}}
where P: S  AC, A  a, C  c , E  aA | e
Phase 2:
Y={S}
1

Y = { S, A, C } from rule S  AC
2

Y = { S, A, C, a, c } from rules A  a and C  c

3

Y = { S, A, C, a, c }
4

Since Y = Y , we can derive G” as:

3 4

G” = { { A, C, S }, { a, c }, P, {S}}
where P: S  AC, A  a, C  c
 Removal of Unit
productions
Any production rule
production.
in the form A → B where A, B ∈ Non-terminal is called unit

Removal Procedure:
Step 1: To remove A→B, add production A → x to the grammar rule whenever B → x
occurs in the grammar. [x ∈ Terminal, x can be Null]
Step 2: Delete A→B from the grammar.
Step 3: Repeat from step 1 until all unit productions are removed.
Problem
Remove unit production from the following:
S → XY, X → a, Y → Z | b, Z → M, M → N, N → a
Solution:
There are 3 unit productions in the
grammar: Y → Z, Z → M, and M → N
At first, we will remove M → N.
As N → a, we add M → a, and M → N is removed.
The production set becomes
S → XY, X → a, Y → Z | b, Z → M, M → a, N →
a
Now we will remove Z → M.
As M → a, we add Z→ a, and Z → M is removed.
The production set becomes
Now we will remove Y → Z.
As Z → a, we add Y→ a, and Y → Z is
removed. The production set becomes
S → XY, X → a, Y → a | b, Z → a, M → a, N →
a
Now Z, M, and N are unreachable, hence we can
remove those.
The final CFG is unit production
free: S → XY, X → a, Y → a | b
 Removal of Null
Productions
In a CFG, a non-terminal symbol ‘A’ is a nullable variable if there is a production A → ϵ or
there is a derivation that starts at A and finally ends up with
ϵ:A → .......… → ϵ
Removal Procedure:
Step1 Find out nullable non-terminal variables which derive ϵ.
Step2 For each production A → a, construct all productions A → x where x is
obtained from ‘a’ by removing one or multiple non-terminals from Step 1.
Step3 Combine the original productions with the result of step 2 and remove ϵ-
productions.
Problem
Remove null production from the
following: S→ASA | aB | b, A → B, B → b
|ϵ
Solution:
There are two nullable variables: A and B
At first, we will remove B → ϵ.
After removing B → ϵ,the production set becomes:
S→ASA | aB | b | a, A → B| b | ϵ,B → b

Now we will remove A → ϵ.

After removing A → ϵ,the production set becomes:
S→ASA | aB | b | a | SA | AS | S, A → B| b, B → b
This is the final production set without null
transition.