Live data from Hacker News

C Compiler from Scratch

github.com

61–68 of 68 posts

Re: C Compiler from Scratch

#61
post #51

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…

I couldn't agree more with this, it's very frustrating. I recently worked through most of the "make a lisp" guide [0], and it was excellent introduction to a simple lisp interpreter. But now I want to try my hand at a compiler (either producing machine code or maybe custom VM bytecode) and the lack of resources for that is bewildering. Just as you say, I've found that most online texts on compilers seem to spend most…

Lisp in Small Pieces https://www.amazon.com/dp/0521545668/ref=cm_sw_r_other_apa_i... is excellent, and I think would help.

Re: C Compiler from Scratch

#62
post #53

A fantastic book along these lines is Allen Holub's "Compiler Design in C". It's old (1990) and out of print, but you can get the PDF for free from Holub's site [1]. Over the course of the book, a C compiler is developed. To handle lexical analysis and parsing, tools similar to lex and yacc are developed. Here's an excerpt from the preface to give an idea of the approach: > This book presents the subject of Compiler…

Thanks for the link. Looks like an excellent resource and one that is not too far out of reach for most of us.

Re: C Compiler from Scratch

#63

Earlier quoted context omitted.

> 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. So? Run your recursive descent parser, if it works, it works. There might be edge cases: when you come across them fix them.…

> Have you ever actually learned the syntax of a language by looking at a BNF? Actually, yes.

Well, you got me one line of a five paragraph post! Congrats.

How did that work out for you? Were you able to write meaningful programs just by seeing what text was matched by the parser, without knowing what that text did?

Re: C Compiler from Scratch

#64

Earlier quoted context omitted.

> Have you ever actually learned the syntax of a language by looking at a BNF? Actually, yes.

Well, you got me one line of a five paragraph post! Congrats. How did that work out for you? Were you able to write meaningful programs just by seeing what text was matched by the parser, without knowing what that text did?

You asked if I learned the syntax from the BNF, not if I learned the semantics from it. Semantic information comes from the prose description of how each production is to be semantically interpreted, although many specifications are very lacking in thoroughness here.

On any project with more than one person (and arguably even many projects with a single person, for the you of today is not the same you of yesteryear), communication is absolutely essential. And if what you're describing is a language, than the BNF for the syntax and corresponding prose for semantics is the most effective way we know of to document and communicate that language. If instead you try to wing it and rely on examples to communicate the specification, then the resulting mess will take you several times as long to clean up as actually properly designing out the documentation would have taken in the first place--and this I speak from bitter experience.

P.S. I didn't engage with the rest of your post because I wasn't interested in writing an essay to rebut your points.

Re: C Compiler from Scratch

#65
post #55

Earlier quoted context omitted.

Check out "Modern Compiler Implementation" by Appel and also the Red (Purple?) Dragon book.

sigh Have you actually done this? Do you really think we haven't? The Appel book in particular is very good, but it only covers assembly generation at a high level. None of the examples target a real-world architecture.

I don't know what you have done. The red dragon book goes over targeting an intermediate form that's basically assembly language, it also covers register allocation in depth. As far as I can tell, most of the texts after that is in research papers and real world examples (https://c9x.me/compile/)

Re: C Compiler from Scratch

#66
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 st…

Yes, I agree with you. For production compilers, with hand-coded parsers, it is a waste of space to store all files in memory. Please note that I was talking about introductions to scanning and parsing. I just feel there is no need to make things more complicated than they need to be, when you are introducing somebody to parsing and scanning. Most people who study computer science, will likely, when they need to do some scanning and parsing, not having to deal with files, but have strings at hand. For an introduction to parsing and scanning, I even would suggest to begin with a back-tracking recursive decent parser, to talk about the essence of parsing. Please note that if you add a little caching, such a parser can have descent performance for many applications that an average software engineer will encounter. For all other applications, standard libraries and/or compilers exist. See https://github.com/FransFaase/IParse for an example of this approach.

Anyway, please do not compare disk space to build with source code size. (I understand that the debug version of uses a lot of static linking with debug information.) I understand that the Linux kernel is 28 million lines of code. Even with 80 characters per line, when I think an average of 40, is far more realistic, that will be under 2 GB. So, yes, you can store all source file in RAM on any descent computer. (I did not find any recent number of lines of code for LLVM/Clang, but extrapolating it, I guess it is in the same order as the Linux Kernel.)

Re: C Compiler from Scratch

#67

Earlier quoted context omitted.

Well, you got me one line of a five paragraph post! Congrats. How did that work out for you? Were you able to write meaningful programs just by seeing what text was matched by the parser, without knowing what that text did?

You asked if I learned the syntax from the BNF, not if I learned the semantics from it. Semantic information comes from the prose description of how each production is to be semantically interpreted, although many specifications are very lacking in thoroughness here. On any project with more than one person (and arguably even many projects with a single person, for the you of today is not the same you of yesteryear),…

> You asked if I learned the syntax from the BNF, not if I learned the semantics from it.

Actually, I didn't ask you anything--it was a rhetorical question, within the context of a post you ignored.

> On any project with more than one person (and arguably even many projects with a single person, for the you of today is not the same you of yesteryear), communication is absolutely essential. And if what you're describing is a language, than the BNF for the syntax and corresponding prose for semantics is the most effective way we know of to document and communicate that language. If instead you try to wing it and rely on examples to communicate the specification, then the resulting mess will take you several times as long to clean up as actually properly designing out the documentation would have taken in the first place--and this I speak from bitter experience.

BNFs might the best way to communicate the syntax of a language to another person who needs to know the syntax to that level of specificity, but the fact that mainstream compilers often don't have widely available BNFs shows that a BNF simply isn't a vital part of compilation. Generating into a real target assembly is a vital part of compilation: if it doesn't generate to a useful target, it literally isn't a compiler.

I'm not against learning BNFs. They're useful. My point, from the beginning, has been that while assembly generation is vastly more complicated and important than parsing, the vast majority of language materials focus on parsing, giving only cursory coverage to generation.

There's literally detailed tutorials on how to use specific tools to do specific steps of parsing. Meanwhile, generation is covered, if at all, by generating partial pseudo-assembly for fictional architectures. Even if you manage to translate the pseudo-assembly into x86, good luck finding any guidance on how to link in a garbage collector, or properly tag the generated code with metadata for debugging or exception reporting, or how C calling conventions work so you can even implement exceptions on the stack... I don't want to hear about your experience with communicating about easy stuff like parsers until you've worked on a difficult problem.

> P.S. I didn't engage with the rest of your post because I wasn't interested in writing an essay to rebut your points.

If you don't feel like participating in the conversation, fine, just go away. Don't take cheap shots at out-of-context sentences where it's convenient, and pretend that you're not responding to the rest because it's beneath you.

Re: C Compiler from Scratch

#68
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

Thanks for the resources !!
Post reply on HN