7 ms·

Self hosted C – breakdown

105 points by andrewchambers 11y ago

userbinator 11y ago
It's always great to see more people writing their own compilers - a "proof by example" that compilers do not have to be magical and mysterious special software that only few experts can write. The theory may be deep, but in practice getting a basic working compiler doesn't require all that much. I notice you're using a recursive-descent parser, which I think is a good idea because it can actually reduce complexity over one made with parser-generators; in fact it's simple enough that even beginners who have just grasped recursion should be able to understand and write one. Once you have a basic parser that can evaluate arithmetic expressions, extending that to generating AST nodes and parse a (mostly) simple language like C is not so difficult. If I remember correctly, at least one college has an expression evaluator as a first-year CS assignment related to recursion. It's interesting that one of the sections of K&R, on reading and writing C declarations, even contains a simple parser for them --- I'm not aware of any introductory books for other languages which contain small pieces of their implementation. That said, you can use the "precedence climbing" technique[1] to collapse many of the recursive functions for most of the expression operators into one function with a succinct loop and a table, making your parser even simpler and faster. C4[2] is an example of this technique but with a series of if-else in the body of the function instead of a table, and I think is worth some careful study just for its mindblowingly awesome ridiculous simplicity. [1] https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing [2] https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822
- emptybits 11y ago
  introductory books for other languages which contain small pieces of their implementation I feel like two of the very few contenders for this might be books on Forth or Lisp, though still maybe not an "introductory" book.
  - junke 11y ago
    Such as Queinnec's Lisp in Small Pieces (https://en.wikipedia.org/wiki/Lisp_in_Small_Pieces https://en.wikipedia.org/wiki/Lisp_in_Small_Pieces)
- andrewchambers 11y ago
  I actually plan to do exactly that that for the preprocessor's expression parser. Thanks for the info!
  - w23j 11y ago
    You probably already know this stuff and don't need the info. But maybe somebody else reading this can find the link useful. This is a great tutorial on expression parsing using Pratt Parsers by Bob Nystrom: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...
- david-given 11y ago
  C is notoriously painful to parse with a parser generator because it's not context free --- consider this statement: foo * bar; It can't be parsed until you know whether foo is a type or a variable --- indeed, depending on the implementation, it can't even be tokenised correctly. So you need hooks from the symbol table back into the tokeniser/parser. I'm not at all surprised that the author's using a hand-written parser, as it reduces the problem space considerably. (There's a really good article which I've been trying to find which goes into details about all the weird parsing edge cases due to the rules about exactly when a word goes into the symbol table which I've been completely unable to find...)
  - andrewchambers 11y ago
    Here is a good one http://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc http://eli.thegreenplace.net/2012/07/05/how-clang-handles-th...
  - yepguy 11y ago
    As far as I know C is context-free. If C's grammar is ambiguous, that just makes it an ambiguous context-free grammar [1]. [1]: https://en.wikipedia.org/wiki/Ambiguous_grammar https://en.wikipedia.org/wiki/Ambiguous_grammar
    - kazinator 11y ago
      The context-free terminology doesn't apply to C because the ambiguity rests in not knowing what is the lexical category of foo in "foo * bar". That information comes from semantics. A language whose semantics you have to understand to understand its syntax is outside of the entire formal language realm inside which we formally recognize a "context-free" category. That formal language realm is purely syntactic: the terminal symbols are just "dumb" and stand for themselves. They are subject to rules which indicate how those symbols are combined. C is "quasi context free" in that if we resolve what the raw tokens mean (which one is a type and which one isn't), then the resulting language is context-free. In fact stronger than context free: amenable not only to LALR(1) parsing approaches but to recursive descent, with a suitable refactoring of the left-recursive rules given in the standard.
hbbio 11y ago
Thanks for providing the links that compare your for loop parser to existing implementations, it's interesting: - Gcc is unreadable; - Clang is "advanced", but not readable; - yours and tcc are clean... But you know it's always a risk to compare yourself to Fabrice Bellard :)
- andrewchambers 11y ago
  Tcc is far faster. I have done some benchmarks and tcc is really incredible. He was just optimising for a different goal I think. edit: Compiling my parse.c file, tcc is 34 times faster than gcc -O0 and my compiler is 3-4 times faster than gcc -O0. I should make a post with the actual stats.
  - david-given 11y ago
    It's worth mentioning that tcc started life as an entry in the Obfuscated C Contest: http://bellard.org/otcc/ http://bellard.org/otcc/ (It won.)
