Lexer - Expression calculator
Tags: go, programming, algorithms
Published: 2021-04-21 20:38:41

Smart calculators are everywhere. You can type the whole expression and it will count with proper priorities and handles parentheses. In this article and serie is described how to do your own smart calculator.

> 🇨🇿 V češtině si lze článek přečíst na [kutac.cz](https://www.kutac.cz/pocitace-a-internety/lexer-1-dil-vlastni-kalkulacky-s-vyrazy)

---

There are many possibilities how to solve this problem. But I will focus on implementation with Lexer, which tokenizes input, and parser, which converts tokens into [Abstract Syntax Tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree).

> :link: The whole code can be found on GitHub in [arxeiss/go-expression-calculator](https://github.com/arxeiss/go-expression-calculator) repository.

# Lexer and tokens

Lexer performs lexical analysis, which is the process of converting input string into the list of tokens. Each token has its own meaning and can contain a value. The first step is to define all tokens which we will need.

```go
type TokenType uint8

const (
	EOL TokenType = iota // End Of Line
	Unknown
	LPar
	RPar
	Exponent
	Multiplication
	Division
	FloorDiv
	Modulus
	Addition
	Substraction
	Number
	Identifier
	Whitespace
)

type Token struct {
	tType            TokenType
	value            float64
	idName           string
}
```

## "Cheating" with regular expression

The lexer can be implemented with [finite automata](https://en.wikipedia.org/wiki/Deterministic_finite_automaton). But it can be quite complicated, so I used regular expression. The final regex is in the code and also in [regex101.com](https://regex101.com/r/rczzqs/latest). The main reason I decided to use regular expression is to support multiple number formats. Like `123`, `5.48`, `.13`, `71.41e2`, `9.731e+3`, `4.43e-4` and all other not mentioned combinations.

# Simplified Lexer

The code below is just a simplified version of the used Lexer. Some edge cases are not caught with this code. Full code can be found on Github with all tests.

With regular expression, the input string is divided into parts and then converted into tokens. 

```go
var tokenRegexp = regexp.MustCompile(`\(|\)|\*\*|\^|//|%|\+|\-|\*|/|(?P<num>(?:[0-9]+(?:\.[0-9]+)?|\.[0-9]+)(?:e[+-]?[0-9]+)?)|(?P<id>(?i)[a-z_][a-z0-9_]*)|(?P<ws>\s+)`)

type Lexer struct {
	expr string
}

func NewLexer(expression string) *Lexer {
	return &Lexer{expr: expression}
}

func (l *Lexer) Tokenize() ([]*Token, error) {
	expr := make([]*Token, 0)

	for _, match := range tokenRegexp.FindAllStringSubmatch(l.expr, -1) {
		t := &Token{}
		switch {
		case match[2] != "":
			t.tType = Identifier
			t.idName = match[2]
		case match[1] != "":
			t.tType = Number
			var err error
			if t.value, err = strconv.ParseFloat(match[1], 64); err != nil {
				return nil, TokenError(t, ErrInvalidNumber)
			}
		case match[3] != "": // Ignore whitespace for now and skip it
			continue
		default:
			t.tType = operatorTokenType(match[0])
		}
		expr = append(expr, t)
	}
	expr = append(expr, &Token{tType: EOL})
	return expr, nil
}

func operatorTokenType(operator string) TokenType {
	switch operator {
	case "(":
		return LPar
	case ")":
		return RPar
	case "^", "**":
		return Exponent
	case "*":
		return Multiplication
	case "/":
		return Division
	case "//":
		return FloorDiv
	case "%":
		return Modulus
	case "+":
		return Addition
	case "-":
		return Substraction
	}
	return Unknown
}
```

## Why we need tokens?

It would be possible to write a single module, which would parse and count the result at once. But splitting the logic into multiple modules is one of the best practices. Check [Single-responsibility principle](https://en.wikipedia.org/wiki/Single-responsibility_principle) and optionally other design principles from [SOLID](https://en.wikipedia.org/wiki/SOLID).

If there would be a requirement to support inputs like `5 PLUS 8 TIMES 4` it would require only to change lexer. But not the rest of the program. The output of Lexer would be still the same.