5 ms·

Oops, I Wrote a C++ Compiler

162 points by mpalme 8y ago

chubot 8y ago
The process of creating the parser went very smoothly thanks to this. The real work involves creating C# syntax classes that mirror the grammar. These classes form the Abstract Syntax Tree (AST) of the compiler. To address this problem, I use Zephyr ASDL to describe the abstract syntax of a language (which CPython also uses!) It's a little DSL that lets you write an ML-style algebraic data type, and generates a bunch of code for you. In CPython, you go from ~100 lines ASDL schema to ~10,000 lines of C! It underlies the 'ast' module in the stdlib. Why is Zephyr ASDL? http://www.oilshell.org/blog/2016/12/11.html http://www.oilshell.org/blog/2016/12/11.html It eliminates the need for a lot of boilerplate he pointed out: https://github.com/praeclarum/CLanguage/tree/master/CLanguage/Syntax https://github.com/praeclarum/CLanguage/tree/master/CLanguag...
- fmihaila 8y ago
  For those writing language processors in Java, I highly recommend having a look at JastAdd [1]. It's a great framework for implementing semantic analysis using attribute grammars [2]. The tool automatically generates Java classes to represent ASTs, based on a high-level description (a CFG grammar) of the desired AST shape. You can use any Java-based parser as long as the AST it produces is constructed from those classes. That's only the starting point; the real power is in the excellent support for expressing attribute computation. It uses a high-level, lazy equational formalism extended by the programmer with custom logic, which is then turned into automatically-generated Java code. Compilers/interpreters written in JastAdd tend to be very well structured and easy to maintain. It's one of my all-time favourite libraries, actively maintained, and very well documented. [1] http://jastadd.org/web/documentation/concept-overview.php http://jastadd.org/web/documentation/concept-overview.php [2] https://en.wikipedia.org/wiki/Attribute_grammar https://en.wikipedia.org/wiki/Attribute_grammar
  - lopatin 8y ago
    And for Scala, there's Kiama https://bitbucket.org/inkytonik/kiama https://bitbucket.org/inkytonik/kiama
amelius 8y ago
Please don't call it C++ if it doesn't even support constructors and destructors. People will be trying to port their existing code, and will be unpleasantly surprised. > But the truth is, I’m just going to keep listening to users and improving the parts I can. I am not trying to recreate GCC or LLVM. Why not use GCC or LLVM as part of your project? That seems like a better investment of your time.
- craftyguy 8y ago
  > Please don't call it C++ if it doesn't even support constructors and destructors. At least they recognize this is missing, and call it out. > Why not use GCC or LLVM as part of your project? That seems like a better investment of your time. Learning opportunity? Maybe they're trying to solve a problem? Or do you think the LLVM folks should have just used GCC instead of wasting their time on LLVM?
  - umanwizard 8y ago
    Aren't constructors and destructors basically the main idea of c++?
    - FartyMcFarter 8y ago
      C++ is too big to have any "main feature", but in any case yeah, it's a huge deal.
- jchw 8y ago
  It is very well explained? GCC and Clang would be nightmares to integrate into an app that runs on many platforms including iOS, and even once you did, you'd still need to implement an interpreter, because you're not allowed to JIT on the app store. Compiling a toolchain for a desktop platform is easy. Cross compiling a toolchain is moderately easy. But embedding a toolchain into an iOS app, where you have to get it and all of its dependencies compiling for iOS, definitely seems like a massive challenge.
  - 8y ago
aaaaaaaaaab 8y ago
More like a “C++ [1] compiler”. [1] restrictions may apply
- saagarjha 8y ago
  To be honest, that's most C++ compilers.
  - aaaaaaaaaab 8y ago
    Touché
  - int_19h 8y ago
    Most C++ compilers still implement most of the C++ standard. This thing basically implements C, and adds methods to structs.
  - mhh__ 8y ago
    That's only technically true. The main C++ compilers in common use basically support, aim to support or have collectively agreed not to support parts of the C++ standard.
    - jcranmer 8y ago
      > have collectively agreed not to support parts of the C++ standard. Those parts were ripped out of the standard. (The big one is export templates, where the expert compiler implementers when asked for feedback about how to implement it said "don't").