- david-given 11y ago
  Just to continue the catalogue: pcc is simple, but very old school and a bit contorted. libfirm is small and clean and generates excellent code. (Despite the name, it's a complete ANSI C compiler, as well as being a LLVM-light.) The ACK is easy to port and is a complete standalone toolchain including compilers, assemblers and linkers, but (at least on modern processors) produces code so bad that it will make you want to stab yourself in the eyes to make the pain go away. There's a look-but-don't-touch licensed compiler called vbcc which is by far the best C compiler I've ever seen; small, easy to understand, easy to port, and produces excellent code... but the author doesn't want to release it under an open source license. Any others?
  - andrewchambers 11y ago
    libfirm doesn't really classify as small to me, it is currently 132,638 lines of code. The cparser alone is 11k lines of code (5 times the size of my c parser).
w23j 11y ago
Can somebody point me at some introductionary material (or approachable code base) to writing an optimizing compiler? There seem to be a lot of very good tutorials on writing a simple compiler, like http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://compilers.iecc.com/crenshaw/ http://compilers.iecc.com/crenshaw/ There are also readable code bases like tinyc or this one. However these always use a simple template based approach to code generation and stop there. Of course there are real world compiler (lvm, gcc, ...). However because of their size and complexity it's hard to learn from them. What I am interested in would be going from: "I have an AST and for this node type I output this assembly." to "I translate the AST to an IR. Transform an the IR in multiple passes and finally output decent asm." That is, something that talks about CFG analysis, register scheduling or maybe SSA form? I have read papers on SSA and Sea-of-Nodes IRs, but these of course always assume that you know how and why to use them. A more approachable text/github-repo that shows how to take the step from template base code gen to more advanced techniques would be great. (I hope it is ok to ask this here. Did not want to hijack the thread.)
- quincunx 11y ago
  After grinding through a bunch of compiler books I have to mention "Modern Compiler Implementation in C - Andrew A. Appel": http://www.amazon.co.uk/dp/0521607655 http://www.amazon.co.uk/dp/0521607655 as one that stands out. For LALR Parsers and DFA scanners and the like, I found the original Dragon Book http://www.amazon.co.uk/dp/B00EKYURHS http://www.amazon.co.uk/dp/B00EKYURHS is still best. Both books are very accessible reading.
- andrewchambers 11y ago
  Someone I know is writing a tiny llvm clone in C. It already can do integer operations faster than gcc -O1. It is currently closed source but it shouldn't be hard for my compiler to target his IR in the future. His backend is currently around 6k lines of code so should be relatively easy to understand, though understanding some of the concepts is harder overall.
- rayiner 11y ago
  This one is very readable: http://www.amazon.com/Engineering-Compiler-Second-Edition-Cooper/dp/012088478X http://www.amazon.com/Engineering-Compiler-Second-Edition-Co.... Corresponding lecture notes: https://www.clear.rice.edu/comp412/Lectures https://www.clear.rice.edu/comp412/Lectures.
crshults 11y ago
Holub's 'Compiler Design in C' is out of print, so he gives it away for free: www.holub.com/software/compilerDesignInC.pdf Probably not exactly what you're asking for, but hey, free book.
eliben 11y ago
It's cute how he compares his "for loop parser" that handles C for-loops with Clang's, that handles C++ stuff including range loops - to show how his code is simpler :) Silly silly Clang developers for making their code too complex!
- andrewchambers 11y ago
  You felt the need to make this comment and that shows you don't have confidence average people will be able to work that out just from looking at the code, which was my point all along. Of course I know clang handles more, it is also designed as a library for other tools. The fact that clang mixes C and C++ parsing is not a merit, more like a necessary evil. This doesn't contradict my point on code clarity at all.
kazinator 11y ago
> It gives me a funny sense of pride that my compiler can now be used to improve itself. Only with difficulty, because your compiler is written in a language that is poorly suited for writing compilers. How about using nice high level language whose implementation is partially written in C to write a C compiler in that nice high level language which then compiles that partially-written-in-C component of the implementation of that high level language.
- andrewchambers 11y ago
  You would be surprised how the logic for a c compiler is pretty densely compressed, even in C code. You don't actually gain too much by switching to haskell or ocaml (I have done experiments).

