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

Advanced Compilers: Self-Guided Online Course

cs.cornell.edu

Post reply on HN
Print view View original

161–170 of 241 posts

Re: Advanced Compilers: Self-Guided Online Course

#161

Post by munificent »

nialv7 wrote: post #74
ibains wrote: post #59

I’ve worked on multiple compilers (optimizations expert) at MSFT on VS and CUDA and gave developed a DSL and worked on Database Compilers. I can’t hire compiler people with right skills. We’re building an IDE and those parsers are written differently, and we use Scala packrat parser combinators. These courses teach very little judgement or industry relevant stuff. When do you use packrat parser vs LALR vs LL? Good lu…

No offence, but parsing (in a compiler, not in general) is probably the most boring part of a compiler. As this is a PhD course, I'd expect the goal of it to be preparing students for research in the field, not writing parsers for some industrial company. Also, there are definitely courses that teach you how to write a parser. But we usually don't call them advanced.

> No offence, but parsing (in a compiler, not in general) is probably the most boring part of a compiler.

Not if you're writing an IDE. Writing a batch mode parser that takes an entire correct source file and produces an AST is easy. Writing a parser that instaneously handle producing an updating AST while the user is typing in the middle of the program while still allowing semantic analysis to occur and without vomiting out a pile of extraneous errors or giving up entirely is a lot harder.

Re: Advanced Compilers: Self-Guided Online Course

#162

Post by munificent »

brundolf wrote: post #54
yla92 wrote: post #12

On the related note, what would you guys recommend as an introduction to compilers, say for beginners?

Crafting Interpreters has been great. It starts with an AST-walking interpreter (in Java), so you get to focus on parsing and the simplest form of interpretation, and then it moves to a bytecode interpreter (in C) so you get to learn about compiling to a more primitive target via a lower-level language (much of which should translate to a "real" compiler). Very approachable, has lots of side-context and an entertaini…

Author here. Also you can read the whole book online for free: http://craftinginterpreters.com/

Re: Advanced Compilers: Self-Guided Online Course

#163

Post by remexre »

vector_spaces wrote: post #104
vector_spaces wrote: post #96

Earlier quoted context omitted.

I saw this great interview recently with Anders Hejlsberg at MSFT on how modern compiler construction differs from what is taught in traditional University courses. Is this what you're alluding to? After watching that interview, it's strange to read a comment like yours. While the architecture is completely different, it doesn't frankly seem like that big a leap to go from "senior engineer with X years working on thi…

I will say that I asked Shriram Krishnamurti about why books on interpreters and compilers tend to avoid the question of parsing like the plague and found his response a little unsatisfactory. All these celebrated texts like SICP, EOPL, and Lisp in Small Pieces avoid the question of parsing altogether by focusing on s-expression based languages. His response was effectively that parsing is over-emphasized in other bo…

A full half of the compilers course I took in undergrad was about {LA,S,}LR; I think "parsing is over-emphasized" is alive and well... That said, it didn't cover non-table-based parsing much. (On the other hand, I'm unaware of a non-table-based parsing algorithm that can statically warn you about problems with the grammar (ambiguities etc).)

Re: Advanced Compilers: Self-Guided Online Course

#164

Post by petr_tik »

mathattack wrote: post #159
bachmeier wrote: post #76

Earlier quoted context omitted.

> I’d like to sit down all university professors who teach compiler courses and teach them a course on what’s relevant. I don't teach compiler courses, but I'm an academic, and I do keep in touch with industry people to find out what's important for my data analysis course. A couple of big problems with your proposal: 1. Time variation in "what industry wants". This year one thing's hot, the next year it's something…

My two cents - what’s useful for employers is giving students the confidence to jump into the code and figure it out. By this measure, what’s relevant for a compilers course isn’t the material itself. It’s that it’s structured to force the students to figure certain things for themselves. There are college hires who need to be spoon fed, and college hires who just need mentorship and direction. Group two are invaluab…

Andy Pavlo of the CMU DB fame echoed this in one of the intro video lectures to one of his courses. He said his contacts in the industry valued people, who can navigate a large codebase productively. Most uni courses seem to involve writing a "toy" solution from scratch, which is seldom the case in professional programming.

He designed the course to be an exercise in working in an existing codebase that one needs to understand before adding features.

I guess that is one of the many reasons CMU grads kick open the door into many companies.

Re: Advanced Compilers: Self-Guided Online Course

#165

Post by Kranar »

WalterBright wrote: post #160
Kranar wrote: post #149

Earlier quoted context omitted.

Strictly speaking, D is not context free nor is any statically typed programming language. That said most languages, including D, have supersets that are context free and can be used to build an AST which can then be refined further with context sensitive checks (ie. variables are used after declaration) and then even further with type checks. Many language tools don't need a full blown language parser and can get by…

