Show HN: An assembler for the LC-3 fictitious computer
github.com
github.com
I remember on the first day of class, prof Patt described his philosophy of learning EE: start from the ground up. Many students went in to that class barely able to use Word and came out knowing how a simple computer worked.
Happy to see LC-3 is still being used.
I still vaguely remember that exactly one instruction needed 2 passes through the core pipeline. During decode, we would inject the reserved word into the instruction pipeline to represent the 2nd pass. We were pretty proud of that "innovation".
The assembler is written in Python, and tries to stick to as simple a subset of Python as possible (essentially, just functions and dictionaries with dot syntax sugar). All control flow leaf terminations are explicit (e.g. continue, break).
Idiomatic Python style is not a goal. Rather, the goal is to minimize the amount of syntax knowledge needed to follow the code. The code could be made much shorter with some clever refactoring, but brevity is a non-goal.
This trivial coding style will hopefully make hacking on the code more approachable for others just learning about lexers / parsers / assemblers / compilers.
The assembler is a simple two-pass implementation: create the symbol table (determine the addresses of all labels) in pass 1, then generate the machine code in pass 2. This is described in chapter 8 of the LC-3 book (Introduction to Computing Systems: From Bits and Gates to C and Beyond).
The LC-3 ISA consists of only 15 instructions, making this a simple task. One oddity is that the ISA is word-addressable, not byte-addressable.
The lexer is a simple regex-based implementation, and the parser is simple recursive descent. This approach is described in Gary Bernhardt's "A Compiler From Scratch" https://www.destroyallsoftware.com/screencasts/catalog/a-com...
The lexer and parser output can be dumped (in JSON format) via command-line flags.
Additionally, the assembler also _accepts_ pre-parsed JSON input. This allows one to build a custom assembly syntax front-end and use this assembler as the back-end: all they have to do is generate the appropriate JSON output. Again, hackability is a goal! (How I wish other compilers allowed AST input!)
A good practice project would be a reimplementation in Golang, focusing on speed.
If you enjoyed this, you may also enjoy my trivial lisp interpreter in C series: https://gist.github.com/cellularmitosis/d8d4034c82b0ef817913... or my lang-related list of links: https://gist.github.com/cellularmitosis/1f55f9679f064bcff029...
Happy hacking!
I’d be happy to turn this into a couple of tutorial blog posts. If you removed all of the lexing and parsing code, and chopped the ISA down to just 1 or 2 instructions, it would really highlight how simple the core problem really is!
One technique I’ve used before (and a technique echoed by David Beazley in his compilers course), was to skip the lexer and parser and jump straight to working on something which is handed an already-parsed AST. Let’s you skip right to the interesting part, especially if you are already bored with writing parsers by hand.
Yes that would be great. Please do! I think there would genuine interest in more posts. Please post it here if so. Cheers.
https://github.com/ajxs/ajxs-elf-as
I embarked on a similar project a little while ago ( see above ). I attempted to write an assembler targeting the MIPS ISA, and assembling ELF relocatable object files. It's 95% complete, with the notable exception of implementing proper bi-endianness. That being said, I'm sure there's so many cases in which it would fail to create linkable object files. At any rate, it was an amazing project for me. I learned so much in doing this that has continued to help me as a developer.
Instead of MIPS, it might be a good idea to target RISC-V. It's a more modern RISC ISA which apparently has a few less quirks. I found the MIPS documentation to be great, mind you. There's lots of resources available online about MIPS programming. So there are advantages to targeting MIPS, no doubt. RISC-V is on the cutting edge, however. If you're interested in embedded development, learning RISC-V now will have other advantages.
Our first assignment in that class was a program written in binary with manually addressed jump statements.
I did this back when I was going through ECE 385 and had frontend knowledge but no backend.