if you can handle compilers, assemblers are a piece of cake. So you can add a flag to emit a .o instead of a .S when you get down to that level.

I've never actually written a linker, but when you're down at that level it's fairly obvious what needs to happen. There's some sort of binary prolog that indicates this is an executable. Then you have this table of symbolic names to offsets, you replace the symbolic references with actual numbers.

If you have something like a.o, b.o, and c.o, and a.o needs to call foo in c.o, it's kind of just sizeof(a.o) + sizeof(b.o) + offset(foo, c.o)

assemblers and linkers are kinda tough because they need to be perfect, but you don't have the hard algorithmic problems you have in compilers, like register allocation.

Also, if you limit yourself to a small subset of x86, you can pretty quickly verify correctness using existing tools, then make toy versions of your assembler and linker. Adding more instructions only means touching the assembler.

You can do it!

A great compiler based on this principle is TCC: http://bellard.org/tcc/ The code generators are basically built around calling parser.next_token(). It is simple (highly recommend reading the source) and very fast. There is also a linker included.

I prefer this demonstration to the one in that paper:

Interpreter: https://news.ycombinator.com/item?id=8558822

JIT compiler: https://news.ycombinator.com/item?id=8746054

To make things more interesting, it's "real syntax", i.e. C-like, rather than the "almost no parsing required" syntax of a Lisp, even smaller than TCC, and yet it can still compile itself.

C4 and the few variants it's spawned have probably become my favourite family of tiny, understandable, but complete compilers. The sheer elegance and simplicity --- one file of less than 1K lines --- makes studying them highly recommended. Almost all the other tiny/teaching/toy compilers I've seen are larger, less capable, or both. I don't know if anyone has made a variant of C4 that generates an AST, but doing that would probably not be too difficult either, and then you'd have a tiny compiler you could experiment on with optimisation and such.

I watched this talk and it was pretty interesting:

https://www.youtube.com/watch?v=KINIAgRpkDA

https://talks.golang.org/2016/asm.slide#1

If I am understanding right, the claim is that they have a single assembly language for ALL GO architectures, based on something Ken Thompson wrote in the 90's for some National Instruments (?) chip. He actually says that all assembly language looks the same now.

I was sort of surprised by that claim. I would like to hear a critique of this from other compiler writers. Does the fact that Go uses a single assembly language make the code slower? I imagine taking advantage of target-specific knowledge is useful, but I don't know how much.

LLVM has this pretty elaborate TableGen system to express target-specific knowledge.

He also makes the claim that they will be able auto-generate a new backend from the PDF description of the architecture. And he says somewhere that they reduce a lot of the work to simple "text processing" (symbol manipulation) and didn't require opening up any processor manuals.

I can see how arithmetic and bitshifting is the same among all architectures. But I would think that even loads and stores have differences, at least if you want to use the processor efficiently. But he says everything kinda looks the same.

Also, another thought is that compiling to WebAssembly might be simpler than native executables?

The basics are the same (and indeed that is why many RISCs resemble MIPS), but you're correct that more advanced (or perhaps I could say, Intel-ligent ;-) architectures have many more interesting instructions that are beyond the subset, and can definitely save on code speed, size, or both when used effectively but are not easy to match nor describe the semantics of. It's easy to match X+Y to an ADD, or even X = 4 * Y + C to an LEA, but at the other extreme, how would you match a whole AES encryption round and replace it with a single AESENC instruction? Currently, no compiler I know of can do that, so you must use intrinsics or pure Asm.

He does actually mention the AES instruction in the talk. I think they just have some one-offs to deal with those specific cases. I guess Go is different than C because it comes with a big standard library. They can just make sure that their standard library crypto uses the AESNES instruction, whereas C compilers have no idea what crypto library you're using.

I haven't looked more than superficially at any existing compilers outside of small toys. Reading large codebases is hard, and I have a harder time with it than most. (Hence my current project involving compilers: https://lobste.rs/s/n0d3qo/what_are_you_working_on_this_week... ) But let me put Go back on the head of the queue..

Also I think this representation is different architecturally. Go now uses an SSA representation apparently, which would be the equivalent of LLVM IR AFAIK. This assembly language is more toward the backend where as the IR is more like the "middle end".

