Creating an assembler for a custom CPU

Explainer for how Mrav CPU assembler was created. Shortest path towards a small, working assembler for a custom ISA.

In this post, we'll explore how the assembler for a custom CPU platform, Mrav CPU, was created. Visit the project page for more blog posts and guides about Mrav and its implementation.

Table of contents

Open Table of contents

The challenge

The Mrav ISA has only 16 instructions, with relatively little structural variation. This means there are just a few different instruction formats - some take three registers as parameters, while others take one register and one immediate value, for example.

The process is straightforward: parse the instructions and their parameters, then process any labels or symbol assignments. Afterward, it's easy to generate the relevant machine code, link symbols, and so forth.

Choosing the technology

While many solutions exist, I aimed for the most lightweight approach possible.

A key goal for all Mrav-related software was high portability. For instance, I wanted the assembler to run effortlessly on any major operating system and also be embeddable within a web browser. This would allow users to easily experiment with Mrav without the overhead of cloning the repository, building, and so forth.

JavaScript was a natural choice and indeed the first language Mrav was prototyped in. However, recalling the first post about Mrav implementation, another objective was maximum automation for the entire toolchain. In my view, Bazel is one of the best tools for this, but its JavaScript support doesn't seem as robust as its support for languages like Go.

Let's briefly review some of the approaches attempted for the Mrav software before I detail the final choice.

JavaScript and Chevrotain

I considered making the entire project a JavaScript monorepo, which led me to explore easy parsing solutions within JavaScript. However, I was hesitant to deal with code generation tools in this workflow, primarily because I'm not highly skilled with JavaScript toolchains to make that work effectively. Consequently, I sought a framework that would allow me to define parsing rules via an API, rather than relying on a configuration file to generate a parser.

I ended up prototyping with Chevrotain, and the coding experience was quite smooth and easy to use.

However, as I mentioned, my familiarity with JavaScript toolchains is limited, and I found the documentation for JavaScript in Bazel less straightforward compared to other languages, which led me to pivot.

Go

Go was my next and ultimate choice. It enables building relatively lightweight, self-sufficient binaries for virtually any system, with easy cross-compilation. This includes the browser context, where Go can compile to WASM.

Participle

Next, I experimented with the Participle library for Go. In many ways, it's similar to Chevrotain in JavaScript: you define structures through an API, and the underlying mechanisms handle the parsing.

However, despite my decision to create my own assembler, I am by no means a parsing expert. I took a compiler construction course years ago, but I've effectively forgotten most of the parser theory.

After spending a few hours with this library, I found it quite challenging to debug, so I abandoned the approach.

Go standard library

I ended up using no third-party framework at all! Everything required for my super lightweight assembler is already available in the Go standard library, and it all cross-compiles trivially to other platforms without issues. I'll describe how this works in the sections below, but for now, the tech stack is simply plain Go and nothing else.

Constructing the assembler

The Mrav assembly language consists of very few elements: instruction keywords, register IDs, immediate values, and a couple of symbols like colons for labels and equality signs (=) for symbol assignments.

It then occurred to me that this is so simple that I don't really need anything fancy for lexical analysis; this is where the Go standard library comes in.

Lexing

Go comes with "batteries included," and its tokenizer can be found in its standard library under text/scanner. While I'm no parsing expert, I believe they refer to it as a tokenizer, but it functions more like a lexer since it not only chunks the text but also provides descriptions (e.g., 'this is an identifier' or 'this is an int constant').

Mrav assembly isn't particularly complex; elements like register IDs (e.g., r1 or R1) are valid Go identifiers, and integer constants are identical. Colons and assignments are also used in Go.

Considering all this, we essentially get our lexer for Mrav for free.

Parsing

The real parsing challenge lies in making sense of different tokens, and I knew I could easily get sidetracked here. However, as I considered Mrav as a simple platform, I realized there were only a few key aspects to focus on:

  • Processing the assembly code line by line.
  • Identifying a limited number of variations for what a line could look like.

A line could be one of several things, such as a label line (foo:), a label with an instruction (foo: add r1 r2 r3), and so on. I immediately thought of algebraic data types (ADT), but these are not easily expressed in Go. ADTs are more characteristic of functional programming languages, and I wondered if any of those could integrate well with Go. I found Oden, but it is unfortunately no longer developed. Similarly, I learned about PureScript and its ability to transpile to Go, but I didn't have much success with it.

Again, I realized I was overcomplicating things, so I opted for a trivial approach in Go. I found a library that supports a somewhat primitive view of an ADT and used it to define a few variations for what each line in assembly could look like:

type Line struct {
	Number  int
	Content AssemblyLine
}

type AssemblyLine = mo.Either5[BlankLine, AssignmentLine, LabelLine, InstructionLine, LabeledInstructionLine]

Comments are obtained for free here via Go lexing since it supports Go comments. I was OK with keeping the same comment format in Mrav.

At this point, it's trivial to parse out each line type with a few if/elses. An excerpt is below:

