28 ms·

Show HN: An assembler for the LC-3 fictitious computer

cellularmitosis 6y ago
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 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-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/d8d4034c82b0ef817913a01138b115bf https://gist.github.com/cellularmitosis/d8d4034c82b0ef817913... or my lang-related list of links: https://gist.github.com/cellularmitosis/1f55f9679f064bcff02905acb44ca510 https://gist.github.com/cellularmitosis/1f55f9679f064bcff029... Happy hacking!
- carapace 6y ago
  You might enjoy http://pythonwise.blogspot.com/2012/06/python-based-assembler.html http://pythonwise.blogspot.com/2012/06/python-based-assemble... https://raw.githubusercontent.com/tebeka/pythonwise/master/assembler.pdf https://raw.githubusercontent.com/tebeka/pythonwise/master/a...
  - bogomipz 6y ago
    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.
    - carapace 6y ago
      Yeah, it moved to the second link. Cheers
      - bogomipz 6y ago
        I see. Is there any chance that the talk you gave that goes along with the slides is also available on line?
        carapace 6y ago
        This isn't mine. I don't know if the talk is available.
  - cellularmitosis 6y ago
    Very cool idea!!! Thanks for sharing this :)
    - carapace 6y ago
      Cheers
- bogomipz 6y ago
carldaddy 6y ago
The LC-3 was part of my computer architecture course in my CS program over a decade ago. Glad to see it’s still being used.
- jamilbk 6y ago
  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. Happy to see LC-3 is still being used.
- kevinmhickey 6y ago
  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".
ajxs 6y ago
Awesome work! Targetting the LC-3 is a great idea. https://github.com/ajxs/ajxs-elf-as 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.
- cellularmitosis 6y ago
  Oh awesome! Targeting something real like MIPS was going to be my next step!
  - ajxs 6y ago
    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.
    - cellularmitosis 6y ago
      Great idea!
lc3sim 6y ago
Lol, nice. I worked on littlecomputer3.com. I look forward to playing with this!
- cellularmitosis 6y ago
  Oh this is great! I had trouble with the github button, but "view source" revealed it :) https://github.com/0x213F/littlecomputer3 https://github.com/0x213F/littlecomputer3
  - lc3sim 6y ago
    Def. an unfinished project. The killer feature was to step forwards and backwards through executing the code. I did this back when I was going through ECE 385 and had frontend knowledge but no backend.
elamje 6y ago
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.

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 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-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/d8d4034c82b0ef817913a01138b115bf https://gist.github.com/cellularmitosis/d8d4034c82b0ef817913... or my lang-related list of links: https://gist.github.com/cellularmitosis/1f55f9679f064bcff02905acb44ca510 https://gist.github.com/cellularmitosis/1f55f9679f064bcff029... Happy hacking!

carapace 6y ago
You might enjoy http://pythonwise.blogspot.com/2012/06/python-based-assembler.html http://pythonwise.blogspot.com/2012/06/python-based-assemble... https://raw.githubusercontent.com/tebeka/pythonwise/master/assembler.pdf https://raw.githubusercontent.com/tebeka/pythonwise/master/a...
- bogomipz 6y ago
  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.
  - carapace 6y ago
    Yeah, it moved to the second link. Cheers
    - bogomipz 6y ago
      I see. Is there any chance that the talk you gave that goes along with the slides is also available on line?
      - carapace 6y ago
        This isn't mine. I don't know if the talk is available.
- cellularmitosis 6y ago
  Very cool idea!!! Thanks for sharing this :)
  - carapace 6y ago
    Cheers
bogomipz 6y ago

carldaddy 6y ago

The LC-3 was part of my computer architecture course in my CS program over a decade ago. Glad to see it’s still being used.

jamilbk 6y ago
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. Happy to see LC-3 is still being used.
kevinmhickey 6y ago
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".

ajxs 6y ago

Awesome work! Targetting the LC-3 is a great idea. https://github.com/ajxs/ajxs-elf-as 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.

cellularmitosis 6y ago
Oh awesome! Targeting something real like MIPS was going to be my next step!
- ajxs 6y ago
  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.
  - cellularmitosis 6y ago
    Great idea!

lc3sim 6y ago

Lol, nice. I worked on littlecomputer3.com. I look forward to playing with this!

cellularmitosis 6y ago
Oh this is great! I had trouble with the github button, but "view source" revealed it :) https://github.com/0x213F/littlecomputer3 https://github.com/0x213F/littlecomputer3
- lc3sim 6y ago
  Def. an unfinished project. The killer feature was to step forwards and backwards through executing the code. I did this back when I was going through ECE 385 and had frontend knowledge but no backend.

elamje 6y ago

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.