there are many intermediate representations.

An option would be a Basic from the '80s: no functions, all variables are global. If you think implementing a return stack is too hard, forget about supporting gosub; goto may be harmful, but it is enough to write some interesting programs (Certainly forget about computed gosub/goto in your first version)

That makes lots of stuff incredibly easy. Variable 'a' always has the same address (the simplest implementation even would just allocate room for variables a-z, a%-z% and a$-z$ regardless of whether they got used, so that 'a' has the same address in every program)

Forgetting about optimization means that, for example

  a = a + 1
  a = 2 * a

  load a
  add 1
  store a
  load a
  mul 2
  store a

  - compute a map mapping line number to generated code for that line
  - fix up the targets of goto's (in the first version, don't bother about trying to use short jumps; just assume all jumps will be long)

Don't think that's cheating; it gives you around a tenfold speed up over a basic interpreter, and back then, people sold compilers doing the above.

If you want advanced functions such as sin, do not hesitate to call into an external library. Those compilers from the '80s weren't afraid to call into ROM code, either.

Going from source to binary on your own code is incredibly satisfying and incredibly enlightening. It thoroughly drives out any "magic" in your mental model of computation.

I agree wholeheartedly use LLVM (or something like it) for anything real. tens or hundreds of thousands of hours, by really smart people, gives you optimizations a lone wolf can never duplicate.

The project seems reasonably popular, for reasons that I don't understand, but it is very simple:

https://github.com/skx/simple.vm

I got about half way there with https://github.com/arlaneenalra/insomniac and have been stuck looking for time to get back to it.

https://gist.github.com/r-lyeh/0af42b2788bb75219061 http://scara.com/~schirmer/o/pcodevm/ Here's another ref: http://homepages.cwi.nl/~steven/pascal/book/pascalimplementa...

But really, all you need is an understanding of the ISA (i.e. the instruction set and the machine it runs on), and have a file format in mind for a middle layer and you can build a runtime. (Basically P-code one form of ISA that's supposed to be portable.) That's kind of what insomniac with a custom isa does:

ISA: https://github.com/arlaneenalra/insomniac/blob/master/insomn... ( a little FORTH happy ...)

Assembler Core: https://github.com/arlaneenalra/insomniac/tree/master/src/li...

VM eval loop: https://github.com/arlaneenalra/insomniac/blob/master/src/li...

and Instructions: https://github.com/arlaneenalra/insomniac/tree/master/src/li...

https://github.com/arlaneenalra/insomniac/blob/master/src/li...

It helps to build the assembler and vm backend first so you have a pipeline in play that you can use to add in ops as you discover they are needed.

(keep in mind all my code is toy stuff..)

I recommend you look at Oberon. I've avoided the Wirth family of languages my whole life, but have been messing with Oberon off and on since winter, because it's interesting from a security standpoint. (It was supposed to be my fun Advent hacking project, but work changes and living changes—i.e., moving—caused interference.) Project Oberon is interesting because it involves a language, a system, and a machine, from the ground up, all created from scratch.[1]

Often, when trying to dive deep on some concept, the available literature can get you rolling with a toy (e.g., compilers), but it helps you reach only a facile understanding, and punts on everything around it. You'll be aware of this; I'm pretty sure it's what you're referring to in your comment above. That's mostly avoided with Oberon, because it's a full-fledged toolchain for quasi-real-world use—at least it was in production use at ETH Zurich.

There are some gotchas with Oberon, and it mostly comes down to a lot of vague, hypey comments written by people who haven't dived deep, and don't have the level of understanding that their comments suggest. There are numerous examples. I could write those up, but here's one: "It was all done without resorting to assembly anywhere." Then you go look into it, and that's because there's no assembler, and it's inline snippets of hex-encoded machine code and other binary blobs instead.

The second big gotcha is that Wirth & Co have produced volumes of (what looks like high-quality) literature, but a bunch of it is either out of date, only superficially helpful, poorly written, or contains errors. For example, "Oberon" refers to so many things—including systems and languages that Wirth had nothing to do with and probably should have never been allowed to bear the name—that it makes jwz's old Java rant[2] seem quaint. (Try starting out at the Wikipedia page and making sense of Oberon's evolution or mapping out the family tree, then try referring to primary and secondary sources directly that might clear things up. Good luck.)