105 points by andrewchambers 11y ago

It's always great to see more people writing their own compilers - a "proof by example" that compilers do not have to be magical and mysterious special software that only few experts can write. The theory may be deep, but in practice getting a basic working compiler doesn't require all that much. I notice you're using a recursive-descent parser, which I think is a good idea because it can actually reduce complexity over one made with parser-generators; in fact it's simple enough that even beginners who have just grasped recursion should be able to understand and write one. Once you have a basic parser that can evaluate arithmetic expressions, extending that to generating AST nodes and parse a (mostly) simple language like C is not so difficult. If I remember correctly, at least one college has an expression evaluator as a first-year CS assignment related to recursion. It's interesting that one of the sections of K&R, on reading and writing C declarations, even contains a simple parser for them --- I'm not aware of any introductory books for other languages which contain small pieces of their implementation. That said, you can use the "precedence climbing" technique[1] to collapse many of the recursive functions for most of the expression operators into one function with a succinct loop and a table, making your parser even simpler and faster. C4[2] is an example of this technique but with a series of if-else in the body of the function instead of a table, and I think is worth some careful study just for its mindblowingly awesome ridiculous simplicity. [1] https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing [2] https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822

emptybits 11y ago
introductory books for other languages which contain small pieces of their implementation I feel like two of the very few contenders for this might be books on Forth or Lisp, though still maybe not an "introductory" book.
- junke 11y ago
  Such as Queinnec's Lisp in Small Pieces (https://en.wikipedia.org/wiki/Lisp_in_Small_Pieces https://en.wikipedia.org/wiki/Lisp_in_Small_Pieces)
andrewchambers 11y ago
I actually plan to do exactly that that for the preprocessor's expression parser. Thanks for the info!
- w23j 11y ago
  You probably already know this stuff and don't need the info. But maybe somebody else reading this can find the link useful. This is a great tutorial on expression parsing using Pratt Parsers by Bob Nystrom: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...
david-given 11y ago
C is notoriously painful to parse with a parser generator because it's not context free --- consider this statement: foo * bar; It can't be parsed until you know whether foo is a type or a variable --- indeed, depending on the implementation, it can't even be tokenised correctly. So you need hooks from the symbol table back into the tokeniser/parser. I'm not at all surprised that the author's using a hand-written parser, as it reduces the problem space considerably. (There's a really good article which I've been trying to find which goes into details about all the weird parsing edge cases due to the rules about exactly when a word goes into the symbol table which I've been completely unable to find...)
- andrewchambers 11y ago
  Here is a good one http://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc http://eli.thegreenplace.net/2012/07/05/how-clang-handles-th...
- yepguy 11y ago
  As far as I know C is context-free. If C's grammar is ambiguous, that just makes it an ambiguous context-free grammar [1]. [1]: https://en.wikipedia.org/wiki/Ambiguous_grammar https://en.wikipedia.org/wiki/Ambiguous_grammar
  - kazinator 11y ago
    The context-free terminology doesn't apply to C because the ambiguity rests in not knowing what is the lexical category of foo in "foo * bar". That information comes from semantics. A language whose semantics you have to understand to understand its syntax is outside of the entire formal language realm inside which we formally recognize a "context-free" category. That formal language realm is purely syntactic: the terminal symbols are just "dumb" and stand for themselves. They are subject to rules which indicate how those symbols are combined. C is "quasi context free" in that if we resolve what the raw tokens mean (which one is a type and which one isn't), then the resulting language is context-free. In fact stronger than context free: amenable not only to LALR(1) parsing approaches but to recursive descent, with a suitable refactoring of the left-recursive rules given in the standard.

hbbio 11y ago

Thanks for providing the links that compare your for loop parser to existing implementations, it's interesting: - Gcc is unreadable; - Clang is "advanced", but not readable; - yours and tcc are clean... But you know it's always a risk to compare yourself to Fabrice Bellard :)

andrewchambers 11y ago
Tcc is far faster. I have done some benchmarks and tcc is really incredible. He was just optimising for a different goal I think. edit: Compiling my parse.c file, tcc is 34 times faster than gcc -O0 and my compiler is 3-4 times faster than gcc -O0. I should make a post with the actual stats.
- david-given 11y ago
  It's worth mentioning that tcc started life as an entry in the Obfuscated C Contest: http://bellard.org/otcc/ http://bellard.org/otcc/ (It won.)
