Hacker News Reader

Comment by hvidgaard | Hacker News Reader

Going from a grammar to an AST is the first and one of the hardest step IMO. And there is plenty of open source tools for exactly that and in general it is uninteresting and boring.

Transforming the AST to something that can be used to emit instructions is the major thing to focus on IMO. Getting to an AST that only use very simple primitives that enables general optimizations and emitting code is hard and a different task every time.

View on HN

> Going from a grammar to an AST is the first and one of the hardest step IMO

I can give some concrete data about this. I've been working professionally on a single compiler full-time for seven years.

I think out of all that time I think I've spent probably less than a week dealing with lexer and parser issues all together. I'd say in practice parsing is vanishingly insignificant.

I guess it's a difference who the course audience is?

I'd wager most people who take a compilers 101 class at uni won't end up working on compilers for their careers. For them, some basic knowledge of parsing will likely serve them well, since designing and parsing file formats and network protocols etc. is something quite a lot of people need to do now and then (perhaps less so nowadays that you can find a library or framework to do almost anything you might want to, but still). These people will, again, be well served by some basic intuition how optimizing compilers work, but most likely they will never need to implement such a thing themselves.

OTOH, if working on optimizing compilers is your career, sure, the parser is likely something that occasionally needs some minor updating, but the vast majority of time you spend on the middle/back-end optimization passes. Very different focus from the average Joe programmer taking a compilers 101 class at uni.

I think it could possibly be a good idea to have separate parsing and compiler courses, and teach parsing as a more general technique, and have it as a prerequisite for compilers.

Couldn't agree more. You've spent a lot more time on it than me, but when I started writing my blog posts about writing a compiler this was the reason I started writing about code-generation first -- far too few resources focuses on that part, despite it being far harder than the lexing and parsing.

It's in the context of a compiler course. When I was TA I've never had students that found it easy. Semantic analysis and optimizations are as easy or hard as the course material dictates. I believe the focus was on the first part because for the most part, writing a small DSL and converting that into an AST is relevant for most CS professionals, where as I think semantic analysis and optimization are only day-to-day relevant for the small subset of people that work on compilers.

Things would be different if you were in the business of, say, keeping g++ up to date with the latest C++ spec, right?

I have to keep up with Ruby changes.

But even for example the parser in clang doesn't seem to be touched very often.

https://github.com/llvm/llvm-project/commits/main/clang/lib/...

Take a look at the commits there and see how much each changes the parser vs the rest of the compiler.

Also, at the bottom of page 2 for parser changes you're already all the way back in 2017!

It's somewhat disingenuous to link only clang/lib/Parse/Parser.cpp--a lot of the parsing code isn't in Parser.cpp, but other files in lib/Parser. Look at the entire directory, and you get about 1 commit per few days (somewhere between daily and weekly).

I think a lot of the commits you're seeing there are really more semantic analysis and tooling rather than actual parsing - they just interact with the parser.

I can only offer my experience - and I think most of my colleagues in the field seem to say the same thing.

> I've been working professionally on a single compiler full-time for seven years.

Which one?

TruffleRuby (says in my profile.)

The semantic analysis is by far and away the hardest thing day to day. Parsing is easy

I'd say parsing is easier when you know how to do it, but getting to understand it the first time is harder.

Parsing most certainly is *not* easy for someone new to compilers. My students remind me of that all the time.

Lexing and parsing probably falls into the category of "obvious once you learn it, mystifying until then."

(Although, that said, compiler courses could probably do well to ditch a lot of the LL(1)/LR(1) parsing theory to focus on other topics instead. You still need to teach grammars, and focus a bit on how to actually parse grammars to AST under recursive descent, including expression precedence, but you could probably excise a lot of the parser generator theory.)

I know embarrassingly little parser theory - I definitely couldn't write a decent parser generator without looking it up in a book for a few hours - but at least there is a theory: Semantic analysis has lots of mathematical symbology to describe it, doesn't help you write code for the most part.

As strange as it looks, parser theory is not very relevant on practice for writing parsers. You just use some parser generator or a parser combinators library if your language allows them, and you won't have many problems (except for maybe they being slow).

It is way more relevant for optimizing parsers performance and for designing languages syntax.

And when hand-writing parsers, it's fairly common to just use simple recursive descent and all it a day.

Anyone can "invent" recursive descent with fairly little prodding about how to divide and conquer.

That's true but it is one and done when you get it working, as opposed to sema which is a constantly changing monster in many languages.

Reply on news.ycombinator.com