hasahmed 8y ago
Very cool
njsubedi 8y ago
This post reminded me of myself in 2012. Where did all that energy go?
maxxxxx 8y ago
Nice! I think doing this is a great learning experience. I think I understand how to write a basic compiler but I am completely stumped by writing an optimizer. How do you model that?
- archgoon 8y ago
  The llvm compiler has it's optimization routines here: https://github.com/llvm-mirror/llvm/tree/master/lib/Transforms https://github.com/llvm-mirror/llvm/tree/master/lib/Transfor... You can play around with how it takes in llvm code to optimized llvm code by using the opt tool. Here's a basic example. $ cat test.c #include <stdio.h> int main() { for (int i = 0; i < 3; i++) { printf("hello world"); } } $ clang -c -S -emit-llvm test.c $ cat test.ll ** too long replacing with gist** https://gist.github.com/cwgreene/b6f33d40ad735a448ed15057d91fdbdc $ opt -S -print-before-all -O2 test.ll ** too long, replacing with gist** https://gist.github.com/cwgreene/99b3075dbfffae35a5745934ded217fb ** final result** @.str = private unnamed_addr constant [12 x i8] c"hello world\00", align 1 ; Function Attrs: nounwind uwtable define i32 @main() #0 { entry: %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0)) #2 %call.1 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0)) #2 %call.2 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0)) #2 ret i32 0 } The command `opt -S -print-before-all -O2` can be manually modified to specify exactly which compiler passes you want to see. You can run `opt --help` to see a list of all compiler passes. (you can figure out what code performs by looking at the * * * IR Dump Before `MODULE NAME` * * * and finding the associated logic in the Lib directory) In the case of llvm, the idea for them is they break the code into things called 'basic blocks' which, along with using Single Static Assignment, are more easily analyzed, transformed, and simplified.
- mhh__ 8y ago
  It's a bit idiosyncratic but Steven Muchnick's "Advanced Compiler Design and implementation" is something of a bible for optimising compiler design. Of course, other books are available. I haven't look around recently enough to name any off-hand but there are some really good free textbooks/monographs(etc.) on optimisation around. Search "ssabook", there's a really great data flow analysis book out there somewhere which if I find I will edit and include.
cift 8y ago
This looks like a cool app, the post says it's available on Android but I can't seem to find it on the Play Store. Anyone know what happened?
ncmncm 8y ago
Does this seem insane to anyone else? Emulating an Arduino, you get no benefit at all from re-implementing a compiler. The Instruction Set Architecture is rigorously defined. All you need to do is implement that, plus some peripherals. Write a compiler from ATmega machine code to your VM, if you like. This C++-- will never be actually useful to anyone, and people developing for Arduino already have more than one anyway. It might be educational, but almost all the work has gone into the least useful and least educational parts of it. The destructor is by far the single most essential feature of C++. After that, constructors, templates, and the standard library take 2nd, 3rd, and 4th place. If you think integer conversions are important, you have not learned much at all. There are already several ATmega emulators done sanely. One more would not be bad, and could break new ground. Use virtualization primitives to make an x86 program translated from ATmega think it's a real chip, and emulate the Arduino 100x faster than the real one.
mynegation 8y ago
It takes hundreds, if not thousands person-years to write C++ compiler intentionally, damn next to impossible to write it accidentally as title implies. Frank is a talented engineer, I used to follow his work on Calca very closely. But as others noted, this does not seem to be anywhere close to C++. The problem with parsing C++ starts with C. Say you see the code “T(t);” at the beginning of a function body. What is it? Declaration of variable t of type T? Call of function T on variable t? You cannot parse it properly without symbol table. No context free parser handles C properly, let alone C++. It gets progressively and exponentially worse from here.
- userbinator 8y ago
  Parsing is the easy part of a C++ compiler, and the T t example you mentioned has a relatively simple solution (which is, as you say, using the symbol table). In fact that ambiguity is present in C as well (with typedefs), and yet it hasn't really stopped many others from writing their own C compilers which handle that case. It's the things like templates, multiple/virtual inheritance, and argument-dependent lookup/overload resolution which are difficult to get right, and the reason that even somewhat fully-featured C++ compilers are rare.
- sedachv 8y ago
  > You cannot parse it properly without symbol table. No context free parser handles C properly, let alone C++. It gets progressively and exponentially worse from here. C is actually pretty easy if you ignore all of the bad advice to use parser generators. I looked into the various YACC grammars for C I could find on the Internet, and all of them either had bugs or were incomplete. TCC[1] has a simple recursive-descent parser. With a recursive descent parser you also have the option of implementing the C pre-processor in the same step. Turns out I was able to implement a single-pass C parser and pre-processor as a bunch of Common Lisp read macros[2]. I have not looked into it, but the approach for C++ looks like it would be very different because template instantiation needs its own step. [1] https://bellard.org/tcc/ https://bellard.org/tcc/ [2] https://github.com/vsedach/Vacietis/blob/master/compiler/reader.lisp https://github.com/vsedach/Vacietis/blob/master/compiler/rea...
