7 ms·

What are some current best practices for writing (C) compilers that were not common when, say, gcc 1.0 was written? Would someone writing a basic C compiler tod

What are some current best practices for writing (C) compilers that were not common when, say, gcc 1.0 was written? Would someone writing a basic C compiler today approach it differently than Stallman did with gcc 1.0?

petercooper 9y ago
Depends if you mean a hobby/small C compiler or if you were trying to write something of similar scope to gcc or Watcom, say. If the latter, there have been big developments in the optimization stages (not least due to CPU and architecture changes over the years) and the approach to targeting runtimes would be quite different (far less likely to target x86 directly nowadays when there are things like LLVM or even the CLR/JVM/similar). At the risk of sparking controversy, I think Go is a great example of "how would they do it now?" which goes further than compiler techniques and back to rethinking what the runtime should even be.
- amelius 9y ago
  > I think Go is a great example of "how would they do it now?" which goes further than compiler techniques and back to rethinking what the runtime should even be. Agreed, but I wish they released the runtime as a separate component, in the same spirit as LLVM.
chubot 9y ago
IMO one big advance would be writing the compiler in something other than C. C is a bad language for writing compilers in (including C compilers)! Even (cough) C++ is better than C for this use case, e.g. comparing LLVM vs. GCC. But C++ has problems too though -- the TableGen language in LLVM is an interesting example of why a big C++ project like LLVM/Clang doesn't want all its logic/specification in C++. They really use C++ to the hilt and they still want/need a DSL. Other interesting options would be Swift, Rust, OCaml, or Go. Swift, Rust, and OCaml all have algebraic data types. I guess choosing something other than C or C++ is a little unusual because there is the tendency to self-host. The Rust, OCaml, and Go compilers are written in Rust, OCaml, and Go, respectively. I'm pretty sure Swift is a lot of C++, but that will probably change as times goes on.
- schwede 9y ago
  One cool benefit of using C for a C compiler though is the ability to self host the compiler.
- qznc 9y ago
  I think C is fine for a simple compiler. Why are algebraic data types so relevant? Pattern matching is nice, because switch statements plus unpacking is more verbose. For big optimizing compilers you appreciate abstractions like C++ enables. for example, a data flow Analysis framework.
  - jmite 9y ago
    Algebraic data is just so perfectly suited to abstract syntax. It's clearly possible to model an AST in C, but not to do it in an ergonomic z typesafe way.
  - ufo 9y ago
    In addition to being more succinct, algebraic data types are also better about warning if you forgot to handle one of the cases.
delhanty 9y ago
Supplementary to that and also a bit more specific I'd be grateful for an answer to the following: Is it considered best practice today to use Flex & Bison for the front-end of (for example) a basic C compiler?
- chubot 9y ago
  I don't think it's ever been the case that C front ends used lex/yacc. Whether it's "best practice" I suppose depends on who you ask! (You'll certainly learn it with parser generators in university because writing a hand-written parser takes too long for an undergrad class, and they will only cover a tiny subset of C if anything.) You can see here that the original C compilers use a hand-written expression parser using the Shunting Yard algorithm, and I'm sure the rest of the front end is hand-written too: http://www.oilshell.org/blog/2017/04/22.html http://www.oilshell.org/blog/2017/04/22.html C predates lex/yacc so the syntax wasn't really designed with them in mind. Some other potential problems: (1) Distinguishing types and variables in C: https://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited https://eli.thegreenplace.net/2011/05/02/the-context-sensiti... https://en.wikipedia.org/wiki/The_lexer_hack https://en.wikipedia.org/wiki/The_lexer_hack (2) The preprocessor. While it doesn't prevent you from using lex/yacc for the C parser, this is an entirely separate lexer and parser that is always written by hand AFAICT. Awk, on the other hand, is almost always parsed with lex/yacc. The language was almost designed around those tools. I think if you're writing say your first compiler you should try to use lex and yacc. I think you can solve the context-sensitivity problem but I haven't done it myself. Operator precedence probably requires some extensions or maybe you can encode the many levels of C precedence in the grammar. One thing I found from implementing a shell parser [1] is that the POSIX spec uses yacc grammars, even if the languages aren't best parsed with bottom-up parsing. For example, all shells except bash use top-down parsing. Analogously, the C grammar may "manually" encode the operator precedence, even though the original C parsers and current ones like GCC/Clang actually use an operator precedence algorithm like the Shunting Yard algorithm, not yacc's shift-reduce algorithm. e.g. this grammar manually encodes it: https://www.lysator.liu.se/c/ANSI-C-grammar-y.html https://www.lysator.liu.se/c/ANSI-C-grammar-y.html Not that yacc can't parse expressions -- it's just something interesting I found. Also, for shell, there are a bunch of parsing rules that are necessarily listed separately from the grammar, and I'm sure the same is true for C. [1] http://www.oilshell.org/blog/tags.html?tag=parsing-shell#parsing-shell http://www.oilshell.org/blog/tags.html?tag=parsing-shell#par...

