Noen gang lurt på hvordan kalkulatoren tar teksten du putter inn og regner ut svaret?
Nei, sier du?
awkward silence
Kremt. Vel, uansett, svaret er at det begynner med en parser. Oppgaven til en parser er å ta input tekst og transformere det til noe med struktur. Dette er et helt fagfelt i seg selv, men jeg tenkte det kunne være artig å vise et kjapt eksempel på hvordan man kan gjøre det. Selv har jeg fått bruk for denne teknikken forbausende mange ganger i jobben, og det har vært noen av de artigste programmene å skrive.
Det vi skal lage her er en “recursive descent parser”, som er en enkel men kraftig teknikk. Mange programmeringsspråk har en slik en i kompilatoren, mye fordi den er enkel å skrive for hånd, og fordi man kan lage gode feilmeldinger.
Lexer
Ofte lønner det seg å splitte parsing i to steg, lexing og parsing. Lexing handler bare om å gjøre tekst om til en liste med symboler. Disse symbolene forenkler mye av jobben senere. Det går også helt fint å gjøre alt i en smell.
Lexeren vår ser slik ut i javascript:
function lex(str) {
const symbols = []
const addSymbol = (symbol, length) => {
symbols.push(symbol)
str = str.slice(length)
}
while(str.length > 0){
if(str[0] === '+') addSymbol({ type: 'plus' }, 1)
else if(str[0] === '-') addSymbol({ type: 'minus' }, 1)
else if(str[0] === '*') addSymbol({ type: 'multiply' }, 1)
else if(str[0] === '/') addSymbol({ type: 'divide' }, 1)
else if(str[0] === '(') addSymbol({ type: 'lparen'}, 1)
else if(str[0] === ')') addSymbol({ type: 'rparen'}, 1)
else if((matches = str.match(/^\d+/))) addSymbol({ type: 'number', value: Number(matches[0]) }, matches[0].length)
else if((matches = str.match(/^\s+/))) str = str.slice(matches[0].length)
else throw new Error('Unexpected input at ' + str.slice(0, 5))
}
addSymbol({ type: 'end' }, 1)
return symbols
}
Denne går gjennom stringen og finner de vanlige symbolene i et regnestykke. Den kaster også vekk all whitespace sånn at vi kan glemme det fra nå av.
Eksempel:
lex('2 + (2 * 4) + 2/4')
/*
[
{ type: 'number', value: 2 },
{ type: 'plus' },
{ type: 'lparen' },
{ type: 'number', value: 2 },
{ type: 'multiply' },
{ type: 'number', value: 4 },
{ type: 'rparen' },
{ type: 'plus' },
{ type: 'number', value: 2 },
{ type: 'divide' },
{ type: 'number', value: 4 },
{ type: 'end' }
]
*/
Grammatikk
Før vi begynner på selve parseren er det ekstremt kjekt å definere grammatikken for “språket” vårt. Når vi lager parseren kan vi nesten bruke grammatikken som pseudokode, og da blir det kanskje litt lettere å forstå konseptet også.
Slik ser grammatikken ut:
* S -> expr // S = start
* expr -> term '+' expr | term '-' expr | term
* term -> factor '*' term | factor '/' term | factor
* factor -> (expr) | NUMBER | '-' factor | '+' factor
* NUMBER -> /\d+/
Man leser dette som en liste med “regler”. Høyresiden av pila er regelen for hvordan venstresida kan bygges. Så vi begynner hele sulamitten med en “expression”. En expression kan igjen bestå av noe med + og - mellom, eller bare noe enkeltstående uten + og - (feks et enkelt tall). Tilsvarende for * og /. Etterhvert kommer vi ned til en factor som igjen kan bestå av en expression inni parentes, osv. Helt i bunn har vi NUMBER som er skrevet med store bokstaver for å indikere at den ikke har noen flere nøstinger (en “terminal” som det heter på engelsk).
Siden expr går igjen rekursivt under expr i seg selv vil man kunne ha så mange plusser og minuser etter hverandre som man vil. Men merk at når vi skal oversette denne regelen til kode er det viktig at vi prøver å finne “term” før vi prøver å finne “expr”. Ellers havner vi i en uendelig loop.
Parser
For å lage parseren kan vi nærmest oversette grammatikken direkte til kode. Vi begynner med expr:
function expr(symbols) {
const left = term(symbols)
const symbol = symbols.shift()
if (symbol.type === 'plus') return left + expr(symbols)
if (symbol.type === 'minus') return left - expr(symbols)
symbols.unshift(symbol)
return left
}
Altså, først finner vi resultatet av “term” (som vi straks skal definere), deretter sjekker vi om neste symbol er + eller -, og avhengig av hva den er kan vi enten legge til eller trekke fra høyra sida, som også er en expression.
Legg merke til at vi muterer symbols lista direkte. Det er bare så vi skal slippe å måtte holde styr på hvor i lista vi er hen til enhver tid. Ellers hadde disse eksemplene blitt litt for lange.
Legg også merke til at hvis vi ikke finner noen + eller - så putter vi symbolet tilbake i starten av lista. Dette er for å tilfredstille den siste regelen i grammatikken, som sier at vi ikke nødvendigvis har noen + eller - etter første term.
Her er koden for term og factor:
function term(symbols) {
const left = factor(symbols)
const symbol = symbols.shift()
if (symbol.type === 'multiply') return left * term(symbols)
if (symbol.type === 'divide') return left / term(symbols)
symbols.unshift(symbol)
return left
}
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 symbol.value
if (symbol.type === 'plus') return factor(symbols)
if (symbol.type === 'minus') return factor(symbols) * -1
throw new Error('Unexpected symbol ' + symbol.type)
}
Term er omtrent helt lik expr, og det er kanskje ikke så rart siden grammatikken er omtrent helt lik for disse. Factor har litt flere komponenter, hovedsaklig for å håndtere parentes. Legg merke til hvor lett det er å finne ut om parentesene er balansert.
Alt vi trenger nå er funksjonen som sparker det hele igang:
function parse(symbols) {
const result = expr(symbols)
if(symbols[0].type !== 'end'){
throw new Error('Expected end of input, but got ' + symbols[0].type)
}
return result
}
Denne gjør ikke stort, den bare sjekker at vi faktisk har brukt alle symbolene. Man får typisk feil her dersom man glemmer å lukke en parentes.
Her er et eksempel på bruk:
const result = parse(lex('2 + (2 * 4) + 2/4'))
console.log(result) // = 10.5
Og that’s it! Nå kan du lage din egen parser. Neste skritt blir å legge inn støtte for alle de andre operatorene som finnes, egne funksjoner, og bra feilmeldinger.
Takk for i…hold up! Vi har jo omtrent ikke testa det greiene her. Funker det egentlig?
Hva med denne:
2 - 2 - 2 // = 2 (feil)
Eller denne:
2 * 2 / 2 * 2 // = 1 (feil)
Og hva hvis vi stapper inn noen parenteser:
((2 * 2) / 2) * 2 // = 4 (riktig)
Her er det noe gærent. Vi får legge til en bug i jira-boardet og ta den opp ved neste sprint.
Du har god luktesans i hvert fall 