2.5 ambiguity in context free grammars

ambiguity in context free grammars

1. Ambiguity in Context-Free Grammars Sampath Kumar S, AP/CSE, SECE

2. 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. 8/4/2016 Sampath Kumar S, AP/CSE, SECE 2

3. Problems to discuss: 74. 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 leftmost derivations. Derivation 1 − X → X+X [ ∵ X → X+X ] → a +X [∵ X → a ] → a+ X*X [ ∵ X → X*X ] → a+a *X [ ∵ X → a ] → a+a *a [ ∵ X → a ] 8/4/2016 Sampath Kumar S, AP/CSE, SECE 3

4. Problems to discuss: Derivation 2 − X → X*X [ ∵ X → X*X] → X+X*X [∵ X → X+X ] → a+ X*X [∵ X → a ] → a+a *X [∵ X → a ] → a+a *a [ ∵ X → a ] As there are two parse trees for a single string " a+a *a", the grammar  G  is ambiguous. 8/4/2016 Sampath Kumar S, AP/CSE, SECE 4

5. Problems to discuss: 75. Show that the following grammar is ambiguous E → id | E+E | E * E | E – E. 76 . Show that the following grammar is ambiguous S → aS|Sa|a . 77. Show that the following grammar is ambiguous S → aS|aSb|X , X → Xa|a . 78. Show that the following grammar is ambiguous S → i C t S | i C t S e S|a , C → a 8/4/2016 Sampath Kumar S, AP/CSE, SECE 5

6. Problems to discuss: 75. id+id *id 76. aa 77. aa 78. ibtibtaea 8/4/2016 Sampath Kumar S, AP/CSE, SECE 6

7. 8/4/2016 Sampath Kumar S, AP/CSE, SECE 7

8. நன்றி  8/4/2016 Sampath Kumar S, AP/CSE, SECE 8