13 ms·

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and par

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and parsing. Some argue that parsing is a microcosm of the rest of the compiler, since it requires one to transform a program from one representation to another. However, this message doesn't really come across when you're operating on highly unstructured input, and not doing any simplification passes. I think execution is really important for visualizing the effects of your work.

pjmlp 6y ago
Agreed, we did it all the way, but that was just in the course of a 5 years degree there was room to spend three semesters having compiler design related lectures, split between parser theory, denotational semantics, programming language history and implementing our own toy compiler.
JoelMcCracken 6y ago
This is what happened in my compilers class. We spent, like, the whole thing talking about grammars etc. Which is mind-numbingly boring (to me), and especially given a significant number of industry parsers are hand-rolled/recursive descent style, its not terribly useful information.
- JoelMcCracken 6y ago
  At the moment, some of us in the PGH FP group are working through https://www.cs.cmu.edu/~rwh/pfpl/ https://www.cs.cmu.edu/~rwh/pfpl/, and so far I vastly prefer it. It is math heavy, which I like for various personal reasons which are irrelevant here, but it also skips parsing!
- ahartmetz 6y ago
  Same here, at FU Berlin. We spent several weeks on LR and LALR parsers and such and, IIRC, even more than a week on regular expressions. Somehow we talked about two-address and three-address instructions, but never seemed to do any code generation, and certainly no optimization. It was very disappointing.
  - Nohortax 6y ago
    I agree
Jtsummers 6y ago
Yeah. I got really good at parsing to an AST and various semantic analysis steps. One course got too bogged down there and we never went further. Another got to the point of emitting machine code, but no optimizations. Only one, in grad school, actually went the whole way (prof could assume knowledge of parsing so that step was fast) with anything on optimizations. Given that parsing is also a critical part of many CS theory courses (or parsing theory), it was somewhat redundant to have spent so much time on it again in the compilers class given the overall time constraint, and frustrating to start on it and run past the planned time repeatedly in courses.
- kazinator 6y ago
  Optimizing work requires wrangling fairly complex, multi-faceted data structures like augmented graphs. Unless you do that in a very high level language in which that is as easy as possible, it's largely intractable for undergrad. When I did this stuff in school, it was C on Unix. Nobody was going to get to a debugged data flow analysis of basic blocks with all the liveness info, optional register allocation, DAG-driven CSE, and whatever topics out of the Dragon Book. Not in one or even two semesters, with undergrad-level C skills, and a full load of other courses. I think that working in Java wouldn't help much. You don't have premature free problem in Java, but in a batch compiler written in C, you can just avoid calling free.
waynesonfire 6y ago
And, it seems to be is a really understood problem that has efficient solutions.
- smasher164 6y ago
  Yes and no. The traditional goal of a parser that accepts valid inputs, and rejects invalid inputs is well understood. A more relevant goal of error-tolerant parsers that can respond quickly to incremental changes is still a wide research problem.
lisper 6y ago
> Too many compilers classes get bogged down in grammar classifications and parsing. Oh so very this. This has repercussions far beyond students who can't write compilers. It infects the entire culture of software engineering with people who think that syntax is everything, and who spend their lives designing grammars and writing parsers for them. The problem with that is for every new grammar, it's not just that you need a new parser, but some human needs to learn that grammar too if it's going to do you any good at all. So we have this proliferation of zillions of grammars, not just in programming languages, but in config files, data formats, etc. Two examples: XML and JSON are bad re-inventions of S-expressions. And the sieve language (which I am currently dealing with because I'm working on a new spam filter) is just an abomination from top to bottom.
- touisteur 6y ago
  And you need the gazillion things on top of a grammar. Error recovery, IDE, language server, formatter, all the memory bugs, all the semantics that's not described in a formal language (and you can't auto-generate code to check or request it), all the binding generators for other languages and linking conventions... Ugh I wish we had a standard tool for that, like a much much much expanded yacc + interpreter generator + batteries included... There's something with libadalang and its language-agnostic tooling langkit (https://github.com/AdaCore/lang https://github.com/AdaCore/lang kit) that is very seducing (write once generate much code).
  - touisteur 6y ago
    Previous discussion on automatic tool chain + interpreter generation : https://news.ycombinator.com/item?id=21917927 https://news.ycombinator.com/item?id=21917927
  - mingodad 6y ago
    I think that the now defunct dotGNU http://www.dotgnu.org/ http://www.dotgnu.org/ was trying to do it, one of the nice things it left us is libjit https://www.gnu.org/software/libjit/ https://www.gnu.org/software/libjit/
