7 ms·
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.
by 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 agoTrue, 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 agoand http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/blog/entries/parsing_the_solved_prob...
- groovy2shoes 11y agoand http://matt.might.net/articles/parsing-with-derivatives/ http://matt.might.net/articles/parsing-with-derivatives/
- agumonkey 11y agoI forgot how beautiful this was.
- nickpsecurity 11y agoThat'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 agoCompilers 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 agoRight, 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 agoThat'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 agoYou should have done it in a homoiconic language like Scheme, where nobody would be puzzled by a notion of an AST.
- mafribe 11y agoThen 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 agoYou have to start somewhere. Code optimization is utterly useless if you can't parse code.
- sklogic 11y agoQuite 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.
- nickpsecurity 11y agoSo 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 agoThe 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 agoMost 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 agoI 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 agoOptimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy.
- pjmlp 11y agoYeah, 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 agoThe second half of the 2nd edition of the Dragon Book is pretty good, especially if you think of it as learning math.
- userbinator 11y agoI 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.