if len(tokens) == 0 {
	return lineMaker(AssemblyBlankLine()), nil
}

if len(tokens) == 1 {
	return Line{}, fmt.Errorf("incomplete and possibly malformed line %d", lineNum)
}

if tokens[0].tokenType != scanner.Ident {
	return Line{}, fmt.Errorf("expected an identifier at line %d, column %d", lineNum, tokens[0].position.Column)
}

if tokens[1].text == "=" {
	if len(tokens) != 3 {
		return Line{}, fmt.Errorf("line %d looks like assignment, but expected it in 'symbol = value' format, got excess content on the line", lineNum)
	}

	if tokens[2].tokenType != scanner.Int {
		return Line{}, fmt.Errorf("line %d column %d, expected an int value", lineNum, tokens[2].position.Column)
	}

	return lineMaker(AssemblyAssignmentLine(
		Symbol(tokens[0].text),
		HardcodedValue(tokens[2].text),
	)), nil
}
...

Machine code generation

Here's the high level logic that assembles a list of assembly files:

func AssembleModules(modules []string) (*model.MravModule, error) {
	objects := make([]*secondpass.MravObject, 0, len(modules))

	for i, m := range modules {
		parsedModule, err := parsing.ParseModuleString(m)

		if err != nil {
			return nil, fmt.Errorf("unable to parse module %d: %w", i, err)
		}

		firstPassModule, err := firstpass.ModuleFirstPass(parsedModule)

		if err != nil {
			return nil, fmt.Errorf("unable to do the first pass on the module %d: %w", i, err)
		}

		object, err := secondpass.BuildObject(firstPassModule)

		if err != nil {
			return nil, fmt.Errorf("unable to do the second pass on the module %d: %w", i, err)
		}

		objects = append(objects, &object)
	}

	program, err := linker.Link(objects)

	if err != nil {
		return nil, err
	}

	return program, nil
}

The final machine code generation is like this:

humanReadableOutput := func() {
	humanReadable, err := format.HumanReadable(program)

	if err != nil {
		log.Fatalf("Cannot output the machine code: %v", err)
	}

	programOutput := strings.Join(humanReadable, "\n") + "\n"

	if err := os.WriteFile(*outputFile, []byte(programOutput), 0644); err != nil {
		log.Fatalf("Cannot write the human readable output file: %v", err)
	}
}

binaryOutput := func() {
	binaryPayload, err := format.Binary(program)

	if err != nil {
		log.Fatalf("Cannot output the machine code: %v", err)
	}

	if err := os.WriteFile(*outputFile, binaryPayload, 0644); err != nil {
		log.Fatalf("Cannot write the binary output file: %v", err)
	}
}

outputProducers := map[string]func(){
	"human":  humanReadableOutput,
	"binary": binaryOutput,
}

I won't deep-dive into the assembly passes and code generation, as the code is very straightforward and standard. In the first pass, we generate the relevant API structs for different instructions, track program counter offsets, and so on. I will discuss the API structs in more detail in a separate blog post.

The second pass produces object files that may contain unresolved symbols. The final linking process resolves these symbols by determining whether other objects in the assembly define them.

Building now the assembler binaries with Bazel is super easy. Following are the targets for WASM (that can be used in a browser), as well as x86_64. You can build for these targets regardless of the platform you're developing on: Linux, Mac, or something else.

go_binary(
    name = "assembler",
    srcs = [
        "assembler.go",
    ],
    cgo = False,
    pure = "on",
    deps = [
        "//software/asm",
        "//software/format",
    ],
)

go_cross_binary(
    name = "assembler_wasm",
    platform = "//platforms:wasm_js",
    target = ":assembler",
)

go_binary(
    name = "as",
    srcs = [
        "as.go",
    ],
    cgo = False,
    pure = "on",
    deps = [
        "//remote/spew",
        "//software/asm",
        "//software/format",
    ],
)

go_cross_binary(
    name = "as_x86_64",
    platform = "//platforms:x86_64_linux",
    target = ":as",
)

Conclusion

The main takeaway is that for Mrav, simplicity was key. By leveraging Go's standard library for lexing/tokenization and keeping the parsing straightforward with a few if/else statements, it became quite easy to generate machine code from user input.

I would have found it fascinating to combine Go with a functional programming language for parsing purposes; I hear Haskell is particularly concise for such tasks. However, if I had pursued that path, I would likely still be working on Mrav.

I certainly haven't exhausted all options for the most succinct way to parse these elements in Go. If this were a production project, I would investigate alternatives with much more rigor. In this case, my primary goal was simply to experiment.

If you know of a method for creating a similar assembler that meets the following conditions:

  1. Equally portable
  2. Easy to build in a Bazel environment
  3. Requires a comparably small amount of code for parsing implementation
  4. Is more production-ready than the approach described here

then I'd love to hear about it in the comments.

Please consider following on Twitter/X and LinkedIn to stay updated.