Expression parser using Recursive Descent

recursive-descent-parser.go

package main

import (
	"errors"
	"fmt"
)

type AstNodeType int

const (
	OperatorNode AstNodeType = 0
	NumberNode               = 1
)

type AstNode struct {
	Type     AstNodeType
	Value    string
	Children []AstNode
}

func EmptyNode() AstNode {
	return AstNode{}
}

func CreateNode(nodeType AstNodeType, value string, children []AstNode) AstNode {
	return AstNode{
		Type:     nodeType,
		Value:    value,
		Children: children,
	}
}

type TokenType int

const (
	NumberToken TokenType = 0
	AddToken              = 1
	SubToken              = 2
)

type Token struct {
	Type    TokenType
	Content string
}

func CreateToken(tokenType TokenType, content string) Token {
	return Token{tokenType, content}
}

type Parser struct {
	Tokens []Token
	Pos    int
}

func CreateParser(tokens []Token) Parser {
	return Parser{
		Tokens: tokens,
		Pos:    0,
	}
}

func (p *Parser) EOF() bool {
	return p.Pos >= len(p.Tokens)
}

func (p *Parser) Peek() Token {
	return p.Tokens[p.Pos]
}

func (p *Parser) Match(tokenType TokenType) bool {
	if !p.EOF() && p.Peek().Type == tokenType {
		return true
	}
	return false
}

func (p *Parser) Advance() {
	p.Pos++
}

func (p *Parser) ParseTerm() (AstNode, error) {
	if p.Match(NumberToken) {
		token := p.Peek()
		p.Advance()
		return CreateNode(NumberNode, token.Content, []AstNode{}), nil
	}
	return EmptyNode(), errors.New("ParseError: expected a Number")
}

func (p *Parser) ParseExpr() (AstNode, error) {
	node, err := p.ParseTerm()
	if err != nil {
		return EmptyNode(), err
	}

	for p.Match(AddToken) || p.Match(SubToken) {
		token := p.Peek()
		p.Advance()
		term, err := p.ParseTerm()
		if err != nil {
			return EmptyNode(), err
		}
		node = CreateNode(OperatorNode, token.Content, []AstNode{node, term})
	}

	return node, nil
}

func (p *Parser) Parse() AstNode {
	root, err := p.ParseExpr()
	if err != nil {
		fmt.Println(p.Pos, p.Peek(), err)
	}
	return root
}

func main() {
	tokens := []Token{
		CreateToken(NumberToken, "1"),
		CreateToken(AddToken, "+"),
		CreateToken(NumberToken, "2"),
		CreateToken(SubToken, "-"),
		CreateToken(NumberToken, "3"),
	}
	parser := CreateParser(tokens)
	root := parser.Parse()
	fmt.Printf("%+v", root)
}