Hacker News Reader

Comment by protomikron | Hacker News Reader

My humble opinion: do not get the Dragon book - it puts too much focus on parser theory and implementation which is in my opinion not the hard part of compiler construction.

Most modern languages use a handwritten recursive descent parser anyway and the interesting part starts after you have the AST (code generation and register allocation).

View on HN

> My humble opinion: do not get the Dragon book - it puts too much focus on parser theory and implementation

This is my strong opinion as well. Almost everyone fixates on parsing.

I've been working on an interpreter/compiler full time since 2013, so coming up for eight years. I think I've spent maybe three or four days working on the parser. It's a vanishingly small part of the job.

I wish compiler courses started with an AST, and then parsing was a separate course unrelated to compilers.

Yes - it's probably the case, because there is nice theory behind it (DFAs for lexing and grammars for parsing).

What I can really recommend (and me and others have recommended it already countless times) is TECS: The elements of computing systems (also know as "Nand2Tetris"). Although it also covers other parts like the hardware stuff it lets you implement

    - an assembler
    - a VM
    - a compiler that compiles a simplified Java-like language to this VM

It takes a bottom-up approach, but if you go through all projects you get a really good view about the big picture. However as it does code generation via an intermediate VM language it doesn't really touch register architectures as a compilation target. Anyway I highly recommend that book.

The small amount of time spent on writing the parser might have something to do with how well-understood that area of computer science is. If nobody had ever written those books which were mostly about parsing, then maybe writing the parser would be the hardest part.

I don’t think so. Almost everyone abandons all the theory and just writes recursive descent. It's not the case that they're using it but have just come to see it as normal. They're not using it.

Recursive descent is theory. If you put someone new to parsing on the job, you'd get a mess, not RD.

Yeah, I always write the grammar before writing the recursive descent parser. I can't imagine doing otherwise. It would be a mess.

I'd go further and say that for most people, the first time you read or write a context-free grammar is when you're trying to write a parser. So the theory is motivating the practice.

In my practical experience students naturally re-invent recursive descent.

Yes. A lot of one semester compiler classes spend way too much time on lexing and parsing. Amusingly, their coverage of parsing is limited to LALR. It almost seems as if profs are thinking, if I had to suffer through LALR(1) table generation then you're going to have suffer through it as well.

By comparison, at Berkeley they recreate 61C Machine Structures every few years. Out goes the unimportant, in comes the new.

Lexing and parsing isn't even a vanishingly small part of the job. It's usually someone else's job. Someone who works on LLVM code generation for the XYZ processor is the wrong person to keep the Clang front end up to date with the latest C++ committee's standard iteration.

They should push DFAs and grammars into theory classes. That said, I do like the 2nd edition of the Dragon book, particularly the later chapters.

In my experience, compilers are taught over three semesters or so: lexing/parsing is one course (or rolled into a prerequisite), the standard compilers is the second, and advanced (graduate-level) compilers is the third course.

Berkeley just has CS164 [1] which is all in one. They haven't taught a graduate compiler section in years (decades?). Stanford is on the quarter system. They have an even more compressed single quarter compiler class, CS143 [2], but they also have a graduate advanced topics class, CS243 [3] as well. Moreover, CS243 doesn't require 143 as a prerequisite. As an aside, Berkeley is very strong at computer architecture (RISC, RISC-V, ...) while Stanford is very strong at compilers (Aiken, Lam, Ullman, Hennessy, ...)

http://www-inst.eecs.berkeley.edu/~cs164/sp19/ https://web.stanford.edu/class/cs143/index2018.html https://suif.stanford.edu/~courses/cs243/

> which is in my opinion not the hard part of compiler construction

It depends on whether you are compiling C++ or not. ;-)

Parsing C++ is not that hard if you use hand rolled recursive descent parser. On the other hand hacking some parser generator framework to be able to parse C++ is hard and IMO mostly pointless busywork.

> hacking some parser generator framework ... is hard and IMO mostly pointless busywork

Bingo. We spent decades formalising and automating something... that was never that hard in the first place.

In context of parsing the situation when all the state machine/language theory has it's place is when you have some reason to care about compiler passes and generate output while reading input. That is, when you are not constructing some intermediate in-memory representation of whole compilation unit, presumably because you are running on system with (very) limited memory. For programming language compilers this ceased to be interesting limitation in 80's.

Not that hard? It's literally undecidable!

https://news.ycombinator.com/item?id=21154565

That's not what 'hard' means in this context. Requiring template instantiation (or some other interplay I'm not aware of) doesn't make parsing harder - it just means it can't be done independently.

And what's more that kind of interplay is easier outside a parser framework!

Many languages are not very pure for parsing. If you're writing a parser using lex and bison this means bending over backwards to make it work.

Reply on news.ycombinator.com