Building an interpreter in Go: Parser

Now that we've scanned the input text into tokens (see previous post), we can turn those tokens into an Abstract Syntax Tree!

The book I've been reading implements a recursive descent parser, and explains it in depth. I've created a visualization of the recursive descent parser using d3.js talking to my parser (written in go) through WebAssembly.

Once again, try changing the inputs to see for yourself! The parser currently only recognizes these operators: +, -, *, /, <, >, <=, >=, ==, !=, and ().

As you can see, the output of the parser is a tree representing the operations in the expression. Each node in the tree is itself an expression represented by a subtree.

The parser reads the tokens left to right, but goes through the operators from lowest precedence to highest precedence.

When the parser is going to assign the right child of some operator, it looks for an expression made from higher-precedence operators.

For example, the expression 2 + 3 * 4: After the parser has found the +, it says "Okay, I've got 2 + some expression", where some expression contains *, /, or () operators.

It'll keep reading tokens as long as they're higher precedence than +, and once it finds one that isn't, it'll assign the right side of + to that expression.

Since each operation is always deferring to higher precedence operators, this works! To understand this better, I'd recommend playing around with the visualization!