A Brief and Brisk Overview of Compiler Architecture

https://blog.felixangell.com/compilers-brief-and-brisk

by signa11 • 7 years ago

136 23 7 years ago

blog.felixangell.com

jfoutz• 7 years ago

If you would like a heartwarming tale of an engineers first compiler, this is the article for you.

There is either nothing to learn here, or a spectacular insight into compilation, depending on where you are in your career.

Compilers are fun. It’s an invaluable experience having written one. There is no magic left in a computer once you’ve written a compiler.

If you have written a compiler, this article is amusing. You get to see a programmers eyes open.

If you have not written a compiler, you get some insight about how they work- but perhaps you get more insight about how you work.

Also, the author should constant fold his arithmetic example. It slows down compile time, but makes the program faster.

bluedino• 7 years ago

I love these articles as they are a big 'magical' to me. They make me wish I had gotten a CS degree.

eatonphil3• 7 years ago

You don't need a CS degree to enjoy this stuff or learn more! I do not have a CS degree, or any degree at all. It took me a few years before I built up the courage to write an interpreter or compiler but I was compelled by peers who had built their own (and didn't attend college either).

There are numerous bloggers who dig deeper into the implementation of things and explain them. You just have to start asking "how do I build X from scratch".

pcr910303• 7 years ago

Are there resources to learn compilers in general?̊̈ It’s hard to find resources that are

* In text * Free and accessible in the web * Not lengthy (not a 1000 page book) * Points to resources to read after.

Any suggestions?̊̈ I have read the unfinished http://www.craftinginterpreters.com/ , but I would like to know more about compilers (that emit machine code).

rwmj2• 7 years ago

For the majority of use cases a simple rule suffices: Write a parser which generates LLVM IR and feed the IR into LLVM. You only need to research two topics: parser generators and LLVM IR, and both are pretty simple skills to pick up.

There are a lot of cases where that doesn't work (eg. writing a functional language or a JIT or doing programming language research) but those are edge cases. In those cases you probably want to read one of Appel's books ("Modern compiler implementation in ML" for example), or the Dragon Book.

sischoel• 7 years ago

These books are kind of old. Are they still state of the art or is there something newer?

I had a compiler class at university but that was a while ago, so I would like to update my knowledge because there seems to be a lot of exiting stuff going on with compilers and transpilers.

oldandtired• 7 years ago

Here, I would disagree with you in part. There are more than two topics that are needed.

First. Design your language if you are not going to use something that already exists. So you need to understand grammars and the various pitfalls. There are quite a number of tutorials on this subject freely available around the web.

Second. Understand what you want your language to actually mean, this is the subject of semantics. So if you are starting out, make a simple grammar and simple associated semantics. Again there is various material around the traps that you can avail yourself of.

Third. Have a look at the various parser generators out there and what they expect in terms of your language. There are many and each has its pros and cons. Again, there are various tutorials about the subject.

Fourth. If your language is relatively simple and has relatively simple semantics, see what is required for the generation of LLVM IR. If there is any complexity in the language and its semantics, LLVM IR may not necessarily be the way to go. So, back to the first and second points, keep your investigatory language simple in both its syntax (grammar) and its semantics.

Fifth. Have fun. The entire subject can be a delight to learn, but some of the material out there is deadly boring and will quickly turn most people off the subject. But it is actually fun. Son enjoy the time you spend learning about the subject.

imoldfella• 7 years ago

100% agree. If starting now I think you should consider targeting mlir[1]. It fixes many problems you will have with llvm, and allows you to create language specific dialects and transformations. Impressive new work by a top-notch team led by LLVM creator Chris Lattner. It has LLVM as an optional target, so you get that for free.

For a parser, you should consider using tree-sitter[2]. Tree-sitter gives you live editor support for free. Impressive work by Max Brunsfeld.

[1] https://www.youtube.com/watch?v=qzljG6DKgic [2] https://www.youtube.com/watch?v=a1rC79DHpmY

z29LiTp5qUC30n• 7 years ago

Yes, read this https://github.com/oriansj/M2-Planet

and you will know how a cross platform self-hosting C compiler works in 1,982 lines of code

and if you want to know how an assembler works read this: https://github.com/oriansj/mescc-tools/

only about 562 lines for the linker, 645 for the macro assembler and 204 lines if you want dwarf stubs in your binaries. Oh and it is cross platform too

markjenkinswpg• 7 years ago

I'm a fan of this.

But, note "The PLAtform NEutral Transpiler"..."allows one to compile a subset of the C language".

Subset of C not being C.

eatonphil3• 7 years ago

