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