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