Parser example (GoWayFest 2018)

parser.go

package main

import (
	"fmt"
	"os"
	"regexp"
	"strings"
)

type token = string

type node interface{}

type binaryNode struct {
	op    token
	left  node
	right node
}

var (
	check     = regexp.MustCompile("[a-z0-9]+")
	stack     = make([]node, 0)
	tokens    []token
	lookahead token
)

func main() {
	tokens = lex(os.Args[1])
	lookahead = next()

	expr()
	fmt.Println(pop())
}

func expr() {
	term()
	exprR()
}

func exprR() {
	if lookahead == "+" {
		match("+")
		term()
		emit("+")
		exprR()
	} else if lookahead == "-" {
		match("-")
		term()
		emit("-")
		exprR()
	}
}

func term() {
	factor()
	termR()
}

func termR() {
	if lookahead == "*" {
		match("*")
		factor()
		emit("*")
		exprR()
	} else if lookahead == "/" {
		match("/")
		factor()
		emit("/")
		exprR()
	}
}

func factor() {
	if lookahead == "(" {
		match("(")
		expr()
		match(")")
	} else {
		atom()
	}
}

func atom() {
	if check.MatchString(lookahead) {
		stack = append(stack, lookahead)
		lookahead = next()
	} else {
		panic("expected atom")
	}
}

func pop() node {
	top := stack[len(stack)-1]
	stack = stack[:len(stack)-1]
	return top
}

func emit(op token) {
	right := pop()
	left := pop()

	node := binaryNode{
		op,
		left,
		right,
	}
	stack = append(stack, node)
}

func next() token {
	if len(tokens) > 0 {
		x := tokens[0]
		tokens = tokens[1:]
		return x
	}
	return ""
}

func match(terminal token) {
	if lookahead == terminal {
		lookahead = next()
	} else {
		panic("expected token " + terminal)
	}
}

func lex(input string) []token {
	return strings.Split(input, "")
}