I suppose we could argue about the definition of context free, but the compiler lexes it without any reference to the parser, and the parser builds the AST without any reference to symbols or semantic meaning. > spell checking ... using context-free parsers Only up to a point. D's spell checker uses the symbols in scope as its "dictionary". This means it is very good at guessing what you meant instead of what is type…

A context free grammar has a formal and rigorous definition. One way to see that Dlang does not have a strictly context free grammar for its AST is the following snippet of code:

A[B] C;

That is parsed differently depending on whether B is a constant integer expression in which case it parses to the declaration of an array of type A with a size of B, or whether B is a typename in which case it parses into an hash map with keys of type B and values of type A.

This disambiguation can not be specified by the context free grammar and instead must be delayed until the semantic analysis (which is usually defined by a context sensitive grammar).

Pretty much all statically typed languages work this way with various kinds of ambiguities. In practice, it's not a particularly big deal. But that's kind of my point, there's no need to work exceedingly hard to force a language construct to be context free, especially if making it context free results in a lack of readability or awkward syntax.

It's perfectly fine to specify a superset of the language that is context free, parse an AST for the superset of that language and then resolve AST ambiguities in later phases, such as the semantic analysis phase or the type checking phase. Almost any tool written to assist an IDE with autocompletion or other functionality will have no problem working with the language superset.

Re: Advanced Compilers: Self-Guided Online Course

#166

Post by petr_tik »

nojvek wrote: post #154

I wish they’d be more courses on compilers that also serve as language servers. The current world is moving towards a phase where a language needs IDE tooling such as compilers, linters, formatters, REPL, language servers, debuggers and profilers. Would love to see a high level course that covers how to build the tooling for a great developer experience.

As i mentioned in another thread, a uni course that has students work on an existing codebase instead of writing something from scratch might be even better - though harder to grade.

Imagine if one could do a major feature contribution to clangd/pyls/rust-analyzer as part of their advanced compilers course. The student gets a better understanding of (open-source) software development practices, gains a deeper proficiency in the language (not just the APIs), the project brings new contributors and users (including the student herself) benefit from the new feature.

Double bubble!

Re: Advanced Compilers: Self-Guided Online Course

#167

Post by remexre »

vector_spaces wrote: post #96
ibains wrote: post #59

I’ve worked on multiple compilers (optimizations expert) at MSFT on VS and CUDA and gave developed a DSL and worked on Database Compilers. I can’t hire compiler people with right skills. We’re building an IDE and those parsers are written differently, and we use Scala packrat parser combinators. These courses teach very little judgement or industry relevant stuff. When do you use packrat parser vs LALR vs LL? Good lu…

I saw this great interview recently with Anders Hejlsberg at MSFT on how modern compiler construction differs from what is taught in traditional University courses. Is this what you're alluding to? After watching that interview, it's strange to read a comment like yours. While the architecture is completely different, it doesn't frankly seem like that big a leap to go from "senior engineer with X years working on thi…

Huh, he's talking a lot about how doing everything incrementally is infeasible; isn't this how Rust's compiler/tooling infrastructure works?

Re: Advanced Compilers: Self-Guided Online Course

#168

Post by haberman »

morelisp wrote: post #128
throwaway_pdp09 wrote: post #125

Earlier quoted context omitted.

Does that issue go away if you use packrat vs some other means?

Packrat parsers are notably faster than recursive descent parsers (also critical for IDE use) and by turning them "inside out" (replacing their memoization with dynamic programming) you get a pika parser which has very good recovery ability. There are varying techniques to improve error recovery for all forms of parsing but hacked-up recursive descent (certainly the most common kind of parser I still write for my hac…

> Packrat parsers are notably faster than recursive descent parsers

I think this needs to be qualified. I don't think a packrat parser is going to beat a deterministic top-down parser. Maybe the packrat parser will win if the recursive descent parser is backtracking.

Re: Advanced Compilers: Self-Guided Online Course

#170

Post by kingaillas »

Kranar wrote: post #149
WalterBright wrote: post #144

Earlier quoted context omitted.

Languages being context sensitive results from hacking in new language features. It's a constant struggle to keep D context free :-/

Strictly speaking, D is not context free nor is any statically typed programming language. That said most languages, including D, have supersets that are context free and can be used to build an AST which can then be refined further with context sensitive checks (ie. variables are used after declaration) and then even further with type checks. Many language tools don't need a full blown language parser and can get by…

You realize the poster you are responding to is the creator of D? And has spend his career writing compilers? I'm not sure he needs to have someone explain what a context free grammar is.
Post reply on HN