Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Teaching Compilers Backward

blog.sigplan.org

Post reply on HN
Print view View original

31–40 of 87 posts

Re: Teaching Compilers Backward

#31

Post by touisteur »

lisper wrote: post #22
smasher164 wrote: post #3

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…

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

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 kit) that is very seducing (write once generate much code).

Re: Teaching Compilers Backward

#32

Post by carapace »

Yeah, FWIW, I think you should start at the bottom[1] with bits, bytes, RAM, and a wee CPU (like Wirth's RISC for Project Oberon[2]) and then META-II [3] seems like the best way forward to conventional languages. (Or go with Forth and Joy and head right past Lambda Calculus and straight to Category Theory[4].)

On the other hand you could start with predicate logic and teach Prolog as a calculator for same, then develop all the low- and mid-level software (your emulator and compiler) using Prolog, then implement a Prolog interpreter in your language to close the loop.

[1] http://phoenixbureau.github.io/PigeonComputer/curiculum.html

[2] https://pythonoberon.readthedocs.io/en/latest/

[3] https://en.wikipedia.org/wiki/META_II

[3] http://conal.net/papers/compiling-to-categories/

Re: Teaching Compilers Backward

#33

Post by todd8 »

smasher164 wrote: post #3

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…

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

[3] https://www.amazon.com/Computer-Systems-Programmers-Perspect...

Re: Teaching Compilers Backward

#34

Post by todd8 »

Jasper_ wrote: post #28
smasher164 wrote: post #3

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…

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…

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?)

Re: Teaching Compilers Backward

#35

Post by touisteur »

touisteur wrote: post #31
lisper wrote: post #22

Earlier quoted context omitted.

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

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 generato…

Previous discussion on automatic tool chain + interpreter generation : https://news.ycombinator.com/item?id=21917927

Re: Teaching Compilers Backward

#37

Post by Nohortax »

ahartmetz wrote: post #29
JoelMcCracken wrote: post #9

Earlier quoted context omitted.

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.

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.

I agree

Re: Teaching Compilers Backward

#38

Post by hctaw »

todd8 wrote: post #34
Jasper_ wrote: post #28

Earlier quoted context omitted.

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…

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 hea…

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.

Re: Teaching Compilers Backward

#39

Post by smasher164 »

Jasper_ wrote: post #28
smasher164 wrote: post #3

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…

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…

I think if schools want to give a taste of the parsing->execution flow, they should have students implement an NFA based regular expression engine. No fancy features like captures and named character classes, just the primitive operations will do.

Regular expression syntax is context-free anyways, so they could use grammars if they wanted. Then again, you have to wonder if all of this should be covered by a theory or PL class instead.

Re: Teaching Compilers Backward

#40

Post by pklausler »

smasher164 wrote: post #3

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…

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.
Post reply on HN