whateveracct 6y ago
the best PL/compilers classes i took were using Scheme, with a simple pattern matching macro [1] so there was no parsing. it was just s-exps. But you still got to write interpreters with different semantics & compilers. [1] https://gist.github.com/cbrooks90/125393006ec7bd137ff6364a9fc21db3 https://gist.github.com/cbrooks90/125393006ec7bd137ff6364a9f...
Jasper_ 6y ago
The overemphasis on parsing is ridiculous, with way too much theory that has little practical application. Parsing is boring, IMHO -- production compilers basically all use hand-written recursive descent, it's boring but it works just fine and is plenty readable, no need to replace it. The rest of the compiler is far more interesting, but a few people in the 60s got caught up on parsing theory based on limitations of their computers at the time, so there's a lot more formalism and theory and of course that's what academia teaches.
- todd8 6y ago
  After working with real-world compilers in industry I was surprised to hear CS professors that taught the compiler class say that no one should be writing parsers by hand because compiler writers should just build a table driven parser using YACC. The error messages are so much better coming out of recursive descent parsers. (I know that there are all sorts of mechanisms for better error messages, but back when I heard this statement there was nothing that really worked well. Does any compiler with good error messages today really use LR parsing?)
  - hctaw 6y ago
    This has been my experience as well, but I'd extend it to parsing in production. There are a million reasons why you need to write custom parsing code and 99% of them are faster and better implemented by hand than using a generator.
    - CalChris 6y ago
      Moreover, buggy parsing code is massive security hole.
      - tester756 6y ago
        why?
      - hctaw 6y ago
        well anything that takes untrusted input that might need to be validated with parsing is a massive security hole. Parsing generators don't fix this class of bug, they just change how it manifests.
todd8 6y ago
Absolutely. I became interested in compilers while in graduate school in the 70's and I spent many many hours studying Aho and Ulman's two volumes work on compilers that preceded their Dragon book [1]. The first volume was all about parsing, mostly LR (bottom-up) parsing and it's variations. These books resembled math books more than CS books. A few years before, Knuth had invented LR parsing [2] and I think that CS departments were still enthralled by the fascinating formal theory discovered around parsing. Aho and Ulman's Dragon Books on compiling are much more balanced. I was fascinated by the formal methods that could be used to specify a language's grammar and then the automated generation of a parser from the grammar. I even went so far as to write a LR parser generator in Fortran IV back then. Once I got into industry and was working in a group doing real-world compiler development I realized that there is a lot more than just lexical scanning and parsing going on in a compiler, it's tool chain, and runtime. Teaching compilers backwards sounds like a really good approach for students learning compilers. On a slightly broader but related topic, many programmers have never been exposed to assembly language, parameter passing mechanisms or how a program turns into a process. Anyone interested in system level programming in the real-world could benefit from Bryant and O'Hallaron's Computer Systems: A Programmer's Perspective [3]. This is not an easy book, but it is excellent and suitable for undergraduate CS students in their 3rd or 4th year. [1] Aho and Ulman, Compiling (Theory of Parsing, Translation and Compiling), Vol 1 (1972) & Vol 2 (1973), Prentice Hall. [2] https://en.wikipedia.org/wiki/LR_parser https://en.wikipedia.org/wiki/LR_parser [3] https://www.amazon.com/Computer-Systems-Programmers-Perspective-2nd/dp/0136108040 https://www.amazon.com/Computer-Systems-Programmers-Perspect...
- WalterBright 6y ago
  > Once I got into industry and was working in a group doing real-world compiler development I realized that there is a lot more than just lexical scanning and parsing going on in a compiler, it's tool chain, and runtime. Lexing and parsing is less than 1% of the job of building a compiler. (Completely ignoring tool chain and runtime.)
