CS143: Compilers (2011)

http://www.keithschwarz.com/cs143/WWW/sum2011/

by rspivak • 10 years ago

139 62 10 years ago

sklogic12• 10 years ago

And again, 90% about the parsing, and a couple of words about "code optimisation". That pitiful so called "Dragon Book" really keeps taking its toll of souls.

I'm terribly sorry to break the news for you, but no, compilers are not about parsing. Nowhere near that.

n00b101• 10 years ago

True, but parsing is still a facinating and active research subject. It should really be its own course, perhaps taught using Grune Jacobs [1]

[1] http://www.springer.com/fr/book/9780387202488

agumonkey3• 10 years ago

and http://tratt.net/laurie/blog/entries/parsing_the_solved_prob...

nickpsecurity3• 10 years ago

That's true. There continues to be interesting work there. Most people dont want to improve parsers though. They just want to translate one programming language to another form. So, our focus should be on that stuff by default instead of the part that is mostly solved for most usecases even with automated tools.

United857• 10 years ago

Compilers are complicated things -- too much to attempt to cover in a single quarter.

There is a followup course, CS243 which focuses on the optimization aspect.

http://suif.stanford.edu/~courses/cs243/

wtetzner• 10 years ago

Right, but while parsing is important, it's the least interesting aspect of implementing a compiler. It would be better if more time was spend on starting with an AST and generating code. Then at the end of the course, implement a parser to generate the AST.

sklogic12• 10 years ago

My point is exactly the opposite - compilers are easy, probably easier than pretty much anything else. And courses like this do not help by pretending this is a complex topic and by obscuring what matters with unimportant minutiae (like parsing and such).

theGimp• 10 years ago

You have to start somewhere. Code optimization is utterly useless if you can't parse code.

sklogic12• 10 years ago

Quite a few very usable languages are just fine without any dedicated syntax at all. Think of Lisp and Fort for example.

And backend is not just about optimisations, they're mostly insig igicant. Backend is about translating gradually one semantics to the other. An example of such is compiling a regular expression into a DFA and then a C array and a switch.

nickpsecurity3• 10 years ago

So write up a grammar, feed it to a parser generator like GOLD, run result through a premade parser engine, and BOOM your done. Then, you can start on the stuff in the middle that really needs more people working on it.

_pmf_• 10 years ago

You have to start somewhere. Code optimization is utterly useless if you can't parse code.

It's absolutely not uncommon for architecture experts to plug into the optimization stage of an existing compiler; expecting them to understand the first stages is not useful at all. They need to understand the AST / IR, but not how to arrive at it.

jstimpfle4• 10 years ago

