Ambiguous & Unambiguous Grammar

Ambiguous and unambiguous grammar of context free grammar (CFG) in Theory of computing

1. Topic : Ambiguous grammar & parse Tree Course title: Theory of computing Course code: se-234 1/3/2020 Ambiguous Grammar & Parse Tree 1 Department Of Software Engineering

2. Ambiguous & Unambiguous Grammar Depending on Number of Derivation Trees, CFGs are sub-divided into 2 types: Ambiguous Grammars Unambiguous Grammars 1/3/2020 Ambiguous Grammar & Parse Tree 2 The Context  Free Grammars(CFGs) are classified based on: Number of Derivation trees Number of strings

3. What is Ambiguous Grammar? 1/3/2020 Ambiguous Grammar & Parse Tree 3 A grammar is said to be Ambiguous if there exists two or more derivation & parse tree for a string w. Figure: 1 s a s s s a s a a a

4. What is Unambiguous Grammar? 1/3/2020 Ambiguous Grammar & Parse Tree 4 A grammar can be unambiguous if the grammar does not contain more than one leftmost derivation or more than one rightmost derivation or more than one parse tree for the given input string. b x b x x b

5. 1/3/2020 Ambiguous Grammar & Parse Tree 5 G = (V,T,P,S) is a CFG is said to be ambiguous if and only if there exist a string in T* that has more than one parse tree. where, V = finite set of variables . T = finite set of terminals . P = finite set of productions of the form, A → α , where A is a variable and α ∈ (V ∪ T )* S = designated variable called the start symbol.   Definition of ambiguous & unambiguous grammar:  

6. 1/3/2020 Ambiguous Grammar & Parse Tree 6 Example - 1 Check the grammar G with production rules − X → X+X | X*X |X| a is ambiguous or not? Let’s find out the derivation tree for the string " a+a *a". It has two leftmost derivations. Derivation – 1 X → X*X → X+X*X [X→X+X] → a+X*X [X →X*X] → a+a*X [X→a ] → a+a*a Derivation – 2 X → X+X → a+X [X→a] → a+X*X [X →X*X] → a+a*X [X→a ] → a+a*a

7. 1/3/2020 Ambiguous Grammar & Parse Tree 7 Figure: 3 Figure: 2 Parse Tree - 1 Parse Tree - 2 Since there are two different parse trees for a single string " a+a *a", So the grammar  G  is ambiguous. x + x x x a x a a * x * x x x + x a a a

8. 1/3/2020 Ambiguous Grammar & Parse Tree 8 Example - 2 The grammar G is with production rules- S → T T → 01 T → T T From the above grammar, Check the ambiguity by the derivation & parse tree for string “010101”. Derivation – 1 S → T → T T [T→TT] → T TT [T→TT] → 01 T T [T→01] → 0101 T [T →01 ] → 010101 [T→01 ] Derivation – 2 S → T → TT [ T→TT] → TTT [ T→TT ] → TT01 [ T →01] → T0101 [ T →01] → 010101 [ T →01]

9. 1/3/2020 Ambiguous Grammar & Parse Tree 9 Figure: 3 Figure: 2 Parse Tree - 1 Parse Tree - 2 S T T T T T 1 1 T 1 S T T T T T 1 1 T 1 The grammar has two or more derivation & parse tree. So this is also an Ambiguous.

10. 1/3/2020 Ambiguous Grammar & Parse Tree 10 Example - 3 Given a context-free grammar G with start symbol S, terminal symbols T and productions P, the language L(G) that G generates is defined to be the set of strings of terminal symbols that can be obtained by derivation from S using the productions P, i.e., the set {w ∈ T ∗ | S ⇒ w }. T → R T → aTc R → ∈ R → RbR Check that the grammar is Ambiguous or Unambiguous for the string ‘ aabbbcc ’ ?

11. 1/3/2020 Ambiguous Grammar & Parse Tree 11 T ⇒ a T c ⇒ aa T cc [T ⇒ aTc ] ⇒ aa R cc [T ⇒ R] ⇒ aa R bRcc [R ⇒ RbR ] ⇒ aa R bRbRcc [R ⇒ RbR ] ⇒ aa R bRbRbRcc [R ⇒ RbR ] ⇒ aab R bRbRcc [R ⇒ ∈ ] ⇒ aabb R bRcc [R ⇒ ∈ ] ⇒ aabbb R cc [R ⇒ ∈ ] ⇒ aabbbcc [R ⇒ ∈ ] Leftmost Derivation of the string ‘ aabbbcc ’ T ⇒ a T c ⇒ aa T cc [T ⇒ aTc ] ⇒ aa R cc [T ⇒ R] ⇒ aaRb R cc [R ⇒ RbR ] ⇒ aaRbRb R cc [R ⇒ RbR ] ⇒ aaRbRbRb R cc [R ⇒ RbR ] ⇒ aaRbRb R bcc [R ⇒ ∈ ] ⇒ aaRb R bbcc [R ⇒ ∈ ] ⇒ aa R bbbcc [R ⇒ ∈ ] ⇒ aabbbcc [R ⇒ ∈ ] Rightmost derivation of the string ‘ aabbbcc ’

