Context Free Grammar
(CFG)
Tutorial 04
CSCI415 – Compiler Design
Announcement
Quiz 01 Next Week !!
Includes:
➢ Tutorial 2: Lexical Analysis
➢ Tutorial 3: DFA Methods (Equivalence and State
Elimination Methods)
➢ Tutorial 4: Context Free Grammar
Duration: 30 mins.
You must take the quiz in your registered slot.
CSCI415 – Compiler Design
What is Context-Free Grammar?
➢ It is a formal method for defining languages named as
“Backus-Naur Form” (BNF) notation.
➢ Can describe languages that has recursive features
➢ Abbreviated as CFG
➢ More powerful than Regex
➢ Has many applications:
➢ Study of human languages
➢ Parsing and Compilation of programming languages
CSCI415 – Compiler Design
How to write CFG?!
CFGs consist of Productions S → 0Z1 | 1T1
where we say Grammar G has Z→0|1
the following productions/rules T → 01 | ε
CSCI415 – Compiler Design
How to write CFG?!
CFGs consist of Productions S → 0Z1 | 1T1
Productions consist of
Z→0|1
❑ Terminals (∑)
T → 01 | ε
CSCI415 – Compiler Design
How to write CFG?!
CFGs consist of Productions S → 0Z1 | 1T1
Productions consist of
Z→0|1
❑ Terminals (∑)
T → 01 | ε
❑ Non-terminals (Variables)
CSCI415 – Compiler Design
How to write CFG?!
For Kleene Star (‘*’)
In BNF, recursion is different from that in Regex = a*
regular expressions. A → Aa | ε
Neither ‘*’ nor ‘+’ are used in CFG, they --or—
are replaced by production rules. A → aA | ε
Notice: The only operators used here are the CONCATENATION and OR
CSCI415 – Compiler Design
How to write CFG?!
For Kleene Star (‘+’)
In BNF, recursion is different from that in Regex = a+
regular expressions. A → Aa | a
Neither ‘*’ nor ‘+’ are used in CFG, they --or—
are replaced by production rules. A → aA | a
Notice: The only operators used here are the CONCATENATION and OR
CSCI415 – Compiler Design
BNF Recursion Forms
Left recursion
The non-terminal A appears as the first symbol on the right-hand
side of the rule defining A
A→Aa|a
Right recursion
The non-terminal A appears as the last symbol on the right-hand
side of the rule defining A
A→aA|a
CSCI415 – Compiler Design
Example 1
Construct the CFG for this regex a [a-z]* a | a
S → aBa | a
B → CB | ε
C→a|b|c|d|e|f|g|h|i|j|k|l|m|n
|o|p|q|r|s|t|u|v|w|x|y|z
CSCI415 – Compiler Design
Example 2
Construct the CFG for this regex (a | b)* | ab (a | b)*
A → B | abB
B → aA | bA | ε
CSCI415 – Compiler Design
Example 3
Construct the CFG for the following language.
∑ = {0, 1}, where the length of w is odd and its middle symbol is 0
X → 0X0 | 1X1 | 1X0 | 0X1 | 0
CSCI415 – Compiler Design
Example 4
Construct the CFG for the following language.
∑ = {0, 1}, starts and ends with the same symbol
Z → 0X0 | 1X1 | 0 | 1
X → 0X | 1X | ε
CSCI415 – Compiler Design
Example 5
Construct the CFG for the following language.
∑ = {0, 1}, starts with 0 and has odd length OR starts with 1 and has even length
S → 0T | 1Z
T → 00T | 01T | 10T | 11T | ε
Z → 00Z | 01Z | 10Z | 11Z | 0 | 1
CSCI415 – Compiler Design
Derivation
We derive strings in the language of a
CFG by starting with the start symbol and
repeatedly replacing some variable A by
the right side of one of its productions.
CSCI415 – Compiler Design
Example 6
Given the following grammar, show how the string “00#11” will be generated.
A → 0A1 | B Derivation
B→# A → 0A1
=> 00A11
=> 00B11
=> 00#11 Generated
CSCI415 – Compiler Design
Example 7
Given the grammar write down the leftmost derivations and parse trees for the
following expressions: 3+4*5-6
Exp → Exp AddOp Term | Term
AddOp → + | -
Term → Term Mulop Factor | Factor
Mulop → *
Factor → (Exp) | number
CSCI415 – Compiler Design
Example 7 – Cont.
Derivation 3 + Factor Mulop Factor AddOp Term
Exp → Exp AddOp Term 3 + 4 Mulop Factor AddOp Term
Exp AddOp Term AddOp Term 3 + 4 * Factor AddOp Term
Term AddOp Term AddOp Term 3 + 4 * 5 AddOp Term
Term AddOp Term AddOp Term 3 + 4 * 5 – Term
Factor AddOp Term AddOp Term 3 + 4 * 5 – Factor
3 AddOp Term AddOp Term 3+4*5-6 Generated
Exp → Exp AddOp Term | Term
3 + Term AddOp Term AddOp → + | -
3 + Term Mulop Factor AddOp Term Term → Term Mulop Factor | Factor
Mulop → *
Factor → (Exp) | number
CSCI415 – Compiler Design
Example 7 – Cont.
Exp → Exp AddOp Term | Term
AddOp → + | -
Term → Term Mulop Factor | Factor
Mulop → *
Factor → (Exp) | number
Generated
CSCI415 – Compiler Design
Example 8
Given the grammar write down the leftmost derivations and parse trees for the
following expressions: 3*(4-5+6)
Exp → Exp AddOp Term | Term
AddOp → + | -
Term → Term Mulop Factor | Factor
Mulop → *
Factor → (Exp) | number
CSCI415 – Compiler Design
Example 8 – Cont.
Derivation 3 * (number AddOp Term AddOp Term)
Exp → Term 3 * (4 AddOp Term AddOp Term)
Term Mulop Factor 3 * (4 – Term AddOp Term)
Factor Mulop Factor 3 * (4 – Factor AddOp Term)
number Mulop Factor 3 * (4 – number AddOp Term)
3 Mulop Factor 3 * (4 – 5 AddOp Term)
3 * Factor 3 * (4 – 5 + Term)
3 * (Exp) 3 * (4 – 5 + Factor)
3 * (Exp AddOp Term) 3 * (4 – 5 + number)
3 * (Exp AddOp Term AddOp Term) 3 * (4 – 5 + 6) Exp → Exp AddOp Term | Term
3 * (Term AddOp Term AddOp Term)
Generated AddOp → + | -
Term → Term Mulop Factor | Factor
3 * (Factor AddOp Term AddOp Term) Mulop → *
CSCI415 – Compiler Design Factor → (Exp) | number
Example 8 – Cont.
Exp → Exp AddOp Term | Term
AddOp → + | -
Term → Term Mulop Factor | Factor
Mulop → *
Factor → (Exp) | number
Generated
CSCI415 – Compiler Design
Ambiguous Grammar
A grammar is called ambiguous grammar
if it generates two different parse trees or
derivations for the same string.
Note that ambiguity is a property of the GRAMMAR not the language.
CSCI415 – Compiler Design
Example 9
The following grammar generates all regular expressions over the alphabet of
letters (we have used quotes to surround operators, since the vertical bar is an
operator as well as a metasymbol)
Rexp → Rexp “|” Rexp
o Give a derivation for the regular
| Rexp Rexp
expression (ab | b)* using this
| Rexp * grammar
|”(“ Rexp “)” o Show that this grammar is
| letter ambiguous
CSCI415 – Compiler Design
Rexp → Rexp “|” Rexp
| Rexp Rexp
Example 9 – Solution | Rexp *
|”(“ Rexp “)”
Derivation | letter
Rexp → Rexp*
(Rexp)*
(Rexp | Rexp)*
(Rexp Rexp | Rexp)*
(letter Rexp | Rexp)*
(a Rexp | Rexp)*
(a letter | Rexp)*
(ab | Rexp)*
(ab | letter)*
(ab | b)*
Generated
CSCI415 – Compiler Design
Thank
You