(I've never written an optimizing compiler).

I actually think many useful languages are mostly syntax. If you compile to another source language (like C or SQL) you might not need much optimization.

Parsing some syntaxes is difficult but that doesn't imply we should just ignore it and let libraries handle everything. Thinking about parsing is an opportunity to learn about tradeoffs and to develop a good taste designing syntaxes which are easy to parse (and, possibly correlated, manipulate) both for computers and humans.

sklogic12• 10 years ago

Most languages are transforming one layer of semantics into another. Optimisations are pretty much irrelevant in this notion.

Parsing in most cases should either be trivial, or can be skipped altogether.

amelius• 10 years ago

I believe the most difficult part of a compiler/language is actually the runtime environment, in case it contains a concurrent garbage collector. Code optimisation is easy compared to that, especially if done a priori.

mafribe9• 10 years ago

Optimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy.

pjmlp2• 10 years ago

Yeah, and apparently the teachers still haven't heard about ANTLR, JavaCC/JJTree, SableCC, parsing expression grammars or attribute grammars.

How come that they are still teaching only yacc/lex as parsing generators in 2016?!

dlo• 10 years ago

The second half of the 2nd edition of the Dragon Book is pretty good, especially if you think of it as learning math.

userbinator• 10 years ago

I agree that it's also better to keep the parsing part small and focus on the more "interesting" things like code generation and optimisation. Recursive descent/precedence climbing seems to be the preferred parsing technique in a lot of production-quality, modern compilers, and I'd argue that knowing about RD is more than sufficient for most of what anyone wanting to play around with compilers needs.

Niklaus Wirth would probably agree.

mataug• 10 years ago

I'm going to be taking a Compilers course next quarter and I was speaking to the prof who told me that she doesn't plan on using the Dragon book, instead she plans to use the Louden book which seems a lot more approachable in a single quarter.

I was lucky enough to buy a used copy on amazon for $8.

http://www.amazon.com/Compiler-Construction-Principles-Kenne...

pjmlp2• 10 years ago

Also take Niklaus Wirth PDF and follow how to write an Oberon-0 compiler end-to-end.

http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf

It is a very instructive process.

alex_muscar• 10 years ago

This is a really neat book. The fact that it builds a complete compiler and virtual machine in ~100 pages is really amazing.

doomrobo• 10 years ago

Took an algorithms course with Keith a few years ago. Really patient engaging lecturer!

melling• 10 years ago

I've got a small collection of compiler resources on Github:

https://github.com/melling/ComputerLanguages/blob/master/com...

I'll add more as they are posted.

RcouF1uZ4gsC• 10 years ago

Also, take a look at http://www.keithschwarz.com/interesting/

It is an amazing archive of all kinds of neat algorithms and data structures.

gravypod• 10 years ago

I'm pleasantly surprised. For academic work, this code is amazingly clean.

yyin• 10 years ago

matthewarkin• 10 years ago

There's self-reported data that some Stanford students have scrapped from CourseRank before it got shutdown. http://www.stanfordrank.com/cs143

ttandon• 10 years ago

Currently taking CS 103 (Mathematical Foundations of Computing) under Keith at Stanford. Truly one of the best taught classes I've ever taken - the man has a love for teaching Computer Science that really makes all the difference.

khushia2• 10 years ago

Out of curiosity - the Mid-term exam paper says:

This midterm exam is open-book, open-note, open-computer, but closed-network. This means that if you want to have your laptop with you when you take the exam, that's perfectly fine, but you must not use a network connection. You should only use your computer to look at notes you've downloaded from online in advance. If you are an SCPD student, you should take this exam in any two-hour period between 11:00 AM Pacific time, July 20 and 11:00 AM Pacific time, July 21 . If you have any questions, please feel free to call me at _ any time in this window except between midnight and 8AM on July 21, Pacific time. You may submit the exam either by faxing it to _ or by scanning and emailing it

I'm not familiar with how these things work in the US - are the students trusted to take the exam away and not use the internet to get help?

thebird• 10 years ago

I can't speak for other schools in the US but I am an undergraduate in the CS department at Stanford, and it's fairly common to have an open-computer test to refer to notes and the textbook. Other students sit around you and it's most likely fear of another student approaching a TA that makes this enforceable.

simscitizen• 10 years ago

At Stanford, faculty are prohibited from proctoring. So there is no professor or grad student that sits in the exam hall with the students while they are taking the test:

"The faculty on its part manifests its confidence in the honor of its students by refraining from proctoring examinations and from taking unusual and unreasonable precautions to prevent the forms of dishonesty mentioned above."

https://communitystandards.stanford.edu/student-conduct-proc...

A professor or grad student walks into the room every 30 minutes or so just to make sure everything looks okay. They otherwise sit outside the exam hall so you can ask them questions, ask to go the bathroom, etc. But it's up to the students to police each other and ultimately themselves.

There are definitely other universities in the US that have this policy, but I would say it's more the exception than the norm.

khushia2• 10 years ago

That's really interesting. I did a CS degree in the UK and all exams were strictly supervised and we were never allowed computers.

The exception to this was programming exams for which the department would boot all the lab workstations into a locked-down mode with no internet & new homedir containing only the exam files. At the end of the exam everything got collected and marked by an automated test suite.

They went to quite some effort to ensure that no cheating could take place - http://pubs.doc.ic.ac.uk/Lexis/Lexis.pdf

ratsbane• 10 years ago

I took that class on the Stanford campus in the Summer of 2011. Keith was one of the most engaging instructors I've ever had. His enthusiasm and knowledge were boundless.

The course was video-recorded and I downloaded and saved most of the lectures (and I gave Keith a DVD with a copy of them.) I still have them, but I don't know if it's okay to put them on YouTube or not.

cplease• 10 years ago

Of course it is not okay unless you have permission.

sewercake• 10 years ago

I'm taking my university's offering of this course in my final semester. It's fantastic. I'm using all of the seperate skills I've developed over the last four years: Mathematical thinking (via parsing), algorithms and data structures (ASTS),Programming Languages, software design. It's also the first course where big design decisions are non-trivial, and really effect things later down the pipeline, an experience that is rare in school, but, from what I can tell, ubiquitous in the field. I really recommend it to any students out there.

jor-el• 10 years ago

I remember while learning data structures and implementing them, I landed on http://www.keithschwarz.com/interesting/. It was enlightenment for me. By browsing through these examples I learned about good programming practices. Most importantly how commenting your code can help you even when you return after few years to fix something in it.

CS143: Compilers (2011)

Related Stories