deleted 8y ago
[deleted]

162 points by mpalme 8y ago

The process of creating the parser went very smoothly thanks to this. The real work involves creating C# syntax classes that mirror the grammar. These classes form the Abstract Syntax Tree (AST) of the compiler. To address this problem, I use Zephyr ASDL to describe the abstract syntax of a language (which CPython also uses!) It's a little DSL that lets you write an ML-style algebraic data type, and generates a bunch of code for you. In CPython, you go from ~100 lines ASDL schema to ~10,000 lines of C! It underlies the 'ast' module in the stdlib. Why is Zephyr ASDL? http://www.oilshell.org/blog/2016/12/11.html http://www.oilshell.org/blog/2016/12/11.html It eliminates the need for a lot of boilerplate he pointed out: https://github.com/praeclarum/CLanguage/tree/master/CLanguage/Syntax https://github.com/praeclarum/CLanguage/tree/master/CLanguag...

fmihaila 8y ago
For those writing language processors in Java, I highly recommend having a look at JastAdd [1]. It's a great framework for implementing semantic analysis using attribute grammars [2]. The tool automatically generates Java classes to represent ASTs, based on a high-level description (a CFG grammar) of the desired AST shape. You can use any Java-based parser as long as the AST it produces is constructed from those classes. That's only the starting point; the real power is in the excellent support for expressing attribute computation. It uses a high-level, lazy equational formalism extended by the programmer with custom logic, which is then turned into automatically-generated Java code. Compilers/interpreters written in JastAdd tend to be very well structured and easy to maintain. It's one of my all-time favourite libraries, actively maintained, and very well documented. [1] http://jastadd.org/web/documentation/concept-overview.php http://jastadd.org/web/documentation/concept-overview.php [2] https://en.wikipedia.org/wiki/Attribute_grammar https://en.wikipedia.org/wiki/Attribute_grammar
- lopatin 8y ago
  And for Scala, there's Kiama https://bitbucket.org/inkytonik/kiama https://bitbucket.org/inkytonik/kiama

amelius 8y ago

Please don't call it C++ if it doesn't even support constructors and destructors. People will be trying to port their existing code, and will be unpleasantly surprised. > But the truth is, I’m just going to keep listening to users and improving the parts I can. I am not trying to recreate GCC or LLVM. Why not use GCC or LLVM as part of your project? That seems like a better investment of your time.

craftyguy 8y ago
> Please don't call it C++ if it doesn't even support constructors and destructors. At least they recognize this is missing, and call it out. > Why not use GCC or LLVM as part of your project? That seems like a better investment of your time. Learning opportunity? Maybe they're trying to solve a problem? Or do you think the LLVM folks should have just used GCC instead of wasting their time on LLVM?
- umanwizard 8y ago
  Aren't constructors and destructors basically the main idea of c++?
  - FartyMcFarter 8y ago
    C++ is too big to have any "main feature", but in any case yeah, it's a huge deal.
jchw 8y ago
It is very well explained? GCC and Clang would be nightmares to integrate into an app that runs on many platforms including iOS, and even once you did, you'd still need to implement an interpreter, because you're not allowed to JIT on the app store. Compiling a toolchain for a desktop platform is easy. Cross compiling a toolchain is moderately easy. But embedding a toolchain into an iOS app, where you have to get it and all of its dependencies compiling for iOS, definitely seems like a massive challenge.
- 8y ago

aaaaaaaaaab 8y ago

More like a “C++ [1] compiler”. [1] restrictions may apply

saagarjha 8y ago
To be honest, that's most C++ compilers.
- aaaaaaaaaab 8y ago
  Touché
- int_19h 8y ago
  Most C++ compilers still implement most of the C++ standard. This thing basically implements C, and adds methods to structs.
- mhh__ 8y ago
  That's only technically true. The main C++ compilers in common use basically support, aim to support or have collectively agreed not to support parts of the C++ standard.
  - jcranmer 8y ago
    > have collectively agreed not to support parts of the C++ standard. Those parts were ripped out of the standard. (The big one is export templates, where the expert compiler implementers when asked for feedback about how to implement it said "don't").

hasahmed 8y ago

Very cool

njsubedi 8y ago

This post reminded me of myself in 2012. Where did all that energy go?

maxxxxx 8y ago

Nice! I think doing this is a great learning experience. I think I understand how to write a basic compiler but I am completely stumped by writing an optimizer. How do you model that?

