Compiler Construction
(CS-342)
Lecture # 10 – Part 03
Course Instructor: M. Ramzan Shahid Khan
Department of Computer Science,
Namal University Mianwali
Fall Semester, 2024
Topics
• Rewriting Rules (Removing Ambiguity)
• How to convert Ambiguous Grammar into Unambiguous Grammar
2
Ambiguous Grammar
• Ambiguity is the property of the Grammar Not
Language.
• Languages cannot be Ambiguous
• Grammars written for Languages can be
Ambiguous
3
Ambiguous Grammar – Problems
1. Associativity
• Scenario: Operators of same precedence must solve from left to
right
• E.g., String: 𝑎 − 𝑏 − 𝑐
• Grammar
𝑋 = 𝑋 + 𝑋 𝑋 − 𝑋 𝑋 ∗ 𝑋|𝑋/𝑋|𝑣𝑎𝑟|𝑐𝑜𝑛𝑠𝑡
4
• String: 𝑎 − 𝑏 − 𝑐
• Grammar
𝑋 = 𝑋 + 𝑋 𝑋 − 𝑋 𝑋 ∗ 𝑋|𝑋/𝑋|𝑣𝑎𝑟|𝑐𝑜𝑛𝑠𝑡
X X
x - x x - x
x - x var var x - x
var var var var
Correct: Left Associative Wrong: Right Associative
𝒂−𝒃 −𝒄 𝒂− 𝒃−𝒄 =𝒂−𝒃+𝒄
5
Ambiguous Grammar – Problems
2. Precedence of the Operator
• Scenario: Multiplication must be performed before Addition
• E.g., String: 𝑥 + 𝑦 ∗ 𝑧
• Grammar
𝐸𝑥𝑝 → 𝐸𝑥𝑝 𝑂𝑝 𝐸𝑥𝑝 | 𝐼𝐷
𝑂𝑝 → +| − | ∗ |/
𝐼𝐷 → 𝑥|𝑦|𝑧
6
• String: 𝑥+𝑦∗𝑧
• Grammar
𝐸𝑥𝑝 → 𝐸𝑥𝑝 𝑂𝑝 𝐸𝑥𝑝 | 𝐼𝐷
𝑂𝑝 → +| − | ∗ |/
𝐼𝐷 → 𝑥|𝑦|𝑧
Exp Exp
Exp Op Exp Exp Op Exp
Exp Op Exp Exp Op Exp * ID
ID +
ID * ID ID + ID
x z
x y
y z
Correct: Wrong:
𝐱 + (𝒚 ∗ 𝒛) 𝒙+𝒚 ∗𝒛
7
Ambiguous Grammar
• We can remove ambiguity through Rewriting Rules
• No Solid Algorithm
• But still few solutions are available
• Most of the Ambiguous Grammars cannot be converted
into Unambiguous Grammars and they are known as
Inherently Ambiguous Grammars
8
Ambiguous Grammar
• We can remove ambiguity through Rewriting Rules
• Associativity can be corrected through
• Left-Recursive Grammar
• Precedence can be corrected through
• Levels
9
Associativity - Left-Recursive Grammars
• Left Side non-terminal appears on First Position
of Right Side i.e. Left of Right Side
• Example:
𝑿→𝑿+𝑌
𝑺→𝑺
10
• String: 𝑎 − 𝑏 − 𝑐
• Grammar
𝑋 = 𝑋 + 𝑋 𝑋 − 𝑋 𝑋 ∗ 𝑋|𝑋/𝑋|𝑣𝑎𝑟|𝑐𝑜𝑛𝑠𝑡
X X
x - x x - x
x - x var var x - x
var var var var
Correct: Left Associative Wrong: Right Associative
𝒂−𝒃 −𝒄 𝒂− 𝒃−𝒄 =𝒂−𝒃+𝒄
11
Ambiguous to Unambiguous - Left Recursive
• Convert the given grammar into Left Recursive
• Allow only Left derivation of the grammar
• Restrict Right derivation
• Grammar
𝐸𝑥𝑝 → 𝐸𝑥𝑝 𝑂𝑝 𝐸𝑥𝑝
𝐸𝑥𝑝 → 𝐼𝐷
𝑂𝑝 → +| − | ∗ |/
𝐼𝐷 → 𝑥|𝑦|𝑧
12
Left Recursive or Left Associative
1st Level:
𝐸𝑥𝑝 → 𝐸𝑥𝑝 𝑂𝑝 𝐸𝑥𝑝 𝐸𝑥𝑝 → 𝐸𝑥𝑝 + 𝑇𝑒𝑟𝑚
𝐸𝑥𝑝 → 𝐼𝐷 𝐸𝑥𝑝 → 𝐸𝑥𝑝 − 𝑇𝑒𝑟𝑚
𝑂𝑝 → +| − | ∗ |/ 𝐸𝑥𝑝 → 𝑇𝑒𝑟𝑚
𝐼𝐷 → 𝑥|𝑦|𝑧
2nd Level:
𝑇𝑒𝑟𝑚 → 𝑇𝑒𝑟𝑚 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟
𝑇𝑒𝑟𝑚 → 𝑇𝑒𝑟𝑚/𝐹𝑎𝑐𝑡𝑜𝑟
𝑇𝑒𝑟𝑚 → 𝐹𝑎𝑐𝑡𝑜𝑟
3rd Level:
𝐹𝑎𝑐𝑡𝑜𝑟 → 𝑥|𝑦|𝑧
13
Left Associative and Precedence - Satisfied
𝐸𝑥𝑝 → 𝐸𝑥𝑝 + 𝑇𝑒𝑟𝑚
𝐸𝑥𝑝 → 𝐸𝑥𝑝 𝑂𝑝 𝐸𝑥𝑝 𝐸𝑥𝑝 → 𝐸𝑥𝑝 − 𝑇𝑒𝑟𝑚
𝐸𝑥𝑝 → 𝐼𝐷 𝐸𝑥𝑝 → 𝑇𝑒𝑟𝑚
𝑂𝑝 → +| − | ∗ |/ 𝑇𝑒𝑟𝑚 → 𝑇𝑒𝑟𝑚 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟
𝐼𝐷 → 𝑥|𝑦|𝑧 𝑇𝑒𝑟𝑚 → 𝑇𝑒𝑟𝑚/𝐹𝑎𝑐𝑡𝑜𝑟
𝑇𝑒𝑟𝑚 → 𝐹𝑎𝑐𝑡𝑜𝑟
𝐹𝑎𝑐𝑡𝑜𝑟 → 𝑥|𝑦|𝑧
14
Left Associative and Precedence - Satisfied
𝐸𝑥𝑝 → 𝐸𝑥𝑝 + 𝑇𝑒𝑟𝑚 𝐸𝑥𝑝 → 𝐸𝑥𝑝 + 𝑇𝑒𝑟𝑚 𝐸𝑥𝑝 → 𝑇𝑒𝑟𝑚
𝐸𝑥𝑝 → 𝐸𝑥𝑝 − 𝑇𝑒𝑟𝑚 ⇒ 𝑇𝑒𝑟𝑚 + 𝑇𝑒𝑟𝑚 ⇒ 𝑇𝑒𝑟𝑚
𝐸𝑥𝑝 → 𝑇𝑒𝑟𝑚 ⇒ 𝐹𝑎𝑐𝑡𝑜𝑟 + 𝑇𝑒𝑟𝑚 No other
𝑇𝑒𝑟𝑚 → 𝑇𝑒𝑟𝑚 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟 ⇒ 𝑥 + 𝑇𝑒𝑟𝑚 way of Left
𝑇𝑒𝑟𝑚 → 𝑇𝑒𝑟𝑚/𝐹𝑎𝑐𝑡𝑜𝑟 ⇒ 𝑥 + 𝑇𝑒𝑟𝑚 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟 Derivation
𝑇𝑒𝑟𝑚 → 𝐹𝑎𝑐𝑡𝑜𝑟 ⇒ 𝑥 + 𝐹𝑎𝑐𝑡𝑜𝑟 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟 Possible!
𝐹𝑎𝑐𝑡𝑜𝑟 → 𝑥|𝑦|𝑧 ⇒ 𝑥 + 𝑦 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟
⇒𝑥+𝑦∗𝑧
String: 𝒙+𝒚∗𝒛
15
𝐸𝑥𝑝 → 𝐸𝑥𝑝 + 𝑇𝑒𝑟𝑚
⇒ 𝑇𝑒𝑟𝑚 + 𝑇𝑒𝑟𝑚
⇒ 𝐹𝑎𝑐𝑡𝑜𝑟 + 𝑇𝑒𝑟𝑚
⇒ 𝑥 + 𝑇𝑒𝑟𝑚
⇒ 𝑥 + 𝑇𝑒𝑟𝑚 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟
⇒ 𝑥 + 𝐹𝑎𝑐𝑡𝑜𝑟 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟
⇒ 𝑥 + 𝑦 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟
⇒𝑥+𝑦∗𝑧
Exp
Exp + Term
Term Term * Factor
Factor z
Factor
y
Correct:
𝐱 + (𝒚 ∗ 𝒛)
x
16
Unambiguous Grammar
• Only one Parse Tree is possible
• Parse Tree is constructed on the basis of derivation
17
Ambiguous to Unambiguous - Example
• Set of Alphabets Σ = {0, … , 9, +,∗, (, )}
• Grammar
𝐸→𝐼
𝐸 →𝐸+𝐸
𝐸 →𝐸∗𝐸
𝐸 → (𝐸)
𝐼 → 𝜀 0 1| … |9
18
• String:
E • 3+2∗5 E
• Grammar
𝐼 → 𝜀|0|1| … |9𝐸
→ (𝐸)𝐸 → 𝐸 ∗ 𝐸𝐸
E * E → 𝐸 + 𝐸𝐸 → 𝐼 E + E
E + E I I E * E
I I 5 3 I I
3 2 2 5
𝟑+𝟐 ∗𝟓 𝟑 + (𝟐 ∗ 𝟓)
19
Left Recursive or Left Associative
1st Level:
𝐸→𝐼 𝐸 → 𝐸 + 𝑇|𝑇
𝐸 →𝐸+𝐸
𝐸 →𝐸∗𝐸 2nd Level:
𝐸 → (𝐸) 𝑇 → 𝑇 ∗ 𝐹|𝐹
𝐼 → 𝜀 0 1| … |9
3rd Level:
𝐹 → (𝐸)| 𝜀 0 1| … |9
20
Left Associative and Precedence - Satisfied
𝐸 → 𝐸 + 𝑇|𝑇
𝐸→𝐼 𝑇 → 𝑇 ∗ 𝐹|𝐹
𝐸 →𝐸+𝐸 𝐹 → (𝐸)| 𝜀 0 1| … |9
𝐸 →𝐸∗𝐸
𝐸 → (𝐸)
𝐼 → 𝜀 0 1| … |9
21
• String:
• 3+2∗5 E
• Grammar
𝐸 → 𝐸 + 𝑇|𝑇
𝑇 → 𝑇 ∗ 𝐹|𝐹 E T
𝐹 → (𝐸)| 𝜀 0 1| … |9 +
T T * F
F F 5
3 2
𝟑 + (𝟐 ∗ 𝟓)
22
