10 ms·

CS143: Compilers (2011)

139 points by rspivak 11y ago

sklogic 11y 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 11y 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 http://www.springer.com/fr/book/9780387202488
  - agumonkey 11y ago
    and http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/blog/entries/parsing_the_solved_prob...
    - groovy2shoes 11y ago
      and http://matt.might.net/articles/parsing-with-derivatives/ http://matt.might.net/articles/parsing-with-derivatives/
      - agumonkey 11y ago
        I forgot how beautiful this was.
  - nickpsecurity 11y 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 11y 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/ http://suif.stanford.edu/~courses/cs243/
  - wtetzner 11y 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.
    - mafribe 11y ago
      That's exactly how I used to teach compilers. But the weaker students had a really hard time understanding the purpose of ASTs ("why don't you give the program to the code generator as a string?") no matter how often I pointed out why ASTs are a better data structure than strings from the POV of efficient code generation. And some students complained about this "unnatural" sequence of explaining compilers in the course evaluations. So I changed to teaching compilers in the standard order, lexing -> parsing -> type-checking -> code gen -> optimisation. No complaints any more. There is another dimension to this. While code gen and optimisations are more interesting than lexing/parsing almost no student will ever again write a code generator, let alone optimisations. OTOH, most programmers need to write little lexers and little parsers for little languages all the time. That's why a bit of facility with lexing/parsing and associated tools is hightly useful.
      - sklogic 11y ago
        You should have done it in a homoiconic language like Scheme, where nobody would be puzzled by a notion of an AST.
        mafribe 11y ago
        Then my students would have been puzzled by Scheme, which they don't know. Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. The only advantage is that Scheme's syntax is simple. Moreover the problem of language representation doesn't go away. You still need to represent programs. The real problem is to understand that there are two level: programs and representations of programs. Avoiding to confuse the two is the real challenge, and it remains a challenge in Scheme.
- theGimp 11y ago
  You have to start somewhere. Code optimization is utterly useless if you can't parse code.
  - sklogic 11y 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.
    - jstimpfle 11y ago
      I hope not all future languages will have regular expression, or Forth, syntax...
      - sklogic 11y ago
        I am talking of the languages that are built on top of Lisp/Forth. I.e., you do not really need any syntax if your underlying implementation language is homoiconic.
  - nickpsecurity 11y 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.
    - jstimpfle 11y ago
      The problem is that writing a good grammar requires understanding of parsers. (Also, real parsers tend to be hand-written, judging from open source language implementations (some have actually migrated from generated parsers to recursive descent in the past). There must be a reason).
- jstimpfle 11y 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.
  - sklogic 11y 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 11y 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.
  - mafribe 11y ago
    Optimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy.
- pjmlp 11y 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 11y 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 11y 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 11y 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-Kenneth-Louden/dp/0534939724 http://www.amazon.com/Compiler-Construction-Principles-Kenne...
- pjmlp 11y 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 http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf It is a very instructive process.
  - alex_muscar 11y 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 11y ago
Took an algorithms course with Keith a few years ago. Really patient engaging lecturer!
melling 11y ago
I've got a small collection of compiler resources on Github: https://github.com/melling/ComputerLanguages/blob/master/compilers.org https://github.com/melling/ComputerLanguages/blob/master/com... I'll add more as they are posted.
RcouF1uZ4gsC 11y ago
Also, take a look at http://www.keithschwarz.com/interesting/ http://www.keithschwarz.com/interesting/ It is an amazing archive of all kinds of neat algorithms and data structures.
- gravypod 11y ago
  I'm pleasantly surprised. For academic work, this code is amazingly clean.
yyin 11y ago
.
- matthewarkin 11y ago
  There's self-reported data that some Stanford students have scrapped from CourseRank before it got shutdown. http://www.stanfordrank.com/cs143 http://www.stanfordrank.com/cs143
- deleted 11y ago
  [deleted]
ttandon 11y 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.
khushia 11y 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 11y 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 11y 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-process/honor-code-and-fundamental-standard#honor-code 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.
  - 11y ago
ratsbane 11y 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 11y ago
  Of course it is not okay unless you have permission.