archgoon 8y ago
The llvm compiler has it's optimization routines here: https://github.com/llvm-mirror/llvm/tree/master/lib/Transforms https://github.com/llvm-mirror/llvm/tree/master/lib/Transfor... You can play around with how it takes in llvm code to optimized llvm code by using the opt tool. Here's a basic example. $ cat test.c #include <stdio.h> int main() { for (int i = 0; i < 3; i++) { printf("hello world"); } } $ clang -c -S -emit-llvm test.c $ cat test.ll ** too long replacing with gist** https://gist.github.com/cwgreene/b6f33d40ad735a448ed15057d91fdbdc $ opt -S -print-before-all -O2 test.ll ** too long, replacing with gist** https://gist.github.com/cwgreene/99b3075dbfffae35a5745934ded217fb ** final result** @.str = private unnamed_addr constant [12 x i8] c"hello world\00", align 1 ; Function Attrs: nounwind uwtable define i32 @main() #0 { entry: %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0)) #2 %call.1 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0)) #2 %call.2 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0)) #2 ret i32 0 } The command `opt -S -print-before-all -O2` can be manually modified to specify exactly which compiler passes you want to see. You can run `opt --help` to see a list of all compiler passes. (you can figure out what code performs by looking at the * * * IR Dump Before `MODULE NAME` * * * and finding the associated logic in the Lib directory) In the case of llvm, the idea for them is they break the code into things called 'basic blocks' which, along with using Single Static Assignment, are more easily analyzed, transformed, and simplified.
mhh__ 8y ago
It's a bit idiosyncratic but Steven Muchnick's "Advanced Compiler Design and implementation" is something of a bible for optimising compiler design. Of course, other books are available. I haven't look around recently enough to name any off-hand but there are some really good free textbooks/monographs(etc.) on optimisation around. Search "ssabook", there's a really great data flow analysis book out there somewhere which if I find I will edit and include.

cift 8y ago

This looks like a cool app, the post says it's available on Android but I can't seem to find it on the Play Store. Anyone know what happened?

ncmncm 8y ago

Does this seem insane to anyone else? Emulating an Arduino, you get no benefit at all from re-implementing a compiler. The Instruction Set Architecture is rigorously defined. All you need to do is implement that, plus some peripherals. Write a compiler from ATmega machine code to your VM, if you like. This C++-- will never be actually useful to anyone, and people developing for Arduino already have more than one anyway. It might be educational, but almost all the work has gone into the least useful and least educational parts of it. The destructor is by far the single most essential feature of C++. After that, constructors, templates, and the standard library take 2nd, 3rd, and 4th place. If you think integer conversions are important, you have not learned much at all. There are already several ATmega emulators done sanely. One more would not be bad, and could break new ground. Use virtualization primitives to make an x86 program translated from ATmega think it's a real chip, and emulate the Arduino 100x faster than the real one.

mynegation 8y ago

It takes hundreds, if not thousands person-years to write C++ compiler intentionally, damn next to impossible to write it accidentally as title implies. Frank is a talented engineer, I used to follow his work on Calca very closely. But as others noted, this does not seem to be anywhere close to C++. The problem with parsing C++ starts with C. Say you see the code “T(t);” at the beginning of a function body. What is it? Declaration of variable t of type T? Call of function T on variable t? You cannot parse it properly without symbol table. No context free parser handles C properly, let alone C++. It gets progressively and exponentially worse from here.

userbinator 8y ago
Parsing is the easy part of a C++ compiler, and the T t example you mentioned has a relatively simple solution (which is, as you say, using the symbol table). In fact that ambiguity is present in C as well (with typedefs), and yet it hasn't really stopped many others from writing their own C compilers which handle that case. It's the things like templates, multiple/virtual inheritance, and argument-dependent lookup/overload resolution which are difficult to get right, and the reason that even somewhat fully-featured C++ compilers are rare.
sedachv 8y ago
> You cannot parse it properly without symbol table. No context free parser handles C properly, let alone C++. It gets progressively and exponentially worse from here. C is actually pretty easy if you ignore all of the bad advice to use parser generators. I looked into the various YACC grammars for C I could find on the Internet, and all of them either had bugs or were incomplete. TCC[1] has a simple recursive-descent parser. With a recursive descent parser you also have the option of implementing the C pre-processor in the same step. Turns out I was able to implement a single-pass C parser and pre-processor as a bunch of Common Lisp read macros[2]. I have not looked into it, but the approach for C++ looks like it would be very different because template instantiation needs its own step. [1] https://bellard.org/tcc/ https://bellard.org/tcc/ [2] https://github.com/vsedach/Vacietis/blob/master/compiler/reader.lisp https://github.com/vsedach/Vacietis/blob/master/compiler/rea...

deleted 8y ago

[deleted]