petercooper 9y ago

Depends if you mean a hobby/small C compiler or if you were trying to write something of similar scope to gcc or Watcom, say. If the latter, there have been big developments in the optimization stages (not least due to CPU and architecture changes over the years) and the approach to targeting runtimes would be quite different (far less likely to target x86 directly nowadays when there are things like LLVM or even the CLR/JVM/similar). At the risk of sparking controversy, I think Go is a great example of "how would they do it now?" which goes further than compiler techniques and back to rethinking what the runtime should even be.

amelius 9y ago
> I think Go is a great example of "how would they do it now?" which goes further than compiler techniques and back to rethinking what the runtime should even be. Agreed, but I wish they released the runtime as a separate component, in the same spirit as LLVM.

chubot 9y ago

IMO one big advance would be writing the compiler in something other than C. C is a bad language for writing compilers in (including C compilers)! Even (cough) C++ is better than C for this use case, e.g. comparing LLVM vs. GCC. But C++ has problems too though -- the TableGen language in LLVM is an interesting example of why a big C++ project like LLVM/Clang doesn't want all its logic/specification in C++. They really use C++ to the hilt and they still want/need a DSL. Other interesting options would be Swift, Rust, OCaml, or Go. Swift, Rust, and OCaml all have algebraic data types. I guess choosing something other than C or C++ is a little unusual because there is the tendency to self-host. The Rust, OCaml, and Go compilers are written in Rust, OCaml, and Go, respectively. I'm pretty sure Swift is a lot of C++, but that will probably change as times goes on.

schwede 9y ago
One cool benefit of using C for a C compiler though is the ability to self host the compiler.
qznc 9y ago
I think C is fine for a simple compiler. Why are algebraic data types so relevant? Pattern matching is nice, because switch statements plus unpacking is more verbose. For big optimizing compilers you appreciate abstractions like C++ enables. for example, a data flow Analysis framework.
- jmite 9y ago
  Algebraic data is just so perfectly suited to abstract syntax. It's clearly possible to model an AST in C, but not to do it in an ergonomic z typesafe way.
- ufo 9y ago
  In addition to being more succinct, algebraic data types are also better about warning if you forgot to handle one of the cases.

delhanty 9y ago

Supplementary to that and also a bit more specific I'd be grateful for an answer to the following: Is it considered best practice today to use Flex & Bison for the front-end of (for example) a basic C compiler?

chubot 9y ago
I don't think it's ever been the case that C front ends used lex/yacc. Whether it's "best practice" I suppose depends on who you ask! (You'll certainly learn it with parser generators in university because writing a hand-written parser takes too long for an undergrad class, and they will only cover a tiny subset of C if anything.) You can see here that the original C compilers use a hand-written expression parser using the Shunting Yard algorithm, and I'm sure the rest of the front end is hand-written too: http://www.oilshell.org/blog/2017/04/22.html http://www.oilshell.org/blog/2017/04/22.html C predates lex/yacc so the syntax wasn't really designed with them in mind. Some other potential problems: (1) Distinguishing types and variables in C: https://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited https://eli.thegreenplace.net/2011/05/02/the-context-sensiti... https://en.wikipedia.org/wiki/The_lexer_hack https://en.wikipedia.org/wiki/The_lexer_hack (2) The preprocessor. While it doesn't prevent you from using lex/yacc for the C parser, this is an entirely separate lexer and parser that is always written by hand AFAICT. Awk, on the other hand, is almost always parsed with lex/yacc. The language was almost designed around those tools. I think if you're writing say your first compiler you should try to use lex and yacc. I think you can solve the context-sensitivity problem but I haven't done it myself. Operator precedence probably requires some extensions or maybe you can encode the many levels of C precedence in the grammar. One thing I found from implementing a shell parser [1] is that the POSIX spec uses yacc grammars, even if the languages aren't best parsed with bottom-up parsing. For example, all shells except bash use top-down parsing. Analogously, the C grammar may "manually" encode the operator precedence, even though the original C parsers and current ones like GCC/Clang actually use an operator precedence algorithm like the Shunting Yard algorithm, not yacc's shift-reduce algorithm. e.g. this grammar manually encodes it: https://www.lysator.liu.se/c/ANSI-C-grammar-y.html https://www.lysator.liu.se/c/ANSI-C-grammar-y.html Not that yacc can't parse expressions -- it's just something interesting I found. Also, for shell, there are a bunch of parsing rules that are necessarily listed separately from the grammar, and I'm sure the same is true for C. [1] http://www.oilshell.org/blog/tags.html?tag=parsing-shell#parsing-shell http://www.oilshell.org/blog/tags.html?tag=parsing-shell#par...