asm-calc/parser/parser.go

// Package parser builds an expression tree from tokens.
package parser

import (
	"fmt"
	"strconv"

	"github.com/zg/asm-calc/lexer"
)

// Node is an expression tree node.
type Node interface{ node() }

// Number is an integer literal.
type Number struct{ Value int64 }

// Variable is a named value.
type Variable struct{ Name string }

// BinaryOp is an infix operation.
type BinaryOp struct {
	Op          lexer.TokenType
	Left, Right Node
}

// UnaryOp is a prefix operation (only negation).
type UnaryOp struct {
	Op      lexer.TokenType
	Operand Node
}

// Assignment binds a name to an expression.
type Assignment struct {
	Name  string
	Value Node
}

func (*Number) node()     {}
func (*Variable) node()   {}
func (*BinaryOp) node()   {}
func (*UnaryOp) node()    {}
func (*Assignment) node() {}

// Parse builds a tree from input.
func Parse(input string) (Node, error) {
	tokens, err := lexer.Lex(input)
	if err != nil {
		return nil, err
	}
	p := &parser{tokens: tokens}
	node, err := p.parseStatement()
	if err != nil {
		return nil, err
	}
	if p.cur().Type != lexer.EOF {
		return nil, fmt.Errorf("column %d: unexpected %s", p.cur().Column, p.cur().Type)
	}
	return node, nil
}

type parser struct {
	tokens []lexer.Token
	pos    int
}

func (p *parser) cur() lexer.Token { return p.tokens[p.pos] }
func (p *parser) peek() lexer.Token {
	if p.pos+1 < len(p.tokens) {
		return p.tokens[p.pos+1]
	}
	return p.tokens[len(p.tokens)-1]
}
func (p *parser) next() lexer.Token { t := p.tokens[p.pos]; p.pos++; return t }

func (p *parser) parseStatement() (Node, error) {
	// An assignment is `ident = expr`; two tokens of lookahead distinguish
	// it from an expression beginning with a variable.
	if p.cur().Type == lexer.IDENT && p.peek().Type == lexer.ASSIGN {
		name := p.next().Value
		p.next() // '='
		value, err := p.parseExpression()
		if err != nil {
			return nil, err
		}
		return &Assignment{Name: name, Value: value}, nil
	}
	return p.parseExpression()
}

// parseExpression handles + and -, the loosest-binding operators.
func (p *parser) parseExpression() (Node, error) {
	left, err := p.parseTerm()
	if err != nil {
		return nil, err
	}
	for p.cur().Type == lexer.PLUS || p.cur().Type == lexer.MINUS {
		op := p.next().Type
		right, err := p.parseTerm()
		if err != nil {
			return nil, err
		}
		left = &BinaryOp{Op: op, Left: left, Right: right}
	}
	return left, nil
}

// parseTerm handles *, / and %.
func (p *parser) parseTerm() (Node, error) {
	left, err := p.parseUnary()
	if err != nil {
		return nil, err
	}
	for t := p.cur().Type; t == lexer.STAR || t == lexer.SLASH || t == lexer.PERCENT; t = p.cur().Type {
		op := p.next().Type
		right, err := p.parseUnary()
		if err != nil {
			return nil, err
		}
		left = &BinaryOp{Op: op, Left: left, Right: right}
	}
	return left, nil
}

func (p *parser) parseUnary() (Node, error) {
	if p.cur().Type == lexer.MINUS {
		p.next()
		operand, err := p.parseUnary()
		if err != nil {
			return nil, err
		}
		return &UnaryOp{Op: lexer.MINUS, Operand: operand}, nil
	}
	if p.cur().Type == lexer.PLUS {
		p.next() // unary plus is a no-op
		return p.parseUnary()
	}
	return p.parsePower()
}

// parsePower handles ^, which binds tightest and is right-associative:
// 2^3^2 is 2^(3^2), not (2^3)^2.
func (p *parser) parsePower() (Node, error) {
	base, err := p.parsePrimary()
	if err != nil {
		return nil, err
	}
	if p.cur().Type == lexer.CARET {
		p.next()
		// Recursing into parseUnary rather than parsePower is what makes
		// the operator right-associative and lets 2^-1 parse.
		exponent, err := p.parseUnary()
		if err != nil {
			return nil, err
		}
		return &BinaryOp{Op: lexer.CARET, Left: base, Right: exponent}, nil
	}
	return base, nil
}

func (p *parser) parsePrimary() (Node, error) {
	tok := p.cur()
	switch tok.Type {
	case lexer.NUMBER:
		p.next()
		v, err := strconv.ParseInt(tok.Value, 10, 64)
		if err != nil {
			return nil, fmt.Errorf("column %d: %q does not fit in a 64-bit integer", tok.Column, tok.Value)
		}
		return &Number{Value: v}, nil

	case lexer.IDENT:
		p.next()
		return &Variable{Name: tok.Value}, nil

	case lexer.LPAREN:
		p.next()
		inner, err := p.parseExpression()
		if err != nil {
			return nil, err
		}
		if p.cur().Type != lexer.RPAREN {
			return nil, fmt.Errorf("column %d: expected ')', got %s", p.cur().Column, p.cur().Type)
		}
		p.next()
		return inner, nil

	case lexer.EOF:
		return nil, fmt.Errorf("column %d: unexpected end of input", tok.Column)

	default:
		return nil, fmt.Errorf("column %d: unexpected %s", tok.Column, tok.Type)
	}
}