Go 6502 Parsing Expressions

27.11.2024 13:23 default

Handling Simple Expressions

After the previous post, our compiler currently handles single integers, storing them in the A register for later use. Now, let’s try to use them for something simple. One way to look at programs is as a collection of statements and expressions–statements do something, while expressions are something–certainly an oversimplification, but useful here. And in fact, we already handle expressions, our single digit integers are expressions, single digit expressions. We’ll expand that to handle binary expressions, something like 1+2 or 9-7 and we’ll work our way up to more complex expressions like 2*(9-(7*2)).

Binary Expressions

Let’s start handling binary addition and subtraction expressions, <term> +|- <term> where each term is a single digit integer. Right now, our compiler reads an expression with:

func Expression() {
	EmitLn("LDA #" + string(GetNum()))
}

Remember, LDA LoaDs the value into the A register, or accumulator. The 6502 also has opcodes for dealing with addition and subtraction. For addition we have ADC(Add with carry) and SBC(Subtract with carry), they both act on the value in the accumulator with some value from memory. So we’ll need to store one of the values in memory. Currently, we’re sticking the first term into the A register, luckily, the way to save something to memory with the 6502 is to first put it in the one of the registers, like the A register! So we’ll tuck that into memory and read our operation and next term.

Let’s rename the current Expression() method to Term() and create a new Expression() that handles addition.

func Term() {
	EmitLn("LDA #" + string(GetNum()))
}

func Expression() {
	Term()
	if Look == '+' {
		Add()
	}
}

func Add() {
	Match('+')
	// Move the previous term to the X register
	EmitLn("STA $0200")
	// Get the next term
	Term()
	EmitLn("CLC")
	EmitLn("ADC $0200")
}

Our new Expression() first expects a <term> and then checks the next character, if it is a +, we move over to start processing the <term>+<term> case. As mentioned, we need to store the <term> we just read in memory, we picked some spare memory address 0x0200 to store the first term, which we do with the STA (STore A) instruction. Then we can load the next term into the A register and then add them together. The 6502’s ADC opcode adds “with carry”, A + M + C the Accumulator, the byte from memory, and the carry bit. For single-byte addition, we always want to start with the carry empty. With the Carry flag CLeared with CLC, ADC just computes A + M and the sum is then left in the A register.

Now we can handle addition!

echo 4+2 | go run . | tee a.asm
        LDA #4
        STA $0200
        LDA #2
        CLC
        ADC $0200

If we assemble and run that, we should see a value of 6 in the A register.

Subtraction should be almost as easy, here is the code for handling subtraction:

func Sub() {
	Match('-')
	// Move the previous term to memory
	EmitLn("STA $0200")
	// Get the next term
	Term()
	EmitLn("SEC")
	EmitLn("SBC $0200")
}

We have almost the same shape for subraction, we need to move the original term to memory, clear the carry, and subtract. SBC (SuBtract with Carry) works similar to ADC, but the carry is now for borrowing, the CPU does A - M - (1-C). That looks a bit strange, but essentially the carry bit is used in the opposite direction, where the carry flag being set means there was no borrow. Again, we just need to know to SEC (SEt Carry) to before subtraction.

We need to go update Expression() to handle our new Sub() case:

func Expression() {
	Term()
	if Look == '+' {
		Add()
	} else if Look == '-' {
        Sub()
    }
}

echo 4-2 | go run . | tee a.asm
        LDA #4
        STA $0200
        LDA #2
        SEC
        SBC $0200

This isn’t actually correct though, instead of 4-2 that computes 2-4! When we call SBC $0200 we have stored 4 at $0200 and have 2 in the A register. So we get A(2) - M(4) - (0). We have two choices, we can either use another memory address to shuffle the values around, or, since we always get the negative of the correct answer, we can negate the value. Lets do the latter:

func Sub() {
	Match('-')
	// Get the next term
	Term()
	// Subtract
	EmitLn("SEC")
	EmitLn("SBC $0200")
	// Negate
	EmitLn("EOR #$FF")
	EmitLn("CLC")
	EmitLn("ADC #$01")
}

For two’s complement, we can perform negation by by first flipping the bits in A with EOR (Exclusive OR), then adding one(remembering to CLC first!).

This isn’t super efficient. We could have read in the entire 4-2, realized we wanted to subtract 2 from 4 and loaded the 2 into memory first put the 4 in the accumulator and do the subraction, but that would make the way compiler more complicated.

Modern compilers have many optimizations to fix situations like this, but they usually come in a later step. Without getting to deep into theory, modern compilers usually read the stream of data like we are, and create an AST (abstract syntax tree) and do optimization passes that pattern match things like the above, noticing that we could store the second value first and swap them. Then produce an IR(intermediate representation) and do even more pattern matching on that to further optimize!

We don’t need to get into all that, because our goal is not to make an efficient compiler, but to learn about compilers and this code will indeed produce the correct result.

We can now process any single digit integer, or addition and subtraction of single digit integers, but we can’t string them together like 1+1+1, this would give us the same code as 1+1.

