5 ms·

Writing a C Compiler (2017)

107 points by lrsjng 3y ago

dananjaya86 3y ago
Book version to be released in October '23 : https://nostarch.com/writing-c-compiler https://nostarch.com/writing-c-compiler
- deleted 3y ago
  [deleted]
RcouF1uZ4gsC 3y ago
Here is how to write a C compiler in Python that correctly compile the vast majority of C programs per the ISO C standard: print(“You have some form of undefined behavior, which means printing this is a valid response per the C standard”)
- tialaramex 3y ago
  Undefined Behaviour has to actually happen, and so that means at runtime†, and thus what you wrote is not a valid C compiler. For C++ IFNDR ("Ill-formed, No diagnostic required") the situation is trickier because the affected programs (some unknowable but likely large proportion of all purported C++ code) are not well formed C++, the standard offers no hint as to what happens or why, since it constrains only the behaviour of a C++ compiler for well formed C++ programs. † It's possible the C lexer claims to have some "Undefined Behaviour" cases like the C++ lexer, hence P2621 "UB? In my lexer?" which is a reference to a 2005 meme because C++ standards committee members are down with the kids, but that's clearly a standards text bug if so because it makes no sense to have UB in the lexer, these should just be ill-formed programs, you get a compiler error.
e19293001 3y ago
[flagged]
- bigdict 3y ago
  getting college essay vibes from this comment
  - belter 3y ago
    And ChatGPT vibes...
    - deleted 3y ago
      [deleted]
