9 ms·

C Compiler from Scratch

484 points by harel 7y ago

Koshkin 7y ago
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.
- 0xffff2 7y ago
  Granted is was for a toy language, not Pascal, but I had to write a complete compiler for my CS undergrad ~3 years ago.
saagarjha 7y ago
Any ideas what subset of C this supports? Or is it fully C89/C99/C11 compliant?
- jcranmer 7y ago
  The introduction states: > Instead, I've fallen back on the old standby and I'm going to write a compiler for a subset of C, enough to allow the compiler to compile itself. Just from cruising the lesson titles and poking around a few of them, substantially less than full C89. I don't see floating point, bitfields, or function pointers anywhere. Apparently, variadic functions and short (!) aren't supported either. Most of the new things in C99 (save perhaps //-style comments, mixed declaration and code, and long long) are unlikely to be supported, let alone C11. Judging from its reference to C-, it might also well not support the full C declarator madness.
z3phyr 7y ago
Writeups like this are helpful for people who find compiler theory books a bit dry. This is great!
aloknnikhil 7y ago
This is fantastic work. I believe learning to write a compiler is similar to learning a functional programming language. It completely changes the way you approach problems. I'm curious why BNF was chosen vs EBNF. I'm new to parsers and grammar. Isn't EBNF easier/simpler to write complex rules?
- shakna 7y ago
  > I'm curious why BNF was chosen vs EBNF. I'm new to parsers and grammar. Isn't EBNF easier/simpler to write complex rules? I can't speak to the specific reasons the OP chose, but I can speak to generalities. Generally speaking, every parser engine out there that supports EBNF supports different extensions of EBNF [+]. They aren't portable from one to another, and that can lock you in. So if you get frustrated with the engine at some point and want to ditch it, it becomes harder to. BNF does make it harder to write complex rules, but if your goal is a self-hosted compiler, like this one appears to be, you might use BNF for the host compiler, and then choose something more expressive now you can use the language you've built. There are tradeoffs in everything. BNF tends to be faster, and more portable with more documentation. EBNF handles more complex cases, but you might have to learn one specific tool rather than a standard you can use everywhere. [+] There is an EBNF standard. However, parser/lexer engines still extend it in their own incompatible ways. ISO tried to standardise it, and just ended up adding to the chaos, and now even they don't recommend their own.
  - chenhan 7y ago
    For the curious, the ISO standard is ISO/IEC 14977. It is available here: https://standards.iso.org/ittf/PubliclyAvailableStandards/ https://standards.iso.org/ittf/PubliclyAvailableStandards/ Direct link to the standard: https://standards.iso.org/ittf/PubliclyAvailableStandards/s026153_ISO_IEC_14977_1996(E).zip https://standards.iso.org/ittf/PubliclyAvailableStandards/s0... But of course, as shanka commented, it isn't a standard that is followed practically. This is just a demonstration of https://xkcd.com/927/ https://xkcd.com/927/ in real life.
- cwzwarich 7y ago
  > I'm curious why BNF was chosen vs EBNF. He wrote a BNF grammar, but his parser is closer to a handwritten parser for an EBNF grammar. Generally speaking, when people write recursive descent parsers by hand in a procedural style, they parse sequences directly rather than using a recursive descent following the grammar.
stevefan1999 7y ago
I'm learning from the Compiler course offered freely from Stanford [0] and the dragon book. I still feel great about it. And I think this GitHub project submitted will be an excellent practical source for analysis of how real world compiler might looks like from its beginning. [0]: https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about https://lagunita.stanford.edu/courses/Engineering/Compilers/...
- giancarlostoro 7y ago
  I want to dive into creating a language / compiler finally but I might do it with the Writing an Interpreter / Compiler series in Golang. Just so I can dive in and try to digest it all. Course I always heard of the dragon book and have wanted it since.
  - chrisseaton 7y ago
    > 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.
    - giancarlostoro 7y ago
      Is there something close to it in the modern sense then?
      - chrisseaton 7y ago
        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.
        7y ago
spicymaki 7y ago
I've been itching to write one of these myself. The looks like a good guide to get started.
jadia 7y ago
This post is going to teach me a million things! Thanks!
plinkplonk 7y ago
This might be relevant A Retargetable C Compiler: Design and Implementation by David Hanson and Chritopher Fraser https://www.amazon.com/Retargetable-Compiler-Design-Implementation/dp/0805316701 https://www.amazon.com/Retargetable-Compiler-Design-Implemen... Written in a literate programming style.
- jacquesm 7y ago
  Happy new year to you Ravi!
  - plinkplonk 7y ago
    Thanks Jacques. Same to you, (and everyone on HN!)
fjfaase 7y ago
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 string.
- zmodem 7y ago
  > Tell me about a project that has a gigabyte of source files, please. Here's one, apparently: http://lists.llvm.org/pipermail/cfe-dev/2019-October/063459.html http://lists.llvm.org/pipermail/cfe-dev/2019-October/063459....
  - fjfaase 7y ago
    This is actually not about a source repository being larger than a gigabyte, but a problem that arises with the C-preprocessor, where for a certain use, a certain header file is included many, many times, and where the position for all includes is kept. Typically a case of severe C-preprocessor abuse, I would say, which probably could be solved in a much better way. This shows how the C-preprocessor is both a blessing and a curse: it fixes many problems, but often causes compilation to be slow, because huge intermediate representations are produced which have to be parsed by the compiler.
- modo_mario 7y ago
  At my first job they used a programming language that worked on top of c somehow developed by their sister company(used to be the same but split) all that to make a shitty ERP and eh...it was many, many gigabytes partially written by people now retired. I don't think the few images and other such stuff used were part of that (it also had a few random cobol files i encountered) and it had everything from the UI rendering and handling to a webserver i had to communicate with but about which nobody knew how it worked because the guy who made it was enjoying his olden days. To be totally fair it was the biggest inefficient coding mess I've seen. I still regret not scanning and keeping the customerlist because if I did i'd be deep in that business right now making bank.
zabana 7y ago
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
- GuB-42 7y ago
  Just take any tutorial about writing a compiler and stop at the Abstract Syntax Tree generation. There is not that much difference between parsing a programming language like C and something like JSON. JSON grammar is smaller but the ideas are the same. In fact, JSON is essentially a subset of JS, and JS has a C-like syntax. What makes a compiler a compiler is what comes after the parser, i.e. code generation.
- abecedarius 7y ago
  Try the first few chapters of https://inf.ethz.ch/personal/wirth/CompilerConstruction/CompilerConstruction1.pdf https://inf.ethz.ch/personal/wirth/CompilerConstruction/Comp... and apply it to the grammar at https://www.json.org/json-en.html https://www.json.org/json-en.html
  - zabana 7y ago
    Thanks for the resources !!
BossingAround 7y ago
I misread and thought someone created a C-compiler in Scratch. That'd have been extremely impressive... :))
- userbinator 7y ago
  That sounds like a challenge someone might actually try... Along the same lines, you may find this amusing: https://news.ycombinator.com/item?id=7882066 https://news.ycombinator.com/item?id=7882066
einpoklum 7y ago
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.
kerkeslager 7y ago
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.
- jcranmer 7y ago
  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.
  - kerkeslager 7y ago
    > 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. Perl has demonstrated that a language doesn't even have to be decideable to be successful. This is a useful tool for getting advanced computer science degrees, not so much a useful tool for writing compilers. > 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. Moreover, this documentation isn't even necessary for a lot of compilers. If you don't have a working compiler, nobody cares if you have a BNF. If you don't plan to submit your language to a standardization body who isn't going to accept it for at least a decade anyway, you probably don't need a BNF. Have you ever actually learned the syntax of a language by looking at a BNF? Or have you learned from examples, like almost[1] every[2] tutorial[3] in[4] existence[5]? And what's more, I learned BNF well enough to describe a grammar to anyone who needs to know it in about 30 minutes of class time in college. So even if you somehow get to the point where you're submitting your language to ANSI for standardization, you can go back and learn BNF then. > 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. I took those classes. At my college it was two semesters. We learned a very small subset of MIPS that would be insufficient even to write a compiler targeting MIPS, let alone a compiler targeting x86. Books like The Art Of Assembly Language give you enough x86 assembler, but there's still a gap between understanding x86 and generating x86. And you'll have to understand C semantics to talk to the rest of the world in code, which means you get to dig into the C standard and also into some implementations of that standard. [1] https://doc.rust-lang.org/book/index.html https://doc.rust-lang.org/book/index.html [2] https://docs.python.org/3/tutorial/index.html https://docs.python.org/3/tutorial/index.html [3] https://mitpress.mit.edu/sites/default/files/sicp/index.html https://mitpress.mit.edu/sites/default/files/sicp/index.html [4] https://docs.oracle.com/javase/tutorial/ https://docs.oracle.com/javase/tutorial/ [5] https://gobyexample.com/ https://gobyexample.com/
tzs 7y ago
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 Design in a way that's understandable to a programmer, rather than a mathematician. My basic premise is that the best way to learn how to write a compiler is to look at one in depth; the best way to understand the theory is to build tools that use that theory for practical ends. So, this book is built around working code that provides immediate practical examples of how given theories are applied. I have deliberately avoided mathematical notation, foreign to many programmers, in favor of English descriptions of the theory and using the code itself to explain a process. If a theoretical discussion isn't clear, you can look at the code that implements the theory. I make no claims that the code presented here is the only (or the best) implementation of the concepts presented. I've found, however, that looking at an implementation-at any implementation--can be a very useful adjunct to understanding the theory, and the reader is well able to adapt the concepts presented here to alternate implementations. > The disadvantage of my approach is that there is, by necessity, a tremendous amount of low-level detail in this book. It is my belief, however, that this detail is both critically important to understanding how to actually build a real compiler, and is missing from virtually every other book on the subject. Similarly, a lot of the low-level details are more related to program implementation in general than to compilers in particular. One of the secondary reasons for learning how to build a compiler, however, is to learn how to put together a large and complex program, and presenting complete programs, rather than just the directly compiler-related portions of those programs, furthers this end. I've resolved the too-many-details problem, to some extent, by isolating the theoretical materials into their own sections, all marked with asterisks in the table of contents and in the header on the top of the page. If you aren't interested in the nuts and bolts, you can just skip over the sections that discuss code. ... > In a sense, this book is really an in-depth presentation of several, very well documented programs: the complete sources for three compiler-generation tools are presented, as is a complete C compiler. (A lexical-analyzer generator modeled after the UNIX lex utility is presented along with two yacc-like compiler compilers.) As such, it is more of a compiler-engineering book than are most texts-a strong emphasis is placed on teaching you how to write a real compiler. On the other hand, a lot of theory is covered on the way to understanding the practice, and this theory is central to the discussion. Though I've presented complete implementations of the programs as an aid to understanding, the implementation details aren't nearly as important as the processes that are used by those programs to do what they do. It's important that you be able to apply these processes to your own programs. [1] https://holub.com/compiler/ https://holub.com/compiler/

484 points by harel 7y ago

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.

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

saagarjha 7y ago

Any ideas what subset of C this supports? Or is it fully C89/C99/C11 compliant?

jcranmer 7y ago
The introduction states: > Instead, I've fallen back on the old standby and I'm going to write a compiler for a subset of C, enough to allow the compiler to compile itself. Just from cruising the lesson titles and poking around a few of them, substantially less than full C89. I don't see floating point, bitfields, or function pointers anywhere. Apparently, variadic functions and short (!) aren't supported either. Most of the new things in C99 (save perhaps //-style comments, mixed declaration and code, and long long) are unlikely to be supported, let alone C11. Judging from its reference to C-, it might also well not support the full C declarator madness.

z3phyr 7y ago

Writeups like this are helpful for people who find compiler theory books a bit dry. This is great!

aloknnikhil 7y ago

This is fantastic work. I believe learning to write a compiler is similar to learning a functional programming language. It completely changes the way you approach problems. I'm curious why BNF was chosen vs EBNF. I'm new to parsers and grammar. Isn't EBNF easier/simpler to write complex rules?

shakna 7y ago
> I'm curious why BNF was chosen vs EBNF. I'm new to parsers and grammar. Isn't EBNF easier/simpler to write complex rules? I can't speak to the specific reasons the OP chose, but I can speak to generalities. Generally speaking, every parser engine out there that supports EBNF supports different extensions of EBNF [+]. They aren't portable from one to another, and that can lock you in. So if you get frustrated with the engine at some point and want to ditch it, it becomes harder to. BNF does make it harder to write complex rules, but if your goal is a self-hosted compiler, like this one appears to be, you might use BNF for the host compiler, and then choose something more expressive now you can use the language you've built. There are tradeoffs in everything. BNF tends to be faster, and more portable with more documentation. EBNF handles more complex cases, but you might have to learn one specific tool rather than a standard you can use everywhere. [+] There is an EBNF standard. However, parser/lexer engines still extend it in their own incompatible ways. ISO tried to standardise it, and just ended up adding to the chaos, and now even they don't recommend their own.
- chenhan 7y ago
  For the curious, the ISO standard is ISO/IEC 14977. It is available here: https://standards.iso.org/ittf/PubliclyAvailableStandards/ https://standards.iso.org/ittf/PubliclyAvailableStandards/ Direct link to the standard: https://standards.iso.org/ittf/PubliclyAvailableStandards/s026153_ISO_IEC_14977_1996(E).zip https://standards.iso.org/ittf/PubliclyAvailableStandards/s0... But of course, as shanka commented, it isn't a standard that is followed practically. This is just a demonstration of https://xkcd.com/927/ https://xkcd.com/927/ in real life.
cwzwarich 7y ago
> I'm curious why BNF was chosen vs EBNF. He wrote a BNF grammar, but his parser is closer to a handwritten parser for an EBNF grammar. Generally speaking, when people write recursive descent parsers by hand in a procedural style, they parse sequences directly rather than using a recursive descent following the grammar.

stevefan1999 7y ago

I'm learning from the Compiler course offered freely from Stanford [0] and the dragon book. I still feel great about it. And I think this GitHub project submitted will be an excellent practical source for analysis of how real world compiler might looks like from its beginning. [0]: https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about https://lagunita.stanford.edu/courses/Engineering/Compilers/...

giancarlostoro 7y ago
I want to dive into creating a language / compiler finally but I might do it with the Writing an Interpreter / Compiler series in Golang. Just so I can dive in and try to digest it all. Course I always heard of the dragon book and have wanted it since.
- chrisseaton 7y ago
  > 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.
  - giancarlostoro 7y ago
    Is there something close to it in the modern sense then?
    - chrisseaton 7y ago
      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.
      - 7y ago

spicymaki 7y ago

I've been itching to write one of these myself. The looks like a good guide to get started.

jadia 7y ago

This post is going to teach me a million things! Thanks!

plinkplonk 7y ago

This might be relevant A Retargetable C Compiler: Design and Implementation by David Hanson and Chritopher Fraser https://www.amazon.com/Retargetable-Compiler-Design-Implementation/dp/0805316701 https://www.amazon.com/Retargetable-Compiler-Design-Implemen... Written in a literate programming style.

jacquesm 7y ago
Happy new year to you Ravi!
- plinkplonk 7y ago
  Thanks Jacques. Same to you, (and everyone on HN!)

fjfaase 7y ago

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 string.

zmodem 7y ago
> Tell me about a project that has a gigabyte of source files, please. Here's one, apparently: http://lists.llvm.org/pipermail/cfe-dev/2019-October/063459.html http://lists.llvm.org/pipermail/cfe-dev/2019-October/063459....
- fjfaase 7y ago
  This is actually not about a source repository being larger than a gigabyte, but a problem that arises with the C-preprocessor, where for a certain use, a certain header file is included many, many times, and where the position for all includes is kept. Typically a case of severe C-preprocessor abuse, I would say, which probably could be solved in a much better way. This shows how the C-preprocessor is both a blessing and a curse: it fixes many problems, but often causes compilation to be slow, because huge intermediate representations are produced which have to be parsed by the compiler.
modo_mario 7y ago
At my first job they used a programming language that worked on top of c somehow developed by their sister company(used to be the same but split) all that to make a shitty ERP and eh...it was many, many gigabytes partially written by people now retired. I don't think the few images and other such stuff used were part of that (it also had a few random cobol files i encountered) and it had everything from the UI rendering and handling to a webserver i had to communicate with but about which nobody knew how it worked because the guy who made it was enjoying his olden days. To be totally fair it was the biggest inefficient coding mess I've seen. I still regret not scanning and keeping the customerlist because if I did i'd be deep in that business right now making bank.

zabana 7y ago

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

GuB-42 7y ago
Just take any tutorial about writing a compiler and stop at the Abstract Syntax Tree generation. There is not that much difference between parsing a programming language like C and something like JSON. JSON grammar is smaller but the ideas are the same. In fact, JSON is essentially a subset of JS, and JS has a C-like syntax. What makes a compiler a compiler is what comes after the parser, i.e. code generation.
abecedarius 7y ago
Try the first few chapters of https://inf.ethz.ch/personal/wirth/CompilerConstruction/CompilerConstruction1.pdf https://inf.ethz.ch/personal/wirth/CompilerConstruction/Comp... and apply it to the grammar at https://www.json.org/json-en.html https://www.json.org/json-en.html
- zabana 7y ago
  Thanks for the resources !!

BossingAround 7y ago

I misread and thought someone created a C-compiler in Scratch. That'd have been extremely impressive... :))

userbinator 7y ago
That sounds like a challenge someone might actually try... Along the same lines, you may find this amusing: https://news.ycombinator.com/item?id=7882066 https://news.ycombinator.com/item?id=7882066

einpoklum 7y ago

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.

kerkeslager 7y ago

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.

jcranmer 7y ago
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.
- kerkeslager 7y ago
  > 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. Perl has demonstrated that a language doesn't even have to be decideable to be successful. This is a useful tool for getting advanced computer science degrees, not so much a useful tool for writing compilers. > 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. Moreover, this documentation isn't even necessary for a lot of compilers. If you don't have a working compiler, nobody cares if you have a BNF. If you don't plan to submit your language to a standardization body who isn't going to accept it for at least a decade anyway, you probably don't need a BNF. Have you ever actually learned the syntax of a language by looking at a BNF? Or have you learned from examples, like almost[1] every[2] tutorial[3] in[4] existence[5]? And what's more, I learned BNF well enough to describe a grammar to anyone who needs to know it in about 30 minutes of class time in college. So even if you somehow get to the point where you're submitting your language to ANSI for standardization, you can go back and learn BNF then. > 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. I took those classes. At my college it was two semesters. We learned a very small subset of MIPS that would be insufficient even to write a compiler targeting MIPS, let alone a compiler targeting x86. Books like The Art Of Assembly Language give you enough x86 assembler, but there's still a gap between understanding x86 and generating x86. And you'll have to understand C semantics to talk to the rest of the world in code, which means you get to dig into the C standard and also into some implementations of that standard. [1] https://doc.rust-lang.org/book/index.html https://doc.rust-lang.org/book/index.html [2] https://docs.python.org/3/tutorial/index.html https://docs.python.org/3/tutorial/index.html [3] https://mitpress.mit.edu/sites/default/files/sicp/index.html https://mitpress.mit.edu/sites/default/files/sicp/index.html [4] https://docs.oracle.com/javase/tutorial/ https://docs.oracle.com/javase/tutorial/ [5] https://gobyexample.com/ https://gobyexample.com/

tzs 7y ago

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 Design in a way that's understandable to a programmer, rather than a mathematician. My basic premise is that the best way to learn how to write a compiler is to look at one in depth; the best way to understand the theory is to build tools that use that theory for practical ends. So, this book is built around working code that provides immediate practical examples of how given theories are applied. I have deliberately avoided mathematical notation, foreign to many programmers, in favor of English descriptions of the theory and using the code itself to explain a process. If a theoretical discussion isn't clear, you can look at the code that implements the theory. I make no claims that the code presented here is the only (or the best) implementation of the concepts presented. I've found, however, that looking at an implementation-at any implementation--can be a very useful adjunct to understanding the theory, and the reader is well able to adapt the concepts presented here to alternate implementations. > The disadvantage of my approach is that there is, by necessity, a tremendous amount of low-level detail in this book. It is my belief, however, that this detail is both critically important to understanding how to actually build a real compiler, and is missing from virtually every other book on the subject. Similarly, a lot of the low-level details are more related to program implementation in general than to compilers in particular. One of the secondary reasons for learning how to build a compiler, however, is to learn how to put together a large and complex program, and presenting complete programs, rather than just the directly compiler-related portions of those programs, furthers this end. I've resolved the too-many-details problem, to some extent, by isolating the theoretical materials into their own sections, all marked with asterisks in the table of contents and in the header on the top of the page. If you aren't interested in the nuts and bolts, you can just skip over the sections that discuss code. ... > In a sense, this book is really an in-depth presentation of several, very well documented programs: the complete sources for three compiler-generation tools are presented, as is a complete C compiler. (A lexical-analyzer generator modeled after the UNIX lex utility is presented along with two yacc-like compiler compilers.) As such, it is more of a compiler-engineering book than are most texts-a strong emphasis is placed on teaching you how to write a real compiler. On the other hand, a lot of theory is covered on the way to understanding the practice, and this theory is central to the discussion. Though I've presented complete implementations of the programs as an aid to understanding, the implementation details aren't nearly as important as the processes that are used by those programs to do what they do. It's important that you be able to apply these processes to your own programs. [1] https://holub.com/compiler/ https://holub.com/compiler/