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

C Compiler from Scratch

github.com

Post reply on HN
Print view View original

41–50 of 68 posts

Re: C Compiler from Scratch

#41

Post by einpoklum »

IMHO, you shouldn't write a compiler 'from scratch". You should write it using lots of libraries offering supporting functionality, such as:

* Grammar-based parsing

* Tree and graph representation, traversing

* (Possibly) A tree or graph grammar library

* Cross-platform filesystem support

* Combinatorial algorithm implementations (some of them may get used in various optimizers)

* terminal support (for formatted output)

and so on. And of course - there's the standard (C) library which one should also not count as "scratch".

Now, as an exercise, it is not-uninteresting to also implement parts of some of those, but it's not clear that "from scratch" is the most pedagogically-useful approach.

Re: C Compiler from Scratch

#42

Post by mywittyname »

Koshkin wrote: post #36
nicoster wrote: post #20

Earlier quoted context omitted.

Is that an issue given the course is free?

Yes. Not everyone likes to give away their personal information - especially (paradox) in exchange for access to a free resource.

Junk email accounts are helpful for this.

Re: C Compiler from Scratch

#43

Post by kerkeslager »

I've been sort of working on a compiler side project for years, and my observation of the materials out there is that they all seem to get caught up in bikeshedding. Parsing just isn't that hard of a problem, and with a vague understanding of what a recursive descent parser is, just about any reasonably-skilled developer can figure out how to write a good-enough parser. EBNF, parser generators, etc. is just noise, yet this is where every compiler tutorial I've come across spends most of its time.

The real meat of any compiler is generation, and that's hard, starting with the fact that if you're new at this you probably don't know assembly. And assembly is death by a thousand cuts: sure, you can probably figure out how to do loops and ifs pretty quickly, but the subtleties of stack allocation, C-style function calling convention, register allocation, etc. all add tiny bits of "messiness" that each add a little bit of complexity to your code. Managing that complexity is the real challenge, and I haven't come across a compiler course that really addresses this.

Re: C Compiler from Scratch

#44

Post by fjfaase »

GuB-42 wrote: post #34
fjfaase wrote: post #21

I feel that many introductions to scanning and parsing are based on old techniques when memory were scarce. In those times storing your files in memory, was simply impossible. But we live in times where we have gigabytes of ram and there are not many projects that could not be read into memory. (Tell me about a project that has a gigabyte of source files, please.) So, why not assume your input to be stored in a strin…

The parser stores the entire AST in memory, it is not acting as if it was scarce. As for the idea of not starting with a string but instead reading the file on the fly, I think it is actually simpler. The point of storing the entire file in memory is to enable going back and forth, but why would you want to do that? State machine based parsers are fast, robust, and based on a solid theoretical grounds, at least for "…

I do not know, if you took time to look at the next function in https://github.com/DoctorWkt/acwj/tree/master/01_Scanner , but there is a Putback variable, which seems to imply that the scanner goes back (at most one character). Also having to pass around the result of next, instead of having a current pointer, or at least a current character, makes things more complicated (I feel). Being able to look ahead, without having to consume a character, (I feel) is easier, also for keeping track of the correct line and column number. Note that if Putback is equal to '\n', the Line has already be incremented. Seems that this could lead to errors being reported on the wrong line for terminal symbols at the end of the line.

Re: C Compiler from Scratch

#45

Post by chrisseaton »

giancarlostoro wrote: post #40
chrisseaton wrote: post #28

Earlier quoted context omitted.

> Course I always heard of the dragon book and have wanted it since. I wouldn’t read it except out of historical interest - it’s not how we build compilers anymore, with its super-heavy emphasis on parsing and syntax-directed translation.

Is there something close to it in the modern sense then?

Not really! It's a bit of a problem that there isn't a good compiler book at the moment, in my opinion. Everything is either far too basic, or too specialised. If a practising programmer wanted to learn compiler and write a compiler today I don't know what they could easily look at. They'd have to read a lot and then get a lot of extra guidance about what to use and what not to use.