pklausler 6y ago
I've worked on production compilers for the bulk of my 40-year career. I prefer optimizers and code generators, but recently had to build a parser for modern Fortran for LLVM, and just used parser combinators to construct a recursive descent recognizer over a normalized contiguous source string in memory. The theory of formal languages is interesting but I think that the whole project of "compiler-compilers" from the 70's and 80's was working toward a solution that's inferior to where we are today with better tooling and less theory.
Animats 6y ago
That's a good point. Students get bogged down in parsing, which is a solved problem but a fussy one with way too much theory. Then the course glosses over optimization and code generation, which is where all the real work takes place.
hinkley 6y ago
I wanted to write a computer language when I was still young and did not quite realize what a commitment that was. Like buying a parrot instead of a hamster. Every compiler compiler description I could find rankled. Because I thought about how a code review works, how the human breaks down a block of code to figure out ah, this comma does not belong here. Then how to unpack that information for the tired intern (or classmate) so they understand why the compiler keeps saying "unexpected 'if' on line <five lines later>". Compiler grammars, it turns out, have absolutely no compassion for humans, their stupid opinions, or their squishy little language cortex. I found that quite offputting. Revolting, even, so I put it down and came back later. SGLR got close to "YES, I am not crazy!" but at the time I still thought 'write a PL' there was only one and it was not very good.
krueger71 6y ago
I remember back in the late 90's when I was studying Computer Science at Lund University, Sweden. They had a research focus in compilers and had their own Simula-compiler if I remember correctly. When they taught compilers, students first had to take the low level programming course where you needed to build a compiler back-end for an in-house IL. The first compiler course you could take after that was very focused on the practical aspects of building a front-end for the back-end you already had. Theory was pretty minimalistic at this point if I remember correctly. You got the hang of basic operator precendence parsing with a recommendation to use if for the expressions in our toy language and recursive decent for the rest. Of course this was almost like throwing someone at the deep end of the pool and se what happens. A grueling course that was renowned by students to be one of the more work intensive in the whole curriculum at that time. A lot of late nights in the computer lab for sure. Afterwards, when I had the second more theoretical compiler course, I did feel that all that practical hard work to make a fully functioning compiler with mostly elbow grease gave an appreciation of the theoretical constructs that could make this more tractable.

pjmlp 6y ago

Agreed, we did it all the way, but that was just in the course of a 5 years degree there was room to spend three semesters having compiler design related lectures, split between parser theory, denotational semantics, programming language history and implementing our own toy compiler.

JoelMcCracken 6y ago

This is what happened in my compilers class. We spent, like, the whole thing talking about grammars etc. Which is mind-numbingly boring (to me), and especially given a significant number of industry parsers are hand-rolled/recursive descent style, its not terribly useful information.

JoelMcCracken 6y ago
At the moment, some of us in the PGH FP group are working through https://www.cs.cmu.edu/~rwh/pfpl/ https://www.cs.cmu.edu/~rwh/pfpl/, and so far I vastly prefer it. It is math heavy, which I like for various personal reasons which are irrelevant here, but it also skips parsing!
ahartmetz 6y ago
Same here, at FU Berlin. We spent several weeks on LR and LALR parsers and such and, IIRC, even more than a week on regular expressions. Somehow we talked about two-address and three-address instructions, but never seemed to do any code generation, and certainly no optimization. It was very disappointing.
- Nohortax 6y ago
  I agree

Jtsummers 6y ago

Yeah. I got really good at parsing to an AST and various semantic analysis steps. One course got too bogged down there and we never went further. Another got to the point of emitting machine code, but no optimizations. Only one, in grad school, actually went the whole way (prof could assume knowledge of parsing so that step was fast) with anything on optimizations. Given that parsing is also a critical part of many CS theory courses (or parsing theory), it was somewhat redundant to have spent so much time on it again in the compilers class given the overall time constraint, and frustrating to start on it and run past the planned time repeatedly in courses.