I've got a work-in-progress series [0] (first three posts are up) on writing a compiler from scratch in JavaScript (no third-party libraries). The first two posts target amd64 assembly, the third post ports to LLVM IR. You may not learn much about the best way to build compilers [i.e. 1) using a parser generator and 2) not emitting text directly], but you'll start with minimal code/functionality and build up from there -- which I always find super useful in learning new things.

There are many series like mine throughout the internet that are generally useful aides when combined with the typical dense, classical compiler textbook. The single exception to "dense textbooks" on compilers is Nikolaus Wirth's Compiler Construction [1] where he takes you through writing a compiler from scratch in ~100 pages. This is one of my favorite compiler (and programming?) books by one of the coolest programming language researchers. But even it may not be super accessible as a first on compilers.

[0] http://notes.eatonphil.com/compiler-basics-lisp-to-assembly....

[1] http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf

userbinator• 7 years ago

This one should be easy to understand: https://compilers.iecc.com/crenshaw/

rambojazz• 7 years ago

Sorry what is this ?̊̈

nabla9• 7 years ago

Compiler architecture is also a good metaphor for understanding what Common Lisp is all about.

Common Lisp = the programmable compiler & runtime all in one. Most CL implementations compile before calling eval. Read–eval–print loop is actually parse-compile-execute-print loop.

  * (defun foo (x) (+ x 1))
  FOO
  * (disassemble 'foo)

  ; disassembly for FOO
  ; Size: 38 bytes. Origin: #x1003A7DD1C
  ; 1C:       498B4C2460       MOV RCX, [R12+96] ; thread.binding-stack-pointer
                                                 ; no-arg-parsing entry point
  ; 21:       48894DF8         MOV [RBP-8], RCX
  ; 25:       BF02000000       MOV EDI, 2
  ; 2A:       488BD3           MOV RDX, RBX
  ; 2D:       41BBC0010020     MOV R11D, 536871360  ; GENERIC-+
  ; 33:       41FFD3           CALL R11
  ; 36:       488B5DF0         MOV RBX, [RBP-16]
  ; 3A:       488BE5           MOV RSP, RBP
  ; 3D:       F8               CLC
  ; 3E:       5D               POP RBP
  ; 3F:       C3               RET
  ; 40:       CC10             BREAK 16   ; Invalid argument count trap
  NIL

Front end = Read function does the lexical analysis. CL syntax is almost one-to-one with the AST, so lexer-parser part is simple. You can reprogram the lexer with reader macros if you want. This is the last place where CL code is text. After it's reader is done with it, the code is represented with CL data structures.

Middle End = CL has multiple passes with AST. First normal macros, then compiler macros operate here. They deal with CL data. Lists, symbols, structs, objects, arrays, numbers, etc. CL packages are symbol tables. AST and IR are all CL data structures.

Back End = finally the function 'compile' function compiles the end result into into native code. Saving the image and exiting the runtime is like compiling in normal languages.

lispm• 7 years ago

Compiling will not change READ into PARSE. READ is still there.

Most CL implementations compile before calling eval

Many or a lot, but I'm not sure actually most.

There are quite a lot which use an Interpreter in the REPL, but where one can compile on demand. SBCL by default compiles. LispWorks for example does not.

After it's reader is done with it, the code is represented with CL data structures.

Right, but the data structures carry no syntactic information. If you write (1 2 +) the reader accepts it and does not know that this is invalid syntax.

AST and IR are all CL data structures.

True, but not necessarily like s-expressions...

See for example data structures the SBCL compiler uses:

https://github.com/sbcl/sbcl/blob/master/src/compiler/node.l...

Saving the image and exiting the runtime is like compiling in normal languages.

Working with images is optional - the Common Lisp standard says nothing about images at all.

nv-vn• 7 years ago

The funny thing about compilers is that one architecture has been established as the dominant architecture (the one described here) for probably the past 50 years. Almost without exception, every compiler is structured just about exactly the same. If you're interested in an alternative architecture, it's worth reading up about Nanopass compilers. While largely the same basic ideas, Nanopass tries to distill each discrete action into its own pass -- think of it like composing a bunch of programs using shell pipes. So rather than just Frontend=>Middle End=>Backend you end up with something like Lex=>Parse=>Remove Lambdas=>Remove Loops=>Remove Conditionals=>SSA=>Allocate Registers=>Eliminate Dead Code=>.....

all2• 7 years ago

This? https://nanopass.org/

It sounds like someone took the Unix philosophy "each program should do one thing well" and applied it to compilers.

enos_feedler• 7 years ago

When I worked on GPU compiler backends the middle and backend passes basically were a collection of more basic passes that did one thing, in sequence. I wouldn't call this an alternative architecture. I think it's just an implementation detail of the dominant architecture.

A Brief and Brisk Overview of Compiler Architecture

Related Stories