Parsing expressions to bytecode

One way to evaluate an arithmetic expression is by converting it to its postfix representation. A pratt parser can be used to do this parsing in one pass. But first, a brief note on what postfix notation and how to use it for evaluation.

Consider the expression:

a + b * c

In postfix notation this becomes:

a b c * +

Evaluating postfix

This postfix notation can be easily mapped to an instruction stream that a virtual machine can evaluate:

Postfix tokens

IP →

OP_CONSTANT

OP_MULTIPLY

OP_ADD

OP_RETURN

Stack

(b * c)

(a + (b * c))

returns (a + (b * c))

The postfix expression.

step 1 / 10

Algorithm

All expressions we are going to parse will be of the form:

expression -> [unary] operand [binary operand]* | (expression)
operand    -> expression | number
unary      -> - | !
binary     -> + | - | / | *

(

opt

-|!

unary · opt

(-|!or 123or 123)

or123

operand

ⓧ

binary

(-|!or 123or 123)

or123

operand

repeats 0 or more times

)

opt

Precedence ofⓧ≤

Fig 1. The shape of an expression

Looking at this we can note that every expression has two parts:

The leading part that start with one of:
1. ( : followed by expression(-|!or 123or 123)
2. -, ! : followed by operand-|!or 123or 123
3. number: possibly followed by a binary operatoror 123or 123
The trailing part that is a series of subexpressions chained to the leading part via infix operators ⓧ.(-|!or 123or 123)

A note on operator precedence

We also need to pay attention to this:

Precedence ofⓧ≤

The precedence of an operator determines how strongly it binds to its operands. So if we had an expression like

a ⓧ b  c

we would be able to get the order of evaluation by applying the operator that has higher precedence. Here since ≥ ⓧ, we have

a ⓧ (b  c)

Hence, the stronger operator binds its operands first.

Suppose we have an expression where we have parsed the infix operator but not the trailing subexpression after it yet, as shown below:

a  ᚠᚢᚦᚨᚱᚲᚷᚹᚺᚾ

Multiple characters in ᚠᚢᚦᚨᚱᚲᚷᚹᚺᚾ could be an operator. We want to know till which operator we must parse to get the right operand of . All we have to do is look for an operator with a precedence lower than . By the rules of precedence, will bind anything that comes between those two operators.

a  ᚠᚢᚦᚨᚱ ⓧ ᚲᚷᚹᚺᚾ

As long as we know that there are no operators in ᚠᚢᚦᚨᚱ that are weaker than , we can safely consume ᚠᚢᚦᚨᚱ as the right operand.

In other words, if there is an operator in ᚠᚢᚦᚨᚱ that is stronger than , it will only end up binding ᚠᚢᚦᚨᚱ as a subexpression and have no effect on the value of the right operand of .

Implementation

Parsing a subexpression means appending the postfix notation of the subexpression to a global answer. So all parsing functions below will append their answer to the global variable and not return anything. All functions also share a global variable that keeps track of how much of the expression has been parsed, instead of passing index arguments.

Let's write a function parsePrecedence that will parse the trailing subexpression: (-|!or 123or 123). parsePrecedence(lowestAllowedPrecedence) will take the precedence of the leading operator as an argument, so that it can ensure that the subexpression only has operators stronger than that.

// The tokenized expression in infix notation
const tokenStream = [token1, token2, ...];
// Global parser object used in all recursive calls
const parser = {currentToken: 0, prevToken: -1};
// Will contain the expression in postfix notation after parsing
const answer = [];
function parsePrecedence(lowestAllowedPrecedence: number) {}

Next we create a rules table. This table records for each token:

infix function: knows how to parse the second operand if the token is used as an infix operator
prefix function: knows how to parse the operand when that token is used as a prefix operator
precedence: the precedence of the token if it's an operator

const rules = {
  [token1]: {infix: fn, prefix: fn, precedence: number},
  [token2]: {infix: fn, prefix: fn, precedence: number},
  ...
};
function getRule(token) {
  return rules[token];
}

Now we can attempt to fill up the definition of this function:

// The tokenized expression in infix notation
function parsePrecedence(lowestAllowedPrecedence: number) {
  // PARSE THE PREFIX PART OF THE SUBEXPRESSION
  // Take first token of the subexpression after the infix operator
  advance();

  // Expect the first token of the subexpression to have a prefix rule. As it has to be one of the 3 cases in the section 2.1.
  const rule = getRule(parser.prevToken);
  if (!rule.prefix) throw new Error("Not an expression");

  // Parse the prefix part of the subexpression using its associated rule
  rule.prefix();
  // ---------------------------------------------------

  // PARSE ALL TRAILING PARTS IN THE SUBEXPRESSION
  // if the next infix operator is stronger than the threshold, keep parsing.
  while (getRule(parser.currentToken).precedence >= lowestAllowedPrecedence) {
    const rule = getRule(parser.currentToken);
    rule.infix();
  }
  // ---------------------------------------------------
}

Looking at some of the rules can be illuminating. Especially the infix rule for a binary operator

For '-' we need a prefix and an infix handler

prefix: () => {
  // get the minus
  const token = scanToken();
  parsePrecedence(PREC_UNARY);
  // Add the negation operator to the top of the parsed stack
  pushToStack(OP_NEGATE);
},
infix: () => {
  // get the minus
  const token = scanToken();
  // parse the postfix expression for the right operand of -. It will be the subexpression which only contains operators of a higher precedence than -.
  parsePrecedence(PREC_MINUS + 1);
  // Push the minus operation to the stack
  pushToStack(OP_MINUS);
}

Now that we have the subexpression parser parsePrecedence, we only need to realize that we can parse the full expression by treating it as the rhs of an assignment. So any expression that we want to parse can be part of an assignment

var a = -b + (c - d) + e * f;

we can parse this by using the precedence of the assignment operator and treating the entire expression as a subexpression following the assignment.

parsePrecedence(PREC_ASSIGNMENT)

Github links

A working implementation of a pratt parser can be found in https://github.com/gautam1168/interpreter/blob/main/compiler.c on the tag ch17. Running it on the following expression:

(5 - (3 - 1)) + -1

will print the parsed instruction stream that is the postfix notation:

== code ==
0000    1 OP_CONSTANT         0 '5'
0002    | OP_CONSTANT         1 '3'
0004    | OP_CONSTANT         2 '1'
0006    | OP_SUBTRACT
0007    | OP_SUBTRACT
0008    | OP_CONSTANT         3 '1'
0010    | OP_NEGATE
0011    | OP_ADD
0012    2 OP_RETURN

after this it will also print out the execution trace. Where it first prints the opcode, followed by the evaluation stack. Finally it ends with the return value printed out.

0000    1 OP_CONSTANT         0 '5'
           [5]
0002    | OP_CONSTANT         1 '3'
           [5][3]
0004    | OP_CONSTANT         2 '1'
           [5][3][1]
0006    | OP_SUBTRACT
           [5][2]
0007    | OP_SUBTRACT
           [3]
0008    | OP_CONSTANT         3 '1'
           [3][1]
0010    | OP_NEGATE
           [3][-1]
0011    | OP_ADD
           [2]
0012    2 OP_RETURN
2