- fuzztester 3y ago
  Nice comment, GPT user. Now, GPT: Replace all occurrences of the substring "me" with "you" in the above comment text.
  - eesmith 3y ago
    Huh. I don't get those vibes. Further investigation doesn't support your claim. The citations check out, including publication year and publishers. And the author has indeed praised the book many times before (https://news.ycombinator.com/item?id=31843833 https://news.ycombinator.com/item?id=31843833, https://news.ycombinator.com/item?id=31843833 https://news.ycombinator.com/item?id=31843833, https://news.ycombinator.com/item?id=31311613 https://news.ycombinator.com/item?id=31311613, https://news.ycombinator.com/item?id=28481028 https://news.ycombinator.com/item?id=28481028, https://news.ycombinator.com/item?id=23386732 https://news.ycombinator.com/item?id=23386732, https://news.ycombinator.com/item?id=22305353 https://news.ycombinator.com/item?id=22305353, and https://news.ycombinator.com/item?id=23386732 https://news.ycombinator.com/item?id=23386732, https://news.ycombinator.com/item?id=21988211 https://news.ycombinator.com/item?id=21988211, https://news.ycombinator.com/item?id=21513056 https://news.ycombinator.com/item?id=21513056, https://news.ycombinator.com/item?id=18996703 https://news.ycombinator.com/item?id=18996703, and https://news.ycombinator.com/item?id=10184364 https://news.ycombinator.com/item?id=10184364 ) with the last comment from 2015. Eg, compare "I am deeply indebted to this book" with "I'm very debted to this man. I enjoyed a lot reading his books and made me who I am today." at https://news.ycombinator.com/item?id=28481028 https://news.ycombinator.com/item?id=28481028 from Sept 10, 2021. Or compare "I owe my entire career to this remarkable individual who, despite never having met or being affiliated with," with "I'm not affiliated with the author though. This book helped a lot in my career as a hardware and firmware engineer." at https://news.ycombinator.com/item?id=23386732 https://news.ycombinator.com/item?id=23386732 from June 2, 2020. Or compare "enabling me to implement powerful features akin to those found in the widely used tool, grep." with similar comments over the last 8+ years, at https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=e19293001%20grep&sort=byPopularity&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... , like "and eventually write your own 'grep' which was for me is a mind-blowing experience" at https://news.ycombinator.com/item?id=13664714 https://news.ycombinator.com/item?id=13664714 from Feb 16, 2017. And https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=e19293001%20dosreist&sort=byPopularity&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... shows the OP citing http://cs.newpaltz.edu/~dosreist/ http://cs.newpaltz.edu/~dosreist/ while this comment uses the archive.org version because the old URL doesn't work.
bigdict 3y ago
Has anyone worked through this? Is it a good (soon to be) book?
userbinator 3y ago
IMHO writing a compiler for a high-level language, in an even higher level language, somehow feels a bit "anachronistic" (for lack of better word).
- retrac 3y ago
  Most of the current major C implementations are written in C++.
  - userbinator 3y ago
    That's unfortunate.
  - WalterBright 3y ago
    ImportC is written in D.
- avgcorrection 3y ago
  For what reason?
  - userbinator 3y ago
    It's backwards. Writing a C compiler in C or Asm makes sense, a Python compiler in C also does, but a C compiler in Python is an odd inversion of abstraction.
    - Jtsummers 3y ago
      Why? The objective is to translate code in one language (C) to another (machine code or assembly or perhaps an intermediate representation). Why does it make sense to use C for that task and not Python or some other language? It's not like C provides facilities that specifically enable compiler writing or text parsing for itself that other languages are lacking.
    - avgcorrection 3y ago
      I guess this harkens back to the days when you had to write a compiler in a low-level language because that’s all that the platform that you are targeting supports. Then it sounds weird to talk about writing a compiler in a high-level language in order to target a low-level one, because surely these high-level languages are more platform-dependent than the blessed (guaranteed on the platform) low-level one. But these days we can access dozens of languages on many platforms. And we can use high-level languages that are good for writing compilers—languages with good string types and algebraic data types—instead of being limited to awfully imperative/procedural ones. In other words: your perspective sounds way more anachronistic.
hcks 3y ago
Yet another “compiling” course that puts all the emphasis on parsing. Rule of thumb: parsing/lexing shouldn’t takes more than 10% of your compiler course.
- WalterBright 3y ago
  Parsing takes a weekend. The rest takes a year to get a rudimentary compiler working.
- tester756 3y ago
  parsing is cool
- deleted 3y ago
  [deleted]
- hota_mazi 3y ago
  I disagree. As opposed to most compiler articles, this one actually covers code generation for every section of its chapters, which is really great. I also like that every chapter focuses on a specific feature and describes how to implement it end to end: lexical/syntactic parsing, AST, and x86_64 generation. Great series!
- marcosdumay 3y ago
  On the other hand, parsing text could easily be a very valuable course on its own. You just have to not keep it restricted to programing languages, and include the knowledge created on this century.
- vector_spaces 3y ago
  This attitude bugs me a lot. It seems really common, especially in more recent texts about language design and implementation, that parsing is heavily de-emphasized to the point where practically nobody talks about it. See Essentials of Programming Languages by Friedman & Wand, the relevant sections in SICP, Programming Languages: Application & Interpretation (which goes so far as to call it a distraction). I get that parsing is more of an implementation detail and doesn't really belong to the space-brained realm of language design per se, but it's a bit annoying that most texts refuse to give any space to the topic, and rely on your language being S-expression based or assume you're going to use a parser generator. Like, in the real world, even if one will never actually implement a fully-fledged programming language, you're still probably going to have to parse things sometimes. I would love a book that goes into detail about different parsing techniques and considers best practices and patterns and tradeoffs/design considerations -- would pay good money for that It reminds me somewhat of the situation in analysis, where there are lots of theorems that aren't written down anywhere because literally every book states them as "easy" exercises. Maybe I'm looking in the wrong places, but I can't find much in the way of concrete guidance on implementing parsers. I'm aware of the beautiful series on parsing theory by Aho & Ullman ("The Theory of Parsing, Translation, and Compiling"), but those are more focused on theory rather than implementation

107 points by lrsjng 3y ago

Book version to be released in October '23 : https://nostarch.com/writing-c-compiler https://nostarch.com/writing-c-compiler

deleted 3y ago
[deleted]

RcouF1uZ4gsC 3y ago

Here is how to write a C compiler in Python that correctly compile the vast majority of C programs per the ISO C standard: print(“You have some form of undefined behavior, which means printing this is a valid response per the C standard”)

tialaramex 3y ago
Undefined Behaviour has to actually happen, and so that means at runtime†, and thus what you wrote is not a valid C compiler. For C++ IFNDR ("Ill-formed, No diagnostic required") the situation is trickier because the affected programs (some unknowable but likely large proportion of all purported C++ code) are not well formed C++, the standard offers no hint as to what happens or why, since it constrains only the behaviour of a C++ compiler for well formed C++ programs. † It's possible the C lexer claims to have some "Undefined Behaviour" cases like the C++ lexer, hence P2621 "UB? In my lexer?" which is a reference to a 2005 meme because C++ standards committee members are down with the kids, but that's clearly a standards text bug if so because it makes no sense to have UB in the lexer, these should just be ill-formed programs, you get a compiler error.

e19293001 3y ago

[flagged]

bigdict 3y ago
getting college essay vibes from this comment
- belter 3y ago
  And ChatGPT vibes...
  - deleted 3y ago
    [deleted]
fuzztester 3y ago
Nice comment, GPT user. Now, GPT: Replace all occurrences of the substring "me" with "you" in the above comment text.
- eesmith 3y ago
  Huh. I don't get those vibes. Further investigation doesn't support your claim. The citations check out, including publication year and publishers. And the author has indeed praised the book many times before (https://news.ycombinator.com/item?id=31843833 https://news.ycombinator.com/item?id=31843833, https://news.ycombinator.com/item?id=31843833 https://news.ycombinator.com/item?id=31843833, https://news.ycombinator.com/item?id=31311613 https://news.ycombinator.com/item?id=31311613, https://news.ycombinator.com/item?id=28481028 https://news.ycombinator.com/item?id=28481028, https://news.ycombinator.com/item?id=23386732 https://news.ycombinator.com/item?id=23386732, https://news.ycombinator.com/item?id=22305353 https://news.ycombinator.com/item?id=22305353, and https://news.ycombinator.com/item?id=23386732 https://news.ycombinator.com/item?id=23386732, https://news.ycombinator.com/item?id=21988211 https://news.ycombinator.com/item?id=21988211, https://news.ycombinator.com/item?id=21513056 https://news.ycombinator.com/item?id=21513056, https://news.ycombinator.com/item?id=18996703 https://news.ycombinator.com/item?id=18996703, and https://news.ycombinator.com/item?id=10184364 https://news.ycombinator.com/item?id=10184364 ) with the last comment from 2015. Eg, compare "I am deeply indebted to this book" with "I'm very debted to this man. I enjoyed a lot reading his books and made me who I am today." at https://news.ycombinator.com/item?id=28481028 https://news.ycombinator.com/item?id=28481028 from Sept 10, 2021. Or compare "I owe my entire career to this remarkable individual who, despite never having met or being affiliated with," with "I'm not affiliated with the author though. This book helped a lot in my career as a hardware and firmware engineer." at https://news.ycombinator.com/item?id=23386732 https://news.ycombinator.com/item?id=23386732 from June 2, 2020. Or compare "enabling me to implement powerful features akin to those found in the widely used tool, grep." with similar comments over the last 8+ years, at https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=e19293001%20grep&sort=byPopularity&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... , like "and eventually write your own 'grep' which was for me is a mind-blowing experience" at https://news.ycombinator.com/item?id=13664714 https://news.ycombinator.com/item?id=13664714 from Feb 16, 2017. And https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=e19293001%20dosreist&sort=byPopularity&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... shows the OP citing http://cs.newpaltz.edu/~dosreist/ http://cs.newpaltz.edu/~dosreist/ while this comment uses the archive.org version because the old URL doesn't work.

bigdict 3y ago

Has anyone worked through this? Is it a good (soon to be) book?

userbinator 3y ago

IMHO writing a compiler for a high-level language, in an even higher level language, somehow feels a bit "anachronistic" (for lack of better word).

retrac 3y ago
Most of the current major C implementations are written in C++.
- userbinator 3y ago
  That's unfortunate.
- WalterBright 3y ago
  ImportC is written in D.
avgcorrection 3y ago
For what reason?
- userbinator 3y ago
  It's backwards. Writing a C compiler in C or Asm makes sense, a Python compiler in C also does, but a C compiler in Python is an odd inversion of abstraction.
  - Jtsummers 3y ago
    Why? The objective is to translate code in one language (C) to another (machine code or assembly or perhaps an intermediate representation). Why does it make sense to use C for that task and not Python or some other language? It's not like C provides facilities that specifically enable compiler writing or text parsing for itself that other languages are lacking.
  - avgcorrection 3y ago
    I guess this harkens back to the days when you had to write a compiler in a low-level language because that’s all that the platform that you are targeting supports. Then it sounds weird to talk about writing a compiler in a high-level language in order to target a low-level one, because surely these high-level languages are more platform-dependent than the blessed (guaranteed on the platform) low-level one. But these days we can access dozens of languages on many platforms. And we can use high-level languages that are good for writing compilers—languages with good string types and algebraic data types—instead of being limited to awfully imperative/procedural ones. In other words: your perspective sounds way more anachronistic.

hcks 3y ago

Yet another “compiling” course that puts all the emphasis on parsing. Rule of thumb: parsing/lexing shouldn’t takes more than 10% of your compiler course.

WalterBright 3y ago
Parsing takes a weekend. The rest takes a year to get a rudimentary compiler working.
tester756 3y ago
parsing is cool
deleted 3y ago
[deleted]
hota_mazi 3y ago
I disagree. As opposed to most compiler articles, this one actually covers code generation for every section of its chapters, which is really great. I also like that every chapter focuses on a specific feature and describes how to implement it end to end: lexical/syntactic parsing, AST, and x86_64 generation. Great series!
marcosdumay 3y ago
On the other hand, parsing text could easily be a very valuable course on its own. You just have to not keep it restricted to programing languages, and include the knowledge created on this century.
vector_spaces 3y ago
This attitude bugs me a lot. It seems really common, especially in more recent texts about language design and implementation, that parsing is heavily de-emphasized to the point where practically nobody talks about it. See Essentials of Programming Languages by Friedman & Wand, the relevant sections in SICP, Programming Languages: Application & Interpretation (which goes so far as to call it a distraction). I get that parsing is more of an implementation detail and doesn't really belong to the space-brained realm of language design per se, but it's a bit annoying that most texts refuse to give any space to the topic, and rely on your language being S-expression based or assume you're going to use a parser generator. Like, in the real world, even if one will never actually implement a fully-fledged programming language, you're still probably going to have to parse things sometimes. I would love a book that goes into detail about different parsing techniques and considers best practices and patterns and tradeoffs/design considerations -- would pay good money for that It reminds me somewhat of the situation in analysis, where there are lots of theorems that aren't written down anywhere because literally every book states them as "easy" exercises. Maybe I'm looking in the wrong places, but I can't find much in the way of concrete guidance on implementing parsers. I'm aware of the beautiful series on parsing theory by Aho & Ullman ("The Theory of Parsing, Translation, and Compiling"), but those are more focused on theory rather than implementation