ADMIN

* Questions on Phase 1 of project?
* Working on more detailed notes on using CSGs for declare-before-use
* Read!
* Quiz (done as a group)
* Missing: Adam, Ananta, Erik, Mark

Note with regexp can't do a^nb^n

CFG for a^n b^n

S -> epsilon
  |  aSb

Challenge: Write a CFG for "strings of a's and b's with
equal numbers of a's and b's"

S -> S S
  |  a b
  |  b a

Can we derive aaabbb?  Probably not.  Whoops.

S -> S S
  |  a S b
  |  b S a
  |  a b
  |  b a
  |  epsilon

Is this too big?

P1 S -> S S
P2  |  a S b
P3  |  b S a
P4  |  epsilon

How would we show this is correct?
  Induction
  Proof by Contradiction
  Divide and Conquer

Prove by hand waving that this language is a subset of
the desired language

Prove by induction (on what?) that all strings of a's and
b's with equal numbers of a's and b's are in this language.

Induce on #as or #bs.

Induction:
  Assume that we can derive any string of equal numbers
  of a's and b's of length < 2k
Need:
  We can derive any string of equal numbers of a's and
  b's of length 2k.

  Four possibilities:
  a X a
   Must have form a X1 b X2 b X3 a
  a X b DONE by P2
  b X a DONE by P3
  b X b 

  Two possibilites:
    X1 a b X2
    X1 b a X2

FINISH THE PROOF FOR MONDAY.  INFORMAL IS FINE, BUT IT
MUST BE WRITTEN OR DIGITAL.

-----

Daren's alternative:
  Prove that the number of strings of length 2n = the number
  of permutations of a^nb^n

-----

ON to today's topic: Ambiguity

S -> epsilon
  |  SS
  |  a

Question: How many ways are there to derive "a"?

An infinite number, because you can apply the S->SS rule
lots of times and then turn most of those S's to epsilons.

Is that a problem?  Not for this language.

E -> num
  |  E op E
  |  ( E )

Are there strings that can be derived in more than one
way in this grammar?  Yes!  num op num op num.

SEE THE REAL BOARD

Is it a problem that we have two proofs that the string is
in the language?  No, if all that we care about is proof.
YES, if we actually use the parse tree for evaluation or
code generation.

We want unambiguous grammars for programming language
design.

Another ambiguous grammar: Conditionals

Statement -> simple-statement
Statement -> if test then Statement else Statement
Statement -> if test then Statement 

Claim: This is ambiguous

Hacker's attempt to fix the problem:
* Require "end if"

Theoretician's response:
* But then the language is different.

Sam's attempt to fix the problem:
* Identify an ambiguous pair
  Done
* Choose one that's correct
  "Match the most recently unclosed if"
* Figure out which rule lets us generate the
  incorrect thing
  Statement -> if test then Statement
    may be at fault since it didn't bind the else
     like it was supposed to
  Statement -> if test then Statement else Statement
    may be at fault since it permits an "unbound if"
    in the middle statement
  We'll fix the second one

Two kinds of conditionals:
  Those with matched elses
  Those without

Statement -> UnmatchedStatement
          |  MatchedStatement
UnmatchedStatement -> if test then Statement
MatchedStatement -> simple-statement
MatchedStatement -> if test then MatchedStatement else Statement

Questions:
(1) Does this generate the same language?
    Yes, I think so.
(2) Is this grammar ambiguous?
    Yes, but it took a lot of work to figure it out

if test then if test then ss1 else if test then ss2 else ss3

Statement -> UnmatchedStatement
          |  MatchedStatement
UnmatchedStatement -> if test then Statement
UnmatchedStatement -> if test then MatchedStatement 
                      else UnmatchedStatement
MatchedStatement -> simple-statement
MatchedStatement -> if test then MatchedStatement 
                    else MatchedStatement