sewercake 11y 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 11y ago
I remember while learning data structures and implementing them, I landed on http://www.keithschwarz.com/interesting/ 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.

139 points by rspivak 11y 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 11y 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 http://www.springer.com/fr/book/9780387202488
- agumonkey 11y ago
  and http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/blog/entries/parsing_the_solved_prob...
  - groovy2shoes 11y ago
    and http://matt.might.net/articles/parsing-with-derivatives/ http://matt.might.net/articles/parsing-with-derivatives/
    - agumonkey 11y ago
      I forgot how beautiful this was.
- nickpsecurity 11y 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 11y 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/ http://suif.stanford.edu/~courses/cs243/
- wtetzner 11y 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.
  - mafribe 11y ago
    That's exactly how I used to teach compilers. But the weaker students had a really hard time understanding the purpose of ASTs ("why don't you give the program to the code generator as a string?") no matter how often I pointed out why ASTs are a better data structure than strings from the POV of efficient code generation. And some students complained about this "unnatural" sequence of explaining compilers in the course evaluations. So I changed to teaching compilers in the standard order, lexing -> parsing -> type-checking -> code gen -> optimisation. No complaints any more. There is another dimension to this. While code gen and optimisations are more interesting than lexing/parsing almost no student will ever again write a code generator, let alone optimisations. OTOH, most programmers need to write little lexers and little parsers for little languages all the time. That's why a bit of facility with lexing/parsing and associated tools is hightly useful.
    - sklogic 11y ago
      You should have done it in a homoiconic language like Scheme, where nobody would be puzzled by a notion of an AST.
      - mafribe 11y ago
        Then my students would have been puzzled by Scheme, which they don't know. Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. The only advantage is that Scheme's syntax is simple. Moreover the problem of language representation doesn't go away. You still need to represent programs. The real problem is to understand that there are two level: programs and representations of programs. Avoiding to confuse the two is the real challenge, and it remains a challenge in Scheme.
theGimp 11y ago
You have to start somewhere. Code optimization is utterly useless if you can't parse code.
- sklogic 11y 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.
  - jstimpfle 11y ago
    I hope not all future languages will have regular expression, or Forth, syntax...
    - sklogic 11y ago
      I am talking of the languages that are built on top of Lisp/Forth. I.e., you do not really need any syntax if your underlying implementation language is homoiconic.
- nickpsecurity 11y 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.
  - jstimpfle 11y ago
    The problem is that writing a good grammar requires understanding of parsers. (Also, real parsers tend to be hand-written, judging from open source language implementations (some have actually migrated from generated parsers to recursive descent in the past). There must be a reason).
jstimpfle 11y 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.
- sklogic 11y 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 11y 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.
- mafribe 11y ago
  Optimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy.
pjmlp 11y 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 11y 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 11y 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 11y 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-Kenneth-Louden/dp/0534939724 http://www.amazon.com/Compiler-Construction-Principles-Kenne...

pjmlp 11y 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 http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf It is a very instructive process.
- alex_muscar 11y 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 11y ago

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

melling 11y ago

I've got a small collection of compiler resources on Github: https://github.com/melling/ComputerLanguages/blob/master/compilers.org https://github.com/melling/ComputerLanguages/blob/master/com... I'll add more as they are posted.

RcouF1uZ4gsC 11y ago

Also, take a look at http://www.keithschwarz.com/interesting/ http://www.keithschwarz.com/interesting/ It is an amazing archive of all kinds of neat algorithms and data structures.

gravypod 11y ago
I'm pleasantly surprised. For academic work, this code is amazingly clean.

yyin 11y ago

matthewarkin 11y ago
There's self-reported data that some Stanford students have scrapped from CourseRank before it got shutdown. http://www.stanfordrank.com/cs143 http://www.stanfordrank.com/cs143
deleted 11y ago
[deleted]

ttandon 11y 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.

khushia 11y 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 11y 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 11y 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-process/honor-code-and-fundamental-standard#honor-code 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.
- 11y ago

ratsbane 11y 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 11y ago
Of course it is not okay unless you have permission.

sewercake 11y 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 11y ago

I remember while learning data structures and implementing them, I landed on http://www.keithschwarz.com/interesting/ 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.