Hi HN, I wrote an assembler for the LC-3. This is part of my journey of learning how to write a compiler.
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 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.
Your first link unfortunately appears to be broken. If you click on the link "You can view the presentation I gave on this here." It shows an error message that the repository has been deleted.
Believe it or not, once the lexing and parsing was out of the way, the two-page description of the two-pass process in the book was really all it took: make a list of all of the goto labels, then calculate the address of each.
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.
I thought it seemed familiar! EE 306: Introduction to Computing with prof Yale Patt. Almost 15 years ago now.
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.
Mine too at UIUC almost 20 years ago! We had to design a working CPU for the instruction set in verilog or VHDL, then run a program in the simulator.
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".
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.
It shouldn't be much more work than you've already done, so you should definitely go for it!
Maybe even build multi-target support into your assembler, it shouldn't be too difficult. I implemented the framework for this.
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.
Ha. I’m an alum of Yale Patts 306 course. He’s a character! Happy that the LC-3 is still around. I regularly use the basic knowledge I gained that semester in my understanding of software.
Our first assignment in that class was a program written in binary with manually addressed jump statements.
22 comments
[ 0.20 ms ] story [ 56.1 ms ] threadThe 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!
http://pythonwise.blogspot.com/2012/06/python-based-assemble...
https://raw.githubusercontent.com/tebeka/pythonwise/master/a...
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.
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".
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.
I did this back when I was going through ECE 385 and had frontend knowledge but no backend.
Our first assignment in that class was a program written in binary with manually addressed jump statements.