kazinator 6y ago
Optimizing work requires wrangling fairly complex, multi-faceted data structures like augmented graphs. Unless you do that in a very high level language in which that is as easy as possible, it's largely intractable for undergrad. When I did this stuff in school, it was C on Unix. Nobody was going to get to a debugged data flow analysis of basic blocks with all the liveness info, optional register allocation, DAG-driven CSE, and whatever topics out of the Dragon Book. Not in one or even two semesters, with undergrad-level C skills, and a full load of other courses. I think that working in Java wouldn't help much. You don't have premature free problem in Java, but in a batch compiler written in C, you can just avoid calling free.

waynesonfire 6y ago

And, it seems to be is a really understood problem that has efficient solutions.

smasher164 6y ago
Yes and no. The traditional goal of a parser that accepts valid inputs, and rejects invalid inputs is well understood. A more relevant goal of error-tolerant parsers that can respond quickly to incremental changes is still a wide research problem.

lisper 6y ago

> Too many compilers classes get bogged down in grammar classifications and parsing. Oh so very this. This has repercussions far beyond students who can't write compilers. It infects the entire culture of software engineering with people who think that syntax is everything, and who spend their lives designing grammars and writing parsers for them. The problem with that is for every new grammar, it's not just that you need a new parser, but some human needs to learn that grammar too if it's going to do you any good at all. So we have this proliferation of zillions of grammars, not just in programming languages, but in config files, data formats, etc. Two examples: XML and JSON are bad re-inventions of S-expressions. And the sieve language (which I am currently dealing with because I'm working on a new spam filter) is just an abomination from top to bottom.

touisteur 6y ago
And you need the gazillion things on top of a grammar. Error recovery, IDE, language server, formatter, all the memory bugs, all the semantics that's not described in a formal language (and you can't auto-generate code to check or request it), all the binding generators for other languages and linking conventions... Ugh I wish we had a standard tool for that, like a much much much expanded yacc + interpreter generator + batteries included... There's something with libadalang and its language-agnostic tooling langkit (https://github.com/AdaCore/lang https://github.com/AdaCore/lang kit) that is very seducing (write once generate much code).
- touisteur 6y ago
  Previous discussion on automatic tool chain + interpreter generation : https://news.ycombinator.com/item?id=21917927 https://news.ycombinator.com/item?id=21917927
- mingodad 6y ago
  I think that the now defunct dotGNU http://www.dotgnu.org/ http://www.dotgnu.org/ was trying to do it, one of the nice things it left us is libjit https://www.gnu.org/software/libjit/ https://www.gnu.org/software/libjit/

whateveracct 6y ago

the best PL/compilers classes i took were using Scheme, with a simple pattern matching macro [1] so there was no parsing. it was just s-exps. But you still got to write interpreters with different semantics & compilers. [1] https://gist.github.com/cbrooks90/125393006ec7bd137ff6364a9fc21db3 https://gist.github.com/cbrooks90/125393006ec7bd137ff6364a9f...

Jasper_ 6y ago

The overemphasis on parsing is ridiculous, with way too much theory that has little practical application. Parsing is boring, IMHO -- production compilers basically all use hand-written recursive descent, it's boring but it works just fine and is plenty readable, no need to replace it. The rest of the compiler is far more interesting, but a few people in the 60s got caught up on parsing theory based on limitations of their computers at the time, so there's a lot more formalism and theory and of course that's what academia teaches.

todd8 6y ago
After working with real-world compilers in industry I was surprised to hear CS professors that taught the compiler class say that no one should be writing parsers by hand because compiler writers should just build a table driven parser using YACC. The error messages are so much better coming out of recursive descent parsers. (I know that there are all sorts of mechanisms for better error messages, but back when I heard this statement there was nothing that really worked well. Does any compiler with good error messages today really use LR parsing?)
- hctaw 6y ago
  This has been my experience as well, but I'd extend it to parsing in production. There are a million reasons why you need to write custom parsing code and 99% of them are faster and better implemented by hand than using a generator.
  - CalChris 6y ago
    Moreover, buggy parsing code is massive security hole.
    - tester756 6y ago
      why?
    - hctaw 6y ago
      well anything that takes untrusted input that might need to be validated with parsing is a massive security hole. Parsing generators don't fix this class of bug, they just change how it manifests.

todd8 6y ago