Re: C Compiler from Scratch

#46

Post by jcranmer »

kerkeslager wrote: post #43

I've been sort of working on a compiler side project for years, and my observation of the materials out there is that they all seem to get caught up in bikeshedding. Parsing just isn't that hard of a problem, and with a vague understanding of what a recursive descent parser is, just about any reasonably-skilled developer can figure out how to write a good-enough parser. EBNF, parser generators, etc. is just noise, ye…

Compiler courses do spend way too much time on parsing, but there is real value in learning it. An LR(k) or LL(k) grammar is guaranteed to be unambiguous, so knowing how to construct one is the best way to design a language, even if parser generators are rarely used to actually build parsers. Furthermore, the industry standard to describe the syntax of a programming language is some form of BNF grammar, with semantics usually given by prose explanations of the operational semantics for every production in the grammar.

> starting with the fact that if you're new at this you probably don't know assembly

Most university curricula put assembly programming at a sophomore-level course (generally as part of an intro to computer architecture course), while compilers are a senior-level course. As a result, most compiler courses will assume a background knowledge of assembly.

Re: C Compiler from Scratch

#47

Post by giancarlostoro »

chrisseaton wrote: post #45
giancarlostoro wrote: post #40

Earlier quoted context omitted.

Is there something close to it in the modern sense then?

Not really! It's a bit of a problem that there isn't a good compiler book at the moment, in my opinion. Everything is either far too basic, or too specialised. If a practising programmer wanted to learn compiler and write a compiler today I don't know what they could easily look at. They'd have to read a lot and then get a lot of extra guidance about what to use and what not to use.

What are some good resources that cover basics and get very specialized? I wouldn't mind reading through some, I just wanna read everything I can but as long as it's relevant to today, I may still get the dragon book though.

Re: C Compiler from Scratch

#48

Post by jcranmer »

fjfaase wrote: post #21

I feel that many introductions to scanning and parsing are based on old techniques when memory were scarce. In those times storing your files in memory, was simply impossible. But we live in times where we have gigabytes of ram and there are not many projects that could not be read into memory. (Tell me about a project that has a gigabyte of source files, please.) So, why not assume your input to be stored in a strin…

A complete debug, unoptimized build of LLVM/Clang requires about 50GB of disk space. And LLVM/Clang is on the smaller end of large projects; the Linux kernel, OpenJDK, and Mozilla are larger open source projects, and the private repositories of people like Microsoft, Facebook, and Google are an order of magnitude, or two, above those.

Keeping the entire program string in memory doesn't really buy you anything. You still need your AST and other IR representations, and location information that is stored as a compressed 32-bit integer is going to be more memory-efficient than a 64-bit pointer anyways. Furthermore, scanning and parsing is very inherently a process that requires proceeding through your string linearly, so building them on an iterator that implements next() and peek() (or unget()) doesn't limit you.

Re: C Compiler from Scratch

#49

Post by 0xffff2 »

Koshkin wrote: post #39

I remember the time when writing a compiler for Pascal - complete with a code generator (for 8086) - was a routine assignment for CS students at the end of the first semester of the second year.

Granted is was for a toy language, not Pascal, but I had to write a complete compiler for my CS undergrad ~3 years ago.

Re: C Compiler from Scratch

#50

Post by abecedarius »

zabana wrote: post #29

Do you know of similar types of tutorials / repos except for language parsers (like markdown or json) ? How difficult would it be to implement in comparison to a compiler ? Where should I start looking ? (I want to build a compiler at some point but I want to get my feet wet building a simple language parser first) Thanks in advance

Try the first few chapters of https://inf.ethz.ch/personal/wirth/CompilerConstruction/Comp... and apply it to the grammar at https://www.json.org/json-en.html
Post reply on HN