Pratt Parser

main.go

package main

// go port of https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing

import (
	"fmt"
	"log"
	"regexp"
	"strconv"
)

func main() {
	val, err := parse("1 + 2 * 4")
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("%d\n", val)
}

type value int

type token interface {
	lbp() int
	nud() (value, error)
	led(value) (value, error)
}

var tokenPat = regexp.MustCompile(`\s*(?:(\d+)|(.))`)

func tokenize(program string) []token {
	var tokens []token
	for _, match := range tokenPat.FindAllStringSubmatch(program, -1) {
		number := match[1]
		operator := match[2]
		if number != "" {
			n, err := strconv.Atoi(number)
			if err != nil {
				log.Fatal(err)
			}
			tokens = append(tokens, &literalToken{value(n)})
			continue
		}
		switch operator {
		case "+":
			tokens = append(tokens, &operatorAddToken{})
		case "-":
			tokens = append(tokens, &operatorSubToken{})
		case "*":
			tokens = append(tokens, &operatorMulToken{})
		case "/":
			tokens = append(tokens, &operatorDivToken{})
		default:
			log.Fatalf("unknown operator: %s", operator)
		}
	}
	tokens = append(tokens, &endToken{})
	return tokens
}

var t token
var tokens []token

func expression(rbp int) (value, error) {
	f := t.nud
	if len(tokens) == 0 {
		return 0, fmt.Errorf("no tokens: %v", tokens)
	}
	t, tokens = tokens[0], tokens[1:]
	left, err := f()
	if err != nil {
		return 0, err
	}
	for rbp < t.lbp() {
		f := t.led
		if len(tokens) == 0 {
			return 0, fmt.Errorf("no tokens: %v", tokens)
		}
		t, tokens = tokens[0], tokens[1:]
		left, err = f(left)
		if err != nil {
			return 0, err
		}
	}
	return left, nil
}

type literalToken struct {
	value value
}

func (t *literalToken) lbp() int {
	return 0
}

func (t *literalToken) nud() (value, error) {
	return t.value, nil
}

func (t *literalToken) led(left value) (value, error) {
	return 0, nil
}

type operatorAddToken struct {
}

func (t *operatorAddToken) lbp() int {
	return 10
}

func (t *operatorAddToken) nud() (value, error) {
	return expression(100)
}

func (t *operatorAddToken) led(left value) (value, error) {
	right, err := expression(10)
	if err != nil {
		return 0, err
	}
	return left + right, nil
}

type operatorSubToken struct {
}

func (t *operatorSubToken) lbp() int {
	return 10
}

func (t *operatorSubToken) nud() (value, error) {
	right, err := expression(100)
	if err != nil {
		return 0, err
	}
	return -right, nil
}

func (t *operatorSubToken) led(left value) (value, error) {
	right, err := expression(10)
	if err != nil {
		return 0, err
	}
	return left - right, nil
}

type operatorMulToken struct {
}

func (t *operatorMulToken) lbp() int {
	return 20
}

func (t *operatorMulToken) nud() (value, error) {
	return 0, nil
}

func (t *operatorMulToken) led(left value) (value, error) {
	right, err := expression(20)
	if err != nil {
		return 0, err
	}
	return left * right, nil
}

type operatorDivToken struct {
}

func (t *operatorDivToken) lbp() int {
	return 20
}

func (t *operatorDivToken) nud() (value, error) {
	return 0, nil
}

func (t *operatorDivToken) led(left value) (value, error) {
	right, err := expression(20)
	if err != nil {
		return 0, err
	}
	return left / right, nil
}

type endToken struct {
}

func (t *endToken) lbp() int {
	return 0
}

func (t *endToken) nud() (value, error) {
	return 0, nil
}

func (t *endToken) led(left value) (value, error) {
	return 0, nil
}

func parse(program string) (value, error) {
	tokens = tokenize(program)
	if len(tokens) == 0 {
		return 0, fmt.Errorf("no tokens: %v", tokens)
	}
	t, tokens = tokens[0], tokens[1:]
	return expression(0)
}