Absolutely. I became interested in compilers while in graduate school in the 70's and I spent many many hours studying Aho and Ulman's two volumes work on compilers that preceded their Dragon book [1]. The first volume was all about parsing, mostly LR (bottom-up) parsing and it's variations. These books resembled math books more than CS books. A few years before, Knuth had invented LR parsing [2] and I think that CS departments were still enthralled by the fascinating formal theory discovered around parsing. Aho and Ulman's Dragon Books on compiling are much more balanced. I was fascinated by the formal methods that could be used to specify a language's grammar and then the automated generation of a parser from the grammar. I even went so far as to write a LR parser generator in Fortran IV back then. Once I got into industry and was working in a group doing real-world compiler development I realized that there is a lot more than just lexical scanning and parsing going on in a compiler, it's tool chain, and runtime. Teaching compilers backwards sounds like a really good approach for students learning compilers. On a slightly broader but related topic, many programmers have never been exposed to assembly language, parameter passing mechanisms or how a program turns into a process. Anyone interested in system level programming in the real-world could benefit from Bryant and O'Hallaron's Computer Systems: A Programmer's Perspective [3]. This is not an easy book, but it is excellent and suitable for undergraduate CS students in their 3rd or 4th year. [1] Aho and Ulman, Compiling (Theory of Parsing, Translation and Compiling), Vol 1 (1972) & Vol 2 (1973), Prentice Hall. [2] https://en.wikipedia.org/wiki/LR_parser https://en.wikipedia.org/wiki/LR_parser [3] https://www.amazon.com/Computer-Systems-Programmers-Perspective-2nd/dp/0136108040 https://www.amazon.com/Computer-Systems-Programmers-Perspect...

WalterBright 6y ago
> Once I got into industry and was working in a group doing real-world compiler development I realized that there is a lot more than just lexical scanning and parsing going on in a compiler, it's tool chain, and runtime. Lexing and parsing is less than 1% of the job of building a compiler. (Completely ignoring tool chain and runtime.)

pklausler 6y ago

I've worked on production compilers for the bulk of my 40-year career. I prefer optimizers and code generators, but recently had to build a parser for modern Fortran for LLVM, and just used parser combinators to construct a recursive descent recognizer over a normalized contiguous source string in memory. The theory of formal languages is interesting but I think that the whole project of "compiler-compilers" from the 70's and 80's was working toward a solution that's inferior to where we are today with better tooling and less theory.

Animats 6y ago

That's a good point. Students get bogged down in parsing, which is a solved problem but a fussy one with way too much theory. Then the course glosses over optimization and code generation, which is where all the real work takes place.

hinkley 6y ago

I wanted to write a computer language when I was still young and did not quite realize what a commitment that was. Like buying a parrot instead of a hamster. Every compiler compiler description I could find rankled. Because I thought about how a code review works, how the human breaks down a block of code to figure out ah, this comma does not belong here. Then how to unpack that information for the tired intern (or classmate) so they understand why the compiler keeps saying "unexpected 'if' on line <five lines later>". Compiler grammars, it turns out, have absolutely no compassion for humans, their stupid opinions, or their squishy little language cortex. I found that quite offputting. Revolting, even, so I put it down and came back later. SGLR got close to "YES, I am not crazy!" but at the time I still thought 'write a PL' there was only one and it was not very good.

krueger71 6y ago

I remember back in the late 90's when I was studying Computer Science at Lund University, Sweden. They had a research focus in compilers and had their own Simula-compiler if I remember correctly. When they taught compilers, students first had to take the low level programming course where you needed to build a compiler back-end for an in-house IL. The first compiler course you could take after that was very focused on the practical aspects of building a front-end for the back-end you already had. Theory was pretty minimalistic at this point if I remember correctly. You got the hang of basic operator precendence parsing with a recommendation to use if for the expressions in our toy language and recursive decent for the rest. Of course this was almost like throwing someone at the deep end of the pool and se what happens. A grueling course that was renowned by students to be one of the more work intensive in the whole curriculum at that time. A lot of late nights in the computer lab for sure. Afterwards, when I had the second more theoretical compiler course, I did feel that all that practical hard work to make a fully functioning compiler with mostly elbow grease gave an appreciation of the theoretical constructs that could make this more tractable.