This is the archived website of SI 413 from the Fall 2012 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.
Use a separate sheet of paper for your answers! Everything should be submitted in one packet, all printed out for me to see.
Pick a pair of two programming languages that you know, and come up with an example of each of the following:
Draw the DFA for the scanner that accepts the following tokens (as specified by regular expressions). Label accepting states with the name of the token.
FLOAT: [0-9]*"."[0-9]+ INT: [0-9]+ RANGE: [0-9]+":"[0-9]+ HEX: 0x[0-9a-f]+
+ means "one or more of the previous thing", and a
* means "zero or more of the previous thing". Square brackets
 indicate a range of characters (or multiple ranges), and anything in quotes
"" means that literal character.)
Now suppose we want to add a new token
OCT to the language above, matching the regular expression
0[0-7]+ (that is, a zero followed by one or more digits between 0 and 7).
The following grammar is ambiguous (in terms of parsing), but it still defines a language:
S → exp
exp → exp
Write a new grammar for the same language which is unambiguous and would work well for top-down parsing. (In particular, your new grammar should be LL(1).)
Using your modified grammar from the previous problem, draw the parse tree that would be generated by a top-down parser for the following string:
53 + 89 - 103