4 ms·

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 unin

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.

mhh__ 6y ago
The semantic analysis is by far and away the hardest thing day to day. Parsing is easy
- azhenley 6y ago
  Parsing most certainly is *not* easy for someone new to compilers. My students remind me of that all the time.
  - jcranmer 6y ago
    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.)
    - mhh__ 6y ago
      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.
      - marcosdumay 6y ago
        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.
        vidarh 6y ago
        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.
  - mhh__ 6y ago
    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.
- norswap 6y ago
  I'd say parsing is easier when you know how to do it, but getting to understand it the first time is harder.
chrisseaton 6y ago
> 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.
- zabzonk 6y ago
  > I've been working professionally on a single compiler full-time for seven years. Which one?
  - chrisseaton 6y ago
    TruffleRuby (says in my profile.)
- MaxBarraclough 6y ago
  Things would be different if you were in the business of, say, keeping g++ up to date with the latest C++ spec, right?
  - chrisseaton 6y ago
    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/Parse/Parser.cpp 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!
    - jcranmer 6y ago
      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).

mhh__ 6y ago

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

azhenley 6y ago
Parsing most certainly is *not* easy for someone new to compilers. My students remind me of that all the time.
- jcranmer 6y ago
  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.)
  - mhh__ 6y ago
    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.
    - marcosdumay 6y ago
      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.
      - vidarh 6y ago
        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.
- mhh__ 6y ago
  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.
norswap 6y ago
I'd say parsing is easier when you know how to do it, but getting to understand it the first time is harder.

chrisseaton 6y ago

> 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.

zabzonk 6y ago
> I've been working professionally on a single compiler full-time for seven years. Which one?
- chrisseaton 6y ago
  TruffleRuby (says in my profile.)
MaxBarraclough 6y ago
Things would be different if you were in the business of, say, keeping g++ up to date with the latest C++ spec, right?
- chrisseaton 6y ago
  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/Parse/Parser.cpp 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!
  - jcranmer 6y ago
    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).