12. 1/3/2020 Ambiguous Grammar & Parse Tree 12 b R b T R R R ∈ R c a a T T c b R ∈ ∈ ∈ b R b T R R R ∈ R c a a T T c ∈ R b ∈ ∈ Parse Tree-1 Parse Tree-2 R R

13. 1/3/2020 Ambiguous Grammar & Parse Tree 13 Example - 4 Consider V N = {S, E}, V T = {if, then, else} and a grammar G = (V T ,V N , S, P) such that the following grammar S → if E then S | if E then S else S Are productions of G. Then the string W → if E then if E then S else S Now check the ambiguity. Derivation – 1 S → if E then S else S → if E then if E then S else S Derivation – 2 S → if E then S → if E then if E then S else S

14. 1/3/2020 Ambiguous Grammar & Parse Tree 14 S E if then S else S if E S then S E if then S else S if E S then Parse Tree-1 Parse Tree-2 The string has two derivation trees. So it is ambiguous.

15. 1/3/2020 Ambiguous Grammar & Parse Tree 15 Consider the following grammar- S → aS | ∈ The language generated by this grammar- L = { a n  , n>=0 } or a* Example - 5 Let us consider a string w = “ aaa ”. First Derivation-   S → aS → aaS        [ S → aS ] → aaaS      [ S → aS ] → aaa ∈ [ S → ∈ ] → aaa Second Derivation-   S → aS → aaS        [ S → aS ] → aaaS      [ S → aS ] → aaa ∈ [S → ∈] → aaa Figure - 4 Parse Tree S S a a S S a ∈ Here first derivation and second derivation are exactly same. So, this is an example of an unambiguous grammar.

16. 1/3/2020 Ambiguous Grammar & Parse Tree 16 Example - 6 The following Grammar generates prefix expressions with operands x and y and binary operators +, -, and *: E → +EE | *EE | -EE | x | y Now find leftmost and rightmost derivations and derivation tree for the string ‘+*- xyxy ’. + E E E y * E E E E - y x x Parse Tree: E → + E E → +* E EE [E → * EE] →+*- E EEE [ E → -EE ] →+*- x E EE [ E → x ] →+*- xy E E [ E → y ] →+*- xyx E [ E → x ] →+*- xyxy [ E → y ] Left Derrivation : In this grammar, there is no more derivation and parse tree. So this is also unambiguous.

17. 1/3/2020 Ambiguous Grammar & Parse Tree 17 Example - 7 Consider the given grammar S → S+S | S-S | S*S | S/S | (S) | x | y | z is the productions of G. Then for the string W → ( x+y )*x-z*y/( x+x ) ; check the ambiguity. S → S *S → ( S )*S → ( S + S )*S → ( x+y )* S → ( x+y )* S -S → ( x+y )*x- S → ( x+y )*x- S *S → ( x+y )*x-z* S → ( x+y )*x-z* S /S → ( x+y )*x-z*y/ S → ( x+y )* x-z*y/( S ) → ( x+y )*x-z*y /( S + S ) → ( x+y )*x-z*y /( x+x ) S → S/ S → S/( S ) → S/( S + S ) → S /( x+x ) → S* S /( x+x ) → S *y/( x+x ) → S- S *y/( x+x ) → S -z*y/( x+x ) → S* S -z*y/( x+x ) → S *x-z*y/( x+x ) → ( S )*x-z*y/( x+x ) → ( S + S )* x-z*y /( x+x ) → ( x+y )*x-z*y /( x+x ) Derivation – 1 Derivation – 2 In this grammar, there are more than two derivation and parse tree. So this is an ambiguous.

18. 1/3/2020 Ambiguous Grammar & Parse Tree 18 Reference from: Basics of Compiler Design - by Torben Ægidius Mogensen Introduction to the Theory of Computation_3 rd Edition – by Michael Sipser Introduction to Automata Theory, Language, and Computation – by John E. Hopcroft https:// www.javatpoint.com/automata-ambiguity-in-grammar https://www.geeksforgeeks.org/ambiguous-grammar/

19. 1/3/2020 Ambiguous Grammar & Parse Tree 19

20. 1/3/2020 Ambiguous Grammar & Parse Tree 20