echo 1+1+1 | go run . | tee a.asm
        LDA #1
        STA $0200
        LDA #1
        CLC
        ADC $0200

General Expressions

We want our compiler to handle longer strings of addition and subtraction, we’d like to handle <term> + <term> and <term> + <term> + <term>, and so on. In BNF(Backus-Naur Form), we’d write it as <expression> ::= <term> + <expression> indicating the recursive nature of adding more expressions. Even further, we could define:

<expression> ::= <term> [ <addop> <expression> ]
<addop> ::= "+" | "-"
<term> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

This means an expression starts with a term, and then zero or more groups of addop and expression, where an addop is just + or - and a term is a dingle digit integer. This definition is recursive, an expression and contain an expression and so on, which covers any combination of addition and subtraction and single digits:

1
4+3
5-2+3
...

The cool thing is, we can cover all of those cases just by repeating what we’ve got so far with a for loop

func Expression() {
	Term()
	for Look == '+' || Look == '-' {
		// Store the previous value
		EmitLn("STA $0200")
		switch Look {
		case '+':
			Add()
		case '-':
			Sub()
		}
	}
}

This small change to Expression allows us to perform any amount of addition and subtraction! We read the first term to A, then as long as we see an addop, we do that addop, which leaves the value in A, which we then store at $0200 again so we can carry onto the next addop, and so on until we reach the end.

echo 5-2+3-9+5+4 | go run . | tee a.asm
        LDA #5
        STA $0200
        LDA #2
        SEC
        SBC $0200
        EOR #$FF
        CLC
        ADC #$01
        STA $0200
        LDA #3
        CLC
        ADC $0200
        STA $0200
        LDA #9
        SEC
        SBC $0200
        EOR #$FF
        CLC
        ADC #$01
        STA $0200
        LDA #5
        CLC
        ADC $0200
        STA $0200
        LDA #4
        CLC
        ADC $0200

Run this, and you should find 6 in the A register.

This is pretty amazing considering how simple the compiler is. But this only works because with addition and subtraction, we can work from left to right–adding or subtracting the next term as soon as we see it. But we want to handle more complex expressions, like (2-(9+3)) which should really add the 9 and 3 first(which will matter more if we get to multiplication).

This concept of needing to store values in increasing memory to pull back out in order is so common it is built into CPUs, the stack. In the 6502, the memory address 0x0100 to 0x01FF are reserved for the stack. The important think to know is that we can push values from the A register onto the stack without really caring which address we’re at, and later we can pull the most recent value back off and into the A register. We’ll update our code to make use of the stack now.

What we’ll do is instead of storing a value directly to memory, we’ll push it onto the stack, then we can read out next value, and if we’re ready to perform an operation, store it and pull the previous one off the stack. This might make more sense one we get going.

Lets change Expression to PHA (PusH Accumulator):

func Expression() {
	Term()
	for Look == '+' || Look == '-' {
		// Save the current value
		EmitLn("PHA")
		switch Look {
		case '+':
			Add()
		case '-':
			Sub()
		}
	}
}

And Add and Sub can now PLA (PulL Accumulator):

func Add() {
	Match('+')
	// Get the next term
	Term()
	// Move it to memory
	EmitLn("STA $0200")
	// Retrieve the previous value
	EmitLn("PLA")
	// Add
	EmitLn("CLC")
	EmitLn("ADC $0200")
}

func Sub() {
	Match('-')
	// Get the next term
	Term()
	// Move it to memory
	EmitLn("STA $0200")
	// Retrieve the previous value
	EmitLn("PLA")
	// Subtract
	EmitLn("SEC")
	EmitLn("SBC $0200")
}

As a bonus, we are actually subtracting in the right order now, so we have removed the negation code from Sub. When we start at Expression, we read a term and push it onto the stack which holds it temporarily. Then we see the - and proceed to read the next term and store it at $0200. Pulling from the stack now puts the first term in the accumulator so that SBC subtracts the second term from the first. There isn’t much benefit of this change since we aren’t doing multiplication yet, so lets add it now!

To expand the BNF for expression we’ve been working on we need to add multiplication, we define a term as being factor, and zero or more groups of mulop and expression, so we get:

<expression> ::= <term> [ <addop> <expression> ]
<addop> ::= "+" | "-"
<term> ::= <factor> [ <mulop> <expression> ]
<mulop> ::= "*" | "/"
<factor> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

There is a nice symmetry between expression and term and it naturally handles operator precedence for situations like 1+2*5 to get 11 instead of the incorrect 15.

The changes are pretty minor, essentially rename our existing term to factor to push single digit reading down a level, then create a new term which is basically a copy of expression iupdated for multiplication.

func Factor() {
	EmitLn("LDA #" + string(GetNum()))
}

func Term() {
	Factor()
	for Look == '*' || Look == '/' {
		// Save the current value
		EmitLn("PHA")
		switch Look {
		case '*':
			Mul()
		case '/':
			Div()
		}
	}
}