david-given 11y ago
Just to continue the catalogue: pcc is simple, but very old school and a bit contorted. libfirm is small and clean and generates excellent code. (Despite the name, it's a complete ANSI C compiler, as well as being a LLVM-light.) The ACK is easy to port and is a complete standalone toolchain including compilers, assemblers and linkers, but (at least on modern processors) produces code so bad that it will make you want to stab yourself in the eyes to make the pain go away. There's a look-but-don't-touch licensed compiler called vbcc which is by far the best C compiler I've ever seen; small, easy to understand, easy to port, and produces excellent code... but the author doesn't want to release it under an open source license. Any others?
- andrewchambers 11y ago
  libfirm doesn't really classify as small to me, it is currently 132,638 lines of code. The cparser alone is 11k lines of code (5 times the size of my c parser).

w23j 11y ago

Can somebody point me at some introductionary material (or approachable code base) to writing an optimizing compiler? There seem to be a lot of very good tutorials on writing a simple compiler, like http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://compilers.iecc.com/crenshaw/ http://compilers.iecc.com/crenshaw/ There are also readable code bases like tinyc or this one. However these always use a simple template based approach to code generation and stop there. Of course there are real world compiler (lvm, gcc, ...). However because of their size and complexity it's hard to learn from them. What I am interested in would be going from: "I have an AST and for this node type I output this assembly." to "I translate the AST to an IR. Transform an the IR in multiple passes and finally output decent asm." That is, something that talks about CFG analysis, register scheduling or maybe SSA form? I have read papers on SSA and Sea-of-Nodes IRs, but these of course always assume that you know how and why to use them. A more approachable text/github-repo that shows how to take the step from template base code gen to more advanced techniques would be great. (I hope it is ok to ask this here. Did not want to hijack the thread.)

quincunx 11y ago
After grinding through a bunch of compiler books I have to mention "Modern Compiler Implementation in C - Andrew A. Appel": http://www.amazon.co.uk/dp/0521607655 http://www.amazon.co.uk/dp/0521607655 as one that stands out. For LALR Parsers and DFA scanners and the like, I found the original Dragon Book http://www.amazon.co.uk/dp/B00EKYURHS http://www.amazon.co.uk/dp/B00EKYURHS is still best. Both books are very accessible reading.
andrewchambers 11y ago
Someone I know is writing a tiny llvm clone in C. It already can do integer operations faster than gcc -O1. It is currently closed source but it shouldn't be hard for my compiler to target his IR in the future. His backend is currently around 6k lines of code so should be relatively easy to understand, though understanding some of the concepts is harder overall.
rayiner 11y ago
This one is very readable: http://www.amazon.com/Engineering-Compiler-Second-Edition-Cooper/dp/012088478X http://www.amazon.com/Engineering-Compiler-Second-Edition-Co.... Corresponding lecture notes: https://www.clear.rice.edu/comp412/Lectures https://www.clear.rice.edu/comp412/Lectures.

crshults 11y ago

Holub's 'Compiler Design in C' is out of print, so he gives it away for free: www.holub.com/software/compilerDesignInC.pdf Probably not exactly what you're asking for, but hey, free book.

eliben 11y ago

It's cute how he compares his "for loop parser" that handles C for-loops with Clang's, that handles C++ stuff including range loops - to show how his code is simpler :) Silly silly Clang developers for making their code too complex!

andrewchambers 11y ago
You felt the need to make this comment and that shows you don't have confidence average people will be able to work that out just from looking at the code, which was my point all along. Of course I know clang handles more, it is also designed as a library for other tools. The fact that clang mixes C and C++ parsing is not a merit, more like a necessary evil. This doesn't contradict my point on code clarity at all.

kazinator 11y ago

> It gives me a funny sense of pride that my compiler can now be used to improve itself. Only with difficulty, because your compiler is written in a language that is poorly suited for writing compilers. How about using nice high level language whose implementation is partially written in C to write a C compiler in that nice high level language which then compiles that partially-written-in-C component of the implementation of that high level language.

andrewchambers 11y ago
You would be surprised how the logic for a c compiler is pretty densely compressed, even in C code. You don't actually gain too much by switching to haskell or ocaml (I have done experiments).