CSC362 2004S, Class 13: Ambiguous Grammars

Admin:
* Claim: We can't parse Pascal with a CFG!
  http://www.egr.unlv.edu/~larmore/Courses/CSC456/S03/Assignments/cfgproglang
  (We can write one, but not one that checks all the semantics.)
* Cool biocomputing talk tomorrow.  E.c. for attending *and reflecting*.
* Changed due date for project, phase 2.
* The newest SEPC members are mathematicians.  The CS folks have let us down.

Overview:
* Ambiguous grammars.
* Conditional grammar, revisited.
* Disambiguating grammars.
* Disambiguating the conditional grammar.
* An expression grammar.

Ambigous grammar is ... a grammar in which there is more than "interpretation" of the same string.  By "interpretation" we mean "parse tree"

s ::= epsilon
s ::= s s
s ::= A

s ::= I s E s
s ::= I s
s ::= X

How can we fix this grammar?  (How can we fix any ambiguous grammar?)
* We *don't* want to change the language
* We simply want a new grammar to describe the same language

"Background" research:
* Find a string with multiple parse trees
  I I X E X
* Decide on the "correct" parse tree
  The one in which E binds with the closer I
* Decide on a policy that describes that correct parse tree
  Bind E's with closer I's

Side note: The theory folks say that some languages are inherently ambiguous, and claim the following example demonstrates why
a^i b^j c^k | i = j or j = k

Think carefully about your grammar and consider how it leads to ambiguity.
s ::= I s E s
s ::= I s
s ::= X
Replace ambiguous rules by less ambiguous rules, often creating new "classes"
  of things.

Claim: The problem seems to come when you can substitute "I s" for the first s in "I s E s".

s ::= I t E s
t ::= I t E s
s ::= I s
s ::= X
t ::= X

Claim: This grammar disambiguates the prior grammar
* Must verify: This new grammar is unambiguous
  FALSE: IIXEIXEX
* This new grammar produces the same language as the previous grammar

Earlier test: Can we construct two parse trees for the old problem string? No

Revised Grammar

s ::= I t E s
t ::= I t E t
s ::= I s
s ::= X
t ::= X

Claim: This grammar disambiguates the prior grammar
* Must verify: This new grammar is unambiguous
* This new grammar produces the same language as the previous grammar

If we were sufficiently precise and had enough time, we'd do a proof
by induction

---

Our next favorite ambiguous grammar: Infix expressions over variables and integers

exp ::= ID
exp ::= INT
exp ::= exp binop exp
exp ::= OPEN exp CLOSE
binop ::= PLUS
binop ::= TIMES
binop ::= MINUS
binop ::= DIVIDE

This grammar is ambiguous
                   exp
                /         \
exp           exp         exp
  |            |           | 
INT[3] PLUS INT[4] TIMES INT[5]
  |            |           | 
exp           exp         exp
   \          /
       exp

Two normal rules for disambiguating expressions:

(1) Order/precedence of operations: times/divide have higher precedence than do add/subtract

(2) Left-associativity: Bind left-to-right

3 - 4 - 5 => (3 - 4) - 5
          NOT 3 - (4 - 5)

(Except exponentiation, which binds right-to-left)