I began with a fresh notebook for taking notes and keeping track of errata in the published stuff. I quit keeping track of errata after two days and several chapters, because it was too much. If you're interested, I highly recommend just running a system image from Peter De Wachter's Norebo[3] and using his emulator for Wirth's RISC machine[4]. Familiarize yourself with the basics of how to use Oberon-the-system by playing with it for an hour or so, crack open the source and just study it directly. Cross reference Wirth's publications if you want (they're all online), but assume that they're lying about something. I can also share my notes. Stay away from the mailing list, it's populated by USENET-style cranks, and it isn't really an essential component of Oberon development. There's not really a community—Wirth pretty much does his own thing, never posts there, and just does a source dump through his personal website.

Having said all that, studying Oberon won't impart all the knowledge you're looking for. It's in this weird place where it's more than a toy, but it really doesn't directly resemble any of the real-world systems that you're actually interested in. (Which most likely means UNIX; let's just be honest.) But it's probably the kind of stepping stone you need.

So the best resources on ELF I know of are the articles written by Eric Youngdale for Linux Journal[5][6], from back in the 90s when vendors were adopting ELF for the first time and he wrote the Linux implementation. I believe this to be the highest quality treatment of the subject that exists (at least as of a few years ago when I was interested in studying this kind of thing).

Hope it helps.

1. https://issuu.com/xcelljournal/docs/xcell_journal_issue_91/3...

2. https://www.jwz.org/doc/java.html

3. https://github.com/pdewacht/project-norebo

4. https://github.com/pdewacht/oberon-risc-emu

5. http://www.linuxjournal.com/article/1059

6. http://www.linuxjournal.com/article/1060

EDIT: I forgot the P-code tie-in! P-code is tangentially related to Oberon because it was developed to port/run (a dialect of) Pascal, one of Oberon's predecessors and Wirth's main claim to fame. Here's a sort-of P-code interpreter for Oberon—it actually runs a (fairly capable) subset of the RISC ISA that Oberon proper targets:

https://www.inf.ethz.ch/personal/wirth/CompilerConstruction/...

(Yes, that's the entire implementation. You'll need a compiler for it though. That can be found in the parent directory. To see what a more "fortified" implementation would look like, and implemented in C, look at Peter De Wachter's emulator, already mentioned above.)

http://linker.iecc.com/

Edit: not that they're conventionally called "architectures" or that COM has any structure to it.

https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/

http://c9x.me/compile/

Note: You could both target and learn from QBE potentially.

ELF:

http://www.cirosantilli.com/elf-hello-world/

My experimental stuff is here: https://github.com/djc/runa. The compiler is written in Python, and shouldn't be that hard to understand. I'm also happy to answer any questions about it here.

  {
   "key"
   {
    "key" "value"
    "morekeys"
     {
     "key2" "value2"
     }
    }
   }

A clause consists of a '{', one or more key-value pairs, and a '}'.

A key-value pair consists of a string and a value.

A value is either a string or a clause.

Now turn each definition into a function.

Here's a nice-looking article from Googling for "writing a recursive descent parser": http://weblog.jamisbuck.org/2015/7/30/writing-a-simple-recur...

But I think I'd agree that writing a recursive descent parser from scratch is probably the best way to learn about parsing; at least for a simple grammar.

BTW, fun fact: it turns out that BNF was invented by an Indian linguist called Pāṇini about 2500 years ago, in order to parse Sanskrit.

https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini

http://timelessname.com/elfbin/

Cheat a lot. They point out some disassembly for you. ".ELF" is clearly some kind of magic string to confirm it's an elf file. "A4 00 00 00" looks like a 4-byte little endian integer (164) or perhaps an offset (0x000000A4 happens to be exactly where all the strings start), "34 00 20 00" might be a pair of shorts... 0x34 = 52 = "Start of program headers" among other matches - it probably corresponds to one of these fields! Try mutating the file and re-running readelf to see what fields change, or if the program still runs.

Just a hex editor and a way to correlate the raw bytes of the disassembly to where the occur in the file can get you surprisingly far. While there will be "dead" data that you can't determine the nature of, documentation can help fill in the holes once you start getting a hold on the "important" bits that actually do stuff (mostly make your program un-runable, I assume.)

IMHO you need to decide on what part of the compiler you want to focus on. You mentioned you already know how to write a lexer and parser. So maybe you should start with an IR like WebAssembly you could compile. Maybe you could even reuse your lexer/parser from your interpreter.

Compiling can be as simple as writing an interpreter, you "just" have to replace some code in the interpreter with `printf`s, that dump e.g. LLVM IR or Assembly. Then use LLVM or any assembler to get a binary. Even GCC basically works that way, gcc just dumps an assembly file and then passes it to assembler and linker. So GCC doesn't really emit ELF or Mach-O either, so don't let that stop you. That doesn't mean you don't have a "full" compiler.

If you don't know assembly use tools like gcc.godbolt.org to see what code gcc generates. The most important thing: Think what code to generate for each feature of your language or IR. If you have figured that out all the rest will be trivial. For example: What code to generate for `if`? So don't try to compile a language with many fancy features at first and please don't try to generate fast code. You want a translation that works in every case, although it might be somewhat inefficient compared to `gcc -O3`. Your first program to compile could be something like `int main() {}`. If you can compile and execute this program, you can start to add features.

This are the restrictions I would make at the beginning: * use a statically typed language, it is easier to generate (faster) code for that * start with global variables, add local variables later * support if, while and then functions (in this order) * only support few datatypes: int, int-array/pointer and string literals for printing.

This should be enough to run the benchmarks binarytrees and fannkuch from The Computer Language Benchmark Game. You will already beat many dynamically typed and interpreted languages for those.

Don't try to generate fast code at first, spill everything onto the stack so you don't have to care about register allocation. Even the V8 full-codegen jit works this way, so you don't have to be ashamed of it ;)

If you don't care about ELF, linking and stuff you could also avoid this by writing a JIT-Compiler: Just emit code into some buffer and then directly start to execute. Although I have to admit that a JIT can introduce some challenges of its own.

Ah and don't forget to write tests. Write a lot of tests from the beginning. Testing a compiler is pretty simple and is is also easy pretty easy to introduce subtle bugs. You will save a lot of time.

I once found a blog post with an example of defining a grammar for a small language and then building an interpreter (in python i think) for it. It was really great, but I lost the link and can't seem to find it again.

The same goes for OS'es - a simple but "end to end" walkthrough would be awesome.

Anyway, cheers!

Maybe this one? Python: Writing a Compiler and Interpreter in 160 lines of code

http://www.jroller.com/languages/entry/python_writing_a_comp...

http://lisperator.net/pltut/

> You probably have to be one of those genius guys ...

Used in the plural, 'guys' usually just means 'people'/'folks' - "alright guys, shall we get going?" - Mac Dictionary agrees.

Happy people don't go around looking to be insulted.

However, I feel the source and target language are too similar. Won't this discourage people? The result code looks like it could have been done in a simpler way, without all the compiler voodoo, by just moving around some parentheses.

Also, the implementation seems to make quite heavy use of external JS libraries. Maybe it is just me, but I'd like to add one NoScript exception for your site, and be done with it, rather than adding exceptions for so many different CDNs.

The klipse plugin indeed loads a couple of external scripts - mostly from my github pages domain: viebel.github.io

https://puu.sh/tVQAL/ec7bd4a05c.png

Apart from that however, I'm thoroughly enjoying this tutorial! It's remarkably similar to a tokenizer & parser I built when I was experimenting with a language that had no syntax, but was simply an AST that could be easily represented as Haskell/Python in the IDE of your choice. Really love how simplistic your code is though, mine just ended up being a mess of callbacks!

break -> breaks

> There a three kinds

a -> are

> starts with a " and end with a "

end -> ends

> couple of tokenizer for a

tokenizer -> tokenizers

> a generic function that tokenize a single

tokenize -> tokenizes

> by means or regular expressions

or -> of