Crafting Interpreters: Part 3 Parsing Expressions

Introduction

In this article series, we’ll work through the excellent Crafting Interpreters, but with a twist: we’ll implement everything in Go instead of Java. Along the way, we’ll explore how the ideas in the book translate to idiomatic Go while building an interpreter from the ground up.

You can find the current state of the code corresponding to this article here.

What we will build

In this chapter, we’ll build a parser to turn our tokens into our grammar structure we built in the last chapter.

A parser takes the stream of tokens and organizes them into a structured representation (usually an AST) that reflects the grammatical rules of the language. This step is crucial because it turns flat text into a form the interpreter can actually understand and execute correctly.

Our parser will function very similarly to out scanner in part one, except instead of turning a list of characters into tokens, it will turn a list of tokens into expressions.

Writing the Parser

Our parser will maintain a list of tokens along with a pointer to its current position in that list. This allows it to walk through the tokens sequentially, consuming them as it recognizes patterns defined by the grammar and building up the program’s structure step by step.

type Parser struct {
 Tokens  []token.Token
 Current int
}

type ParseError struct {
 Message string
}

func (e ParseError) Error() string {
 return fmt.Sprintf("parse error: %s", e.Message)
}

func NewParser(tokens []token.Token) *Parser {
 return &Parser{Tokens: tokens, Current: 0}
}

Just like in the scanner, the parser relies on a set of helper functions to move through the token list while constructing expressions. These utilities handle things like advancing the current position, peeking at upcoming tokens, and conditionally consuming expected ones, making the parsing logic cleaner and easier to reason about.

func (p *Parser) match(types ...token.TokenType) bool {
 for _, typ := range types {
  if p.check(typ) {
   p.advance()
   return true
  }
 }
 return false
}

func (p *Parser) advance() token.Token {
 if !p.isAtEnd() {
  p.Current++
 }
 return p.previous()
}

func (p *Parser) isAtEnd() bool {
 return p.peek().Type == token.EOF
}

func (p *Parser) peek() token.Token {
 return p.Tokens[p.Current]
}

func (p *Parser) previous() token.Token {
 return p.Tokens[p.Current-1]
}

func (p *Parser) check(typ token.TokenType) bool {
 if p.isAtEnd() {
  return false
 }
 return p.peek().Type == typ
}

func (p *Parser) consume(typ token.TokenType, message string) (token.Token, error) {
 if p.check(typ) {
  return p.advance(), nil
 }

 return p.peek(), p.error(p.peek(), message)
}

func (p *Parser) error(token token.Token, message string) ParseError {
 lox.Error(token.Line, message)
 return ParseError{Message: message}
}

We also include a special synchronize function to recover from parsing errors by advancing through tokens until it reaches a safe point—typically the next semicolon or the start of a new statement. This prevents a single error from cascading into many, allowing the parser to continue processing the rest of the program.

It is unused for now, but we will utilize it in later chapters when we add in classes and flow control.

func (p *Parser) synchronize() {
 p.advance()

 for !p.isAtEnd() {
  if p.previous().Type == token.SEMICOLON {
   return
  }
  switch p.peek().Type {
  case token.CLASS, token.FUN, token.VAR, token.FOR, token.IF, token.WHILE, token.PRINT, token.RETURN:
   return
  }
  p.advance()
 }
}

Our entry point is the parse function, which attempts to consume the entire token list and produce a valid representation of the program (typically an expression or a list of statements). This ensures that all tokens are accounted for and that the input forms a complete, well-structured program rather than just a partial match.

func (p *Parser) Parse() (grammar.Expr, error) {
 expr, err := p.expression()
 if err != nil {
  return nil, err
 }
 return expr, nil
}

We then apply our grammar rules to recursively expand a single expression into a full Abstract Syntax Tree (AST). Each rule corresponds to a specific pattern in the language, allowing the parser to build up a hierarchical structure that captures both the order of operations and the relationships between different parts of the program.

expression     → equality ;
equality       → comparison ( ( "!=" | "==" ) comparison )* ;
comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term           → factor ( ( "-" | "+" ) factor )* ;
factor         → unary ( ( "/" | "*" ) unary )* ;
unary          → ( "!" | "-" ) unary
               | primary ;
primary        → NUMBER | STRING | "true" | "false" | "nil"
               | "(" expression ")" ;

Expressions will become an equality.

func (p *Parser) expression() (grammar.Expr, error) {
 expr, err := p.equality()
 if err != nil {
  return nil, err
 }
 return expr, nil
}

Equalities become a comparison, an equality token and another comparison.

func (p *Parser) equality() (grammar.Expr, error) {
 expr, err := p.comparison()
 if err != nil {
  return nil, err
 }

 for p.match(token.BANG_EQUAL, token.EQUAL_EQUAL) {
  operator := p.previous()
  right, err := p.comparison()
  if err != nil {
   return nil, err
  }
  expr = grammar.NewBinary(expr, operator, right)
 }
 return expr, nil
}

Comparisons become a term, a comparator token and another term

func (p *Parser) comparison() (grammar.Expr, error) {
 expr, err := p.term()
 if err != nil {
  return nil, err
 }

 for p.match(token.GREATER, token.GREATER_EQUAL, token.LESS, token.LESS_EQUAL) {
  operator := p.previous()
  right, err := p.term()
  if err != nil {
   return nil, err
  }
  expr = grammar.NewBinary(expr, operator, right)
 }
 return expr, nil
}

Terms become a factor, a plus/minus and another factor.

func (p *Parser) term() (grammar.Expr, error) {
 expr, err := p.factor()
 if err != nil {
  return nil, err
 }

 for p.match(token.MINUS, token.PLUS) {
  operator := p.previous()
  right, err := p.factor()
  if err != nil {
   return nil, err
  }
  expr = grammar.NewBinary(expr, operator, right)
 }
 return expr, nil
}

Factors become a unary, a divide or multiply and another unary.

func (p *Parser) factor() (grammar.Expr, error) {
 expr, err := p.unary()
 if err != nil {
  return nil, err
 }

 for p.match(token.SLASH, token.STAR) {
  operator := p.previous()
  right, err := p.unary()
  if err != nil {
   return nil, err
  }
  expr = grammar.NewBinary(expr, operator, right)
 }
 return expr, nil
}

Unaries can become another unary (prefixed with a ! or a - ) OR just a primary.

func (p *Parser) unary() (grammar.Expr, error) {
 if p.match(token.BANG, token.MINUS) {
  operator := p.previous()
  right, err := p.unary()
  if err != nil {
   return nil, err
  }
  return grammar.NewUnary(operator, right), nil
 }

 return p.primary()
}

And primaries can be come any primitive token — or they could match back into a full expression.

func (p *Parser) primary() (grammar.Expr, error) {
 if p.match(token.FALSE) {
  return grammar.NewLiteral(false), nil
 }
 if p.match(token.TRUE) {
  return grammar.NewLiteral(true), nil
 }
 if p.match(token.NIL) {
  return grammar.NewLiteral(nil), nil
 }

 if p.match(token.NUMBER, token.STRING) {
  return grammar.NewLiteral(p.previous().Literal), nil
 }

 if p.match(token.LEFT_PAREN) {
  expr, err := p.expression()
  if err != nil {
   return nil, err
  }
  p.consume(token.RIGHT_PAREN, "Expect ')' after expression.")
  return grammar.NewGrouping(expr), nil
 }

 return nil, p.error(p.peek(), "Expect expression.")
}

Testing

With this parser set up we can take a basic lox file like

-123 * (45.67)

and have it scanned and parsed into our lisp like syntax

(* (- 123) (group 45.67))

using this test code.

func TestAstPrinterParser(t *testing.T) {
 content := loadFile("./fixtures/basic.lox")
 scanner := scanner.NewScanner(content)
 tokens := scanner.ScanTokens()

 parser := parser.NewParser(tokens)
 expr, err := parser.Parse()
 if err != nil {
  t.Errorf("expected no error, got %v", err)
 }
 fmt.Println(expr)

 expected := "(* (- 123) (group 45.67))"

 printer := AstPrinter{}
 result := expr.Accept(&printer)
 if result != expected {
  t.Errorf("expected %s, got %s", expected, result)
 }
}

Conclusion

In this article, we explored how to build a parser that transforms a flat list of tokens into a structured Abstract Syntax Tree (AST) using a set of grammar-driven matching rules. Along the way, we saw how this process mirrors the scanner, which walks through raw characters to produce tokens — except now we’re operating at a higher level of abstraction. Finally, we validated our work with an end-to-end test, confirming that our scanner and parser work together to correctly process input. In the next chapter, we’ll take the next step and begin evaluating these expressions, turning our AST into a functioning (and very minimal) calculator language.