Nå er det på tide å fikse bug’en fra del 1. Kan ikke leve med sånt på samvittigheten. I tillegg syns jeg vi burde gjøre noe annet enn å bare spytte ut resultatet rett fra parseren. Det er mye mer gøy å regne ut svaret direkte i maskinkode!
Bugfix
I del 1 fikk vi feil svar når vi regnet ut 2 - 2 - 2. Problemet ligger i grammatikken:
* expr -> term '+' expr | term '-' expr | term
Hvis vi bruker dette på eksemplet ovenfor får vi først en term som er 2, etterfulgt av -, og en ny expression. I praksis betyr dette at vi putter parenteser rundt tallene, omtrent slik: 2 - (2 - 2). Riktige parenteser skulle vært slik: (2 - 2) - 2. Dvs, hvis vi har flere minustegn etter hverandre må vi utøve de fra venstre til høyre, ikke fra høyre til venstre.
For å løse problemet må vi unngå at expr nevnes rekursivt i grammatikken. Det kan vi gjøre på følgende måte:
* expr -> term ('+' / '-' term)*
Her sier vi enkelt og greit at en expression er en term etterfulgt av 0 eller flere nye terms med + eller - forran. I koden kan vi da utføre hver operasjon fra venstre til høyre, etterhvert som hver nye term kommer inn. Her er koden:
function expr(symbols) {
const left = term(symbols)
let symbol = symbols.shift()
let result = left
while(['plus', 'minus'].includes(symbol.type)){
if (symbol.type === 'plus') result += term(symbols)
if (symbol.type === 'minus') result -= term(symbols)
symbol = symbols.shift()
}
symbols.unshift(symbol)
return result
}
Basically det samme som vi hadde før, bare at nå har vi byttet ut det rekursivet kallet til expr med en while-loop.
Koden for term hadde det samme problemet, og løses på samme måte:
* term -> factor ('*' / '/' factor)*
function term(symbols) {
const left = factor(symbols)
let symbol = symbols.shift()
let result = left
while(['multiply', 'divide'].includes(symbol.type)){
if (symbol.type === 'multiply') result *= factor(symbols)
if (symbol.type === 'divide') result /= factor(symbols)
symbol = symbols.shift()
}
symbols.unshift(symbol)
return result
}
Resten av koden er helt lik del 1.
Abstract syntax tree
For å komme videre må vi gjøre noe med outputen til parseren. Sånn det står nå regnes svaret ut direkte i parseren. Men hva hvis vi vil regne ut svaret i maskinkode? Det vi trenger er et abstract syntax tree. I stedet for å regne ut svaret direkte lager vi heller en trestruktur som beskriver regnestykket vårt. Denne kan vi igjen bruke til å generere maskinkode for ulike maskiner.
Her er koden, skrevet om til å spytte ut en AST:
function expr(symbols) {
const left = term(symbols)
let symbol = symbols.shift()
let root = left
while(['plus', 'minus'].includes(symbol.type)){
root = {
type: 'expr',
operator: symbol.type,
left: root,
right: term(symbols)
}
symbol = symbols.shift()
}
symbols.unshift(symbol)
return root
}
function term(symbols) {
const left = factor(symbols)
let symbol = symbols.shift()
let root = left
while(['multiply', 'divide'].includes(symbol.type)){
root = {
type: 'term',
operator: symbol.type,
left: root,
right: factor(symbols)
}
symbol = symbols.shift()
}
symbols.unshift(symbol)
return root
}
function factor(symbols) {
const symbol = symbols.shift()
if (symbol.type === 'lparen') {
const result = expr(symbols)
const rparen = symbols.shift()
if (rparen.type !== 'rparen') {
throw new Error('Expected right parens')
}
return result
}
if (symbol.type === 'number') return { type: 'number', value: symbol.value }
if (symbol.type === 'plus') return factor(symbols)
if (symbol.type === 'minus') return { type: 'term', operator: 'multiply', left: { type: 'number', value: -1}, right: factor(symbols) }
throw new Error('Unexpected symbol ' + symbol.type)
}
For eksempelet vårt (2 - 2 - 2) får vi følgende output:
{
type: 'expr',
operator: 'minus',
left: {
type: 'expr',
operator: 'minus',
left: { type: 'number', value: 2 },
right: { type: 'number', value: 2 }
},
right: { type: 'number', value: 2 }
}
Vi har altså et sett med noder. Hver node har en type (‘expr’, ‘term’, ‘number’). Hvis noden er helt i bunn av treet er den en “number” og har bare en “value”. Hvis noden er høyere opp i treet har den typisk en venstre og høyreside med en operator i mellom.
Nå som vi har en AST kan vi bruke denne videre til å gjøre mye artig. Hvis dette var et programmeringsspråk kunne vi gjort optimaliseringer på treet. Vi kunne beskjært treet, kollapset greiner, analysert for å finne feil, mm.
Maskinkode
Ok, her må jeg innrømme at jeg er ganske blank. Det er heller ikke noe poeng å gjøre om et regnestykke til maskinkode når vi allerede er i et programmeringsspråk som kan gi oss svaret direkte. Men whatevs, vi kjører på.
Jeg plukka meg ut en maskin til å kjøre programmet vårt. Det er en 8 bits emulator som kan testes her: https://schweigi.github.io/assembler-simulator/
Den har noen flerbruksregistre A, B, C, D, som kan brukes til å lagre verdier. Den har også en stack som du kan pushe og poppe fra. Den skal vi utnytte til det fulle. Et par skjær i sjøen er at den ikke støtter negative tall eller desimaltall osv (eller jeg har i hvert fall ikke funnet ut av det enda). Så vi får holde oss til veldig enkle regnestykker 
Her er koden:
function codegen(node) {
if(node.type === 'expr'){
return genExpr(node)
} else if (node.type === 'number') {
return genNumber(node)
} else if (node.type === 'term') {
return genTerm(node)
}
}
function genExpr(node) {
if (node.operator === 'plus') {
return [
codegen(node.left),
codegen(node.right),
`pop B`,
`pop A`,
`add A, B`,
`push A`,
].join('\n')
} else if (node.operator === 'minus') {
return [
codegen(node.left),
codegen(node.right),
`pop B`,
`pop A`,
`sub A, B`,
`push A`,
].join('\n')
}
}
function genTerm(node) {
if (node.operator === 'multiply') {
return [
codegen(node.left),
codegen(node.right),
`pop B`,
`pop A`,
`mul B`,
`push A`,
].join('\n')
} else if (node.operator === 'divide') {
return [
codegen(node.left),
codegen(node.right),
`pop B`,
`pop A`,
`div B`,
`push A`,
].join('\n')
}
}
function genNumber(node) {
return `push ${node.value}`
}
Output for 2 + 2 + 2 blir (test her: https://schweigi.github.io/assembler-simulator):
push 2
push 2
pop B
pop A
add A, B
push A
push 2
pop B
pop A
add A, B
push A
Så ideen her er at hvert nivå i syntax-treet vårt dytter resultatet sitt på stacken. Nivået over kan poppe verdien av stacken og putte den i et register.
For eksempel, i en expression genererer man koden for venstre og høyreside, og begge disse pusher resultatet sitt på stacken:
codegen(node.left),
codegen(node.right),
`pop B`,
`pop A`,
`add A, B`,
`push A`,
Man popper begge disse verdiene av stacken i hvert sitt register (A og B). Deretter kan man kjøre ADD-instruksjonen på disse registrene. Resultatet havner i register A, som vi så dytter på stacken igjen.
Oppsummering
Igjen, dette var ganske meningsløst, men kanskje litt artig også. Det var i hvert fall litt artig å generere denne “maskinkoden”, det har jeg aldri prøvd før. I x86 kan man gjøre artimetikk direkte i assembly, så i praksis ville man vel aldri sett den løsninga jeg presenterte her. De fleste kompilatorer ville også optimalisert vekk hele regnestykket og byttet det ut med resultatet. Men prinsippene er i hvert fall de samme. Neste steg nå blir å lage et helt eget programmeringsspråk!