func Expression() {
	Term()
	for Look == '+' || Look == '-' {
		// Save the current value
		EmitLn("PHA")
		switch Look {
		case '+':
			Add()
		case '-':
			Sub()
		}
	}
}

Then we need to add our new Mul().

var mulCount int

func Mul() {
	mulCount++
	Match('*')
	// Get the next factor
	Factor()
	// Move it to memory
	EmitLn("STA $0200")
	// Move previous factor to X register
	EmitLn("PLA")
	EmitLn("TAX")
	// Multiply
	EmitLn("LDA #0")
	EmitLn("CLC")
	EmitLn(fmt.Sprintf("mul%d:", mulCount))
	EmitLn("ADC $0200")
	EmitLn("DEX")
	// If X is not zero, used label to loop
	EmitLn(fmt.Sprintf("BNE mul%d", mulCount))
}

This starts off very familiar, we match the operator and read the next factor, move it to memory and pull our old value from the stack. Then we get into the actually multiplication code.

We have no multiplication opcode on the 6502, so we will do repeated addition. We move one value to the X register with TAX (Transfer A to X), clear A(by loading a 0) and then add the value from memory and use DEX (DEcrement X) to decrement the X register. As long as X is not zero, we use BNE (Branch Not Equal) to jump back to the label to loop. We are going to keep track of how many times we multiply, and create a new label for each one to keep them unique. Later, we’ll probably use a mutliplication subroutine, but this seemed easier for now.

The mulCount is used to ensure we get unique labels. For now we aren’t reusing any code here, we emit the full multiplication algorithm for every multiplication we perform, hopefully we can clean that up later.

Division is a much less straight forward algorithm. I’ll just paste it here and not go into detail about what it does. I am using this algorithm on Wikipedia.

var divCount int


func Div() {
	divCount++
	Match('/')
	// Get the next factor
	Factor()
	// Move it to memory
	EmitLn("STA $0200")
	// Move previous factor to A register
	// use $0201 for R, $0202 for Q, and $0203 for i.
	EmitLn("LDA #0") // 
	EmitLn("STA $0201") // Clear R 
	EmitLn("STA $0202") // Clear Q
	EmitLn("LDA #$80")
	EmitLn("STA $0203") // Set i to 0b10000000

	EmitLn(fmt.Sprintf("div%dl1:", divCount))
	// Load N into A
	EmitLn("PLA")
	// Shift R left
	EmitLn("ASL $0201")
	// BIT i and N, does N & i, if not zero, set R[0] = 1
	EmitLn("BIT $0203")
	// If not zero, set R[0] = 1
	EmitLn(fmt.Sprintf("BEQ div%dl2", divCount))
	// Set R[0] = N[i], INC works because we just shifted R left, so R[0] is 0
	EmitLn("INC $0201")

	EmitLn(fmt.Sprintf("div%dl2:", divCount))
	// Push N back on stack for next iteration
	EmitLn("PHA")
	// Load R into A and subtract D
	EmitLn("LDA $0201")
	EmitLn("SEC")
	EmitLn("SBC $0200")
	// Result of R - D is in A, if negative, R < D and we skip this conditional
	EmitLn(fmt.Sprintf("BMI div%dl4", divCount))
	// The result was positive or zero, so R >= D
	// Save result back to R
	EmitLn("STA $0201")
	// Q[i] = 1
	EmitLn("LDA $0202")
	// Ora with i
	EmitLn("ORA $0203")
	EmitLn("STA $0202")

	// Else, R < D, so we need start our next iteration
	EmitLn(fmt.Sprintf("div%dl4:", divCount))
	// Shift i right
	EmitLn("CLC")
	EmitLn("ROR $0203")
	// If i is not zero, loop
	EmitLn(fmt.Sprintf("BNE div%dl1", divCount))
	// Done, clear stack and move Q to A
	EmitLn("PLA")
	EmitLn("LDA $0202")
}

That is quite a beast. The important thing to note is that we follow the same scheme, we load the next factor, perform division and leave the result in the A register. With this we can handle strings of addition, subtraction, multiplication, and division of single-digit integers, properly handling multiplication precendence!

Finally, we’ll add handling of parenthesis and we’ll have accomplished our goal of handling complex math expressions. You may have noticed multiplication and division made our compiler far more complex, but that was operations themselves. If the 6502 had opcodes to MUL and DIV, it would have looked a lot more like addition and subtraction did. Luckily, adding parenthesis just affects the parsing, and not the operations. Parenthesis are used to group the given expression as a single factor, so our parser needs to reflect that, and when checking for a factor, we check to see if we have a parenthesis. If we do, we parse the interior as an expression and move on.

func Factor() {
	if Look == '(' {
		Match('(')
		Expression()
		Match(')')
	} else {
		EmitLn("LDA #" + string(GetNum()))
	}
}

The BNF would look like:

<factor> ::= ( <expression> ) | "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

We either see an opening parenthesis, an expression and a closing parenthesis, or we see a single digit. Our parser is reflecting the same thing.