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…
C Compiler from Scratch
61–68 of 68 posts
Re: C Compiler from Scratch
#62A 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…
Re: C Compiler from Scratch
#63Earlier 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.
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
#64Earlier 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?
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
#65Earlier 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.
Re: C Compiler from Scratch
#66I 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…
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
#67Earlier 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),…
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
#68Do 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