Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Expression parser using Recursive Descent
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment