If I ever design a first course in compilers, I'll do it backwards
pozorvlak.dreamwidth.org
pozorvlak.dreamwidth.org
Ghuloum's scheme compiler tutorial essentially follows this method: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf. It starts with emitting x86 machine code for constants, then unary and binary primitives, local variables, conditionals, heap allocation, procedure calls, and finally closures. It helps that Scheme has little to no parser to speak of, but it is straightforward to extend the technique to a language that does.
When reversed, however, most of my students found it extremely hard to wrap their head around the the first part of the course, i.e. code generation from an AST. They didn't have sufficient grounding in recursive data structures and algorithms. While this might be a problem with the degree program rather than the compilers course, I believe that learning to write a recursive descent parser (by hand) provides this grounding and makes the code generation bit much easier to grasp.
Unfortunately the new lecturer had also done away with teaching the students how to write parsers by hand, instead encouraging them to use parser generators. I thought that was tragic. One of the best moments of my programming life was writing a recursive descent parser for a non-trivial grammar in one sitting (about 500 lines of python), hitting run and having it just work first time. It was orgasmic.
This was, in the grand scheme of things, likely offset by the hours of frustration most of the students went through while debugging their parser which did not work perfectly the first time.
Similarly, I think parsing is best understood by implementing a parsing algorithm. While popular algorithms like LL and LR are rather complex, CYK algorithm is straightforward to implement, directly corresponding to the definition of context-free grammar. Other algorithms are optimizations.
For ordering, I think it is best to start with AST and its interpretation. And then parsing and lexing (in that order). And then compilation. And then extending the language with features. And then various optimizations.
Using a parser generator of some kind is possibly okay to teach the concept of a grammar, but it's terrible for error handling, efficiency, and simplicity. For most programming languages, nothing beats a plain old hand-written recursive descent parser (optionally with pratt parsing for expressions) on those metrics. And indeed, most compilers I've seen in production are written that way.
Same thing with virtual functions, once I've learned how it was implemented then I was ready to understand why it was useful, not before..
It could be me who work this way, though.
None of the work is motivated concretely by the work of the prior step.
Fine if you are designing the representations for them, but I'm wondering how they would design an AST for a language they haven't seen or haven't thought about how to parse.
It would be an interesting experiment. If you were going to have them design the internal representations, you could have then move backward in a why that allows them to compile a family of languages. They could create something as general as the LLVM suite. :)
As for AST design, it is easier to design the AST first than you might think. Just ask the designers of Lisp.
A third alternative would be to start in the "middle" with the AST, and go both forwards and backwards from there. :)
So, start with the AST as a given, or even have them design it, and use it to drive the design of the concrete syntax, static analysis, code generation, etc. At each phase, cover relevant concerns (i.e. "here's how to avoid shift-reduce conflicts in the concrete syntax").
I know nothing about teaching, so probably this wouldn't work, just speculation.
What if the course was designed based on an "Agile," evolutionary methodology?
In that course, you would divide the course work in 4 "scrums". In each scrum you do a little bit of everything (little bit of lex, little bit of parse, little bit of syntax analysis, little bit of code generation). In the first scrum you also would cover the architecture and high level overview of the "roadmap."
Of course, at the end of the first "scrum" you would have a very primitive compiler for a very primitive language and without a lot of error checking, but students would have been exposed to the end to end experience.
The second and subsequent "scrums" would only deepen each part of the compiler, and students would benefit from knowing the interactions across modules and simply learning more sophisticated techniques.
I remember when building my first compiler in college that I really had no clue why we were learning about tokenization and state machines for so long when I really wanted to generate optimized code.
(A bit off topic, but Scrum is however an actual methodology name.)
I understand that, I'm just unsure of what benefit having scrums would be in this context, or whether that term is even appropriate for what is essentially an instructor introducing the next assignment (which never needed a special name before.)
Ideally I would want to teach a two semester course starting with the backend first -- the first task would be to write several significant programs in assembly language (for some clean RISC machine) and grade them on how well they managed register allocation, stack frame / heap management, page alignment, etc.. Then cover how to convert some SSA IR (e.g., LLVM) into that language.
How do you translate into a language you don't understand?
Started with an interpreter. Eventually turned it into a compiler. Really fun project, ran into a bunch of weird issues that would have quickly been solved had I read any theory whatsoever about compilers.
But looking back at it now, after having taken an actual compilers course in college, it did sort of have all the stages. They just happened to all be mushed together and not very cleanly separated or very cleanly defined.
The grammar, for instance, was more like a bunch of if statements and function calls that kinda sorta made the compiler do what I wanted ... but corner cases kept cropping up ...
Fun times.
Given an abstract syntax, it's super-easy to create an unambiguous concrete one (it may be ugly and verbose, but can completely avoid the issues of operator precedence, shift-reduce conflicts, lookahead, ambiguity, top-down vs. bottom-up, etc. etc.). If concrete syntax turns out to be interesting, it's always possible to design a second one (for the same abstract syntax) that's much more usable, pretty, etc.
When the language is modified, the focus can be placed more on the abstract syntax, and less on concrete syntax.
This was a very effective way to grasp the code generation without getting bogged in lexing/parsing, register assignment (the machine was stack-based) and so on.
Sadly we later moved to the hard parts. Manual LALR(1) machine generation was probably the dullest grindwork in the whole CS curriculum :)
This is definitely closer to what is described in this post than most compilers courses, but not entirely the same.
I agree with the post in that the current common method of starting with _just_ parsing/lexing is wrong. It's a shame that the first part of the compiler you write in these courses is, in my opinion, the most boring and least relevant to compiler theory. CMU's method of giving you the whole, although fuzzy, picture within the first two weeks wasn't viewed as wrong by me, my lab partner, or anyone else I knew who took the compilers course. In fact, everyone I knew who successfully completed the course highly recommended it to everyone they knew. This is a pretty good measure of success for a course.