The ID (identifier) token and what it represents

I was asked whether the scanner needs to recognize bad identifiers like foo.bar.baz .  The short answer is "no, that's a job for the parser", but the question indicates a need to be a little clearer about exactly what the identifier (ID) token represents.

foo.bar.baz is 5 tokens:  ID foo, DOT, ID bar, DOT, ID baz.  A scanner should in general not try to match anything with internal structure, like foo.bar(); it is returning the atoms of a program, to be assembled into molecules by the parser.    (I know the STRINGLIT token may seem like an exception, but from the parser's point of view it has no internal structure, even if the scanner has to do some work to interpret things like \n and \" inside the quoted string literal.)

Building compilers: Pedagogic vs real projects

The order we're tackling the Cool compiler is to build a lexical analyzer for the whole language, then a parser for the whole language, then a static checker for the whole language, then a code generator for the whole language.  We're forced to do that because it gives us some kind of order for studying the different parts of the compiler and their underlying theory, instead of studying everything at once.  But, in case it's not obvious, let me just mention that no sane person would build a real compiler this way.

How do you build a real compiler?

First you build a compiler for the teeniest tiniest subset of the language that you can possibly test ... maybe it can compile the "hello world" program and nothing else.  Probably it can't compile the "hello world" program because that would involve string processing and IO ... but it might compile a procedure that can add two integers.  Maybe you make it an interpreter instead of a compiler, and then you add a code generator as a second step.

And then you add some small feature, adding and fixing what you need in every phase of the compiler, from lexical analysis to code generation.

And then another feature.   And so on.  Add, test, revise, add, test, revise, until you have a complete compiler for the whole language.   It doesn't work as a class project in a compilers course, but it's much better than what we are doing for a real compiler, whether it's for a full programming language like Java or for some itsy bitsy language you invent as an interface to some application you are building.

[Thanks Dan for prompting this thought in our after-class discussion.]

Two more NFA => DFA problems for the board

1.  From the winter 2005 midterm, a language for binary or trinary literals.  A binary literal is
(0|1)+b2
and a trinary literal is
(0|1|2)b3
So for example 01110101b2 is a binary literal, 0110101b3 is a trinary literal and so is 01002201b3, but 010020101b2 is neither a binary literal nor a trinary literal.   Given an NFA for this, we'll construct the DFA.

2.  From the Spring 2006 midterm, a simplified quoted string problem.  A quoted string (string literal) starts with a quotation mark and ends with a quotation mark.  Within the string, we can have alphabetic characters.  To put a quotation mark within a quoted string, we type two quotation marks together, like this:
"this is a ""string with a quoted substring"" up to here"
If we let 'a' stand for alphabetic characters and Q stand for a quotation mark, the regular expression might be something like
Q(a|(QQ))*Q
We'll use the subset construction to derive a DFA from the NFA.

Regexp => NFA => DFA problem for tomorrow's class

The main things I want to do in class Friday are:

• work a few examples of translating regular expressions to non-deterministic finite-state acceptors
• discuss a few practical complications that aren't apparent in the theory, like how the "maximum munch" rule and matching a lot of different patterns (with different actions) go together
• discuss the limitations of lexical analysis (the pumping lemma, for those of you who took automata theory)

Here's a small example we can do on the board tomorrow, for the first two items above.  Imagine your language has integer constants and floating point constants.  Integer constants are a sequence of one or more integer digits.  It might be specified as
[0-9]+
or equivalently as
[0-9][0-9]+
Floating point constants consist of zero or more digits, followed by a decimal point, followed by one or more digits.  (So .00 is a floating point constant, but 0. is not, and neither is . )  This might be specified as
[0-9]*[.][0-9][0-9]*

We could carefully follow Thompson's construction to get the NFA for each of these and then combine them, but it's easier and less messy to just eyeball the pattern for integer constant and the pattern for floating point constant and create an automaton for each of them, then use Thompson's construction just to tie them together as
    ( integer constant ) |  (floating point constant )
and then we can go through the subset construction to get a single deterministic finite-state acceptor that is looking for both of them and succeeds if it matches either one.  You might want to try that in advance (but you don't have to).  If you do, consider what should happen with the following input:
998
99.foo
.998

Scanner assignment up

Grab http://www.cs.uoregon.edu/classes/10W/cis461/handouts/Cool.tgz to get started on the scanner (lexical analyzer) assignment.

I have filled in a lot of trivial grungy stuff and the stuff that doesn't really have anything to do with lexical analysis ... I think what's left for you to fill in should be pretty quick.   Keyword and punctuation patterns are certainly trivial ... you'll see the pattern in Cup.jflex Cool.jflex  and just fill in the few I removed.  Two patterns might take a bit more work: comments and strings.  There is a pattern for comments there already, and it *might* be right, but I don't promise.  There is a pattern for string literals, and I'd be really surprised if it is correct.   It's really ugly, too ... like a lot of complex regular expressions.  Consider using the lexical state facility of JFlex to break it down into simpler patterns that you can read, understand, and fix.

Java will complain that the generated scanner uses unsafe operations.  That's because the scanner skeleton file is written in the old, pre-generics style.   I'm using one of the optional skeletons because I threw in the ability to #include just for fun and to demo how that works ... it's not part of Cool, but it's something you'll want to do in another scanner some day. 

Due: Monday of next week.  The parser assignment will come out Monday or Wednesday.

The README.txt file says a bit more about what you'll find and how to get going.  Although the amount of work here should not be large, it's a good idea to tackle it soon, so that you have a chance to ask questions when things break.

Schedule: Two midterms and no final?

I will attend a workshop in Germany during finals week.  In principle I could ask someone to proctor a regular final exam and scan and email the exams to me, and I could grade them from Germany ... but it would be a rush job, and too much could go wrong (e.g., some huge blunder in an exam question and me not there to explain what I meant).  So ... what to do?

The best I can think of is two midterms instead of a midterm and a final --- and then put a bit of space between the second midterm and the final project due date, so they don't interfere too much.  I'm thinking final project due Monday of dead week, second midterm on Wednesday or Friday.  Comments?  Better ideas?

Revise Cool language manual posted

I've revised the Cool language manual for this year's class.  Most of the changes are really small an cosmetic, e.g., making the assignment symbol be ":=" instead of "<-"  ("=" is a comparison in Cool).  I added section 13 at the end with notes on differences between Cool and Java (and to some extent C++).  Those aren't essential but might be helpful.

The link from the course web site should work, or follow it here:
http://www.cs.uoregon.edu/classes/10W/cis461/handouts/cool-manual.pdf