Expression Parser Explorer

Type an expression and step through how a recursive descent parser reads it: the token stream, the grammar-rule call stack and the abstract syntax tree, using the exact grammar from the compiler series.

What the explorer runs

The explorer runs the expression part of the compiler series’ front end. The lexer is the one from chapter 3, and the parser follows the expression rules of chapter 4 step for step. Rule names, token kinds, node names and error messages are the ones the C++ code uses. The input is the expression subset of Si: integer and boolean literals, names, function calls, unary - and !, and the binary operators * /, + -, < <= > >= and == !=. Statements, types and blocks are not part of it. Nothing you type is evaluated. The explorer only lexes and parses.

Parsing happens in two phases. First the lexer turns characters into tokens, one per step, and appends an EOF token. Then the parser reads those tokens and builds an abstract syntax tree (AST). With Step by: Rule call, every rule entry, consumed token, created node and return is a separate step. Token granularity groups everything up to the next consumed token, which is faster to play through.

Precedence comes from the order of the rules

The grammar is a ladder, from the loosest-binding operators to the tightest:

expression     -> equality ;
equality       -> comparison (("==" | "!=") comparison)* ;
comparison     -> additive (("<" | "<=" | ">" | ">=") additive)* ;
additive       -> multiplicative (("+" | "-") multiplicative)* ;
multiplicative -> unary (("*" | "/") unary)* ;
unary          -> ("!" | "-") unary | primary ;
primary        -> INT | BOOL | IDENT | IDENT "(" arguments? ")" | "(" expression ")" ;

Nothing in the grammar states that * binds tighter than +. It doesn’t have to. additive can only see its operands through multiplicative, so by the time additive looks for a +, any * between the operands has already been consumed and wrapped into a node one level down. Watch the Call stack panel while parsing a + b * 2: the operand b is read deep inside multiplicative, which keeps going and consumes * 2 before it returns to additive. In the finished tree, the multiplication is therefore a child of the addition.

Parentheses work by climbing back up the ladder. When primary sees (, it calls expression again, so whatever is inside the parentheses gets parsed completely before the outer rules carry on. They create no node of their own. The tree for (a) is just Identifier a.

Associativity comes from the loops

Every binary level runs the same loop as parseBinaryExpression in the chapter. It parses a left operand, then, while the next token is one of its operators, consumes the operator, parses a right operand and replaces the left operand with a new BinaryExpression node. Because each new node takes the previous result as its left child, a - b - c becomes (a - b) - c. The operators are left-associative, which is what subtraction and division need.

Unary operators are the exception. unary calls itself for its operand, so !!ok nests to the right: Not(Not(ok)).

Why there is no left recursion

A textbook grammar might write additive -> additive "+" multiplicative. A recursive descent parser can’t use that directly: the function for additive would call itself before consuming any input and recurse until the stack overflowed. Chapter 4 avoids it by writing each level as an operand followed by a repeated (operator operand)*, which is exactly the loop above. The chapter’s grammar section and its list of common recursive descent mistakes cover this in more detail.

Reading the errors

Errors use the parser’s own format: Parse error at line:column: message; found 'token'. One detail is easy to miss. parsePrimary advances before it inspects the token, so in a + * b the error points at the * it has just consumed, and it is reported from primary, not from additive. A missing ) is reported against whatever token stood where the parenthesis should have been, or end of file.

The explorer adds two checks of its own, labelled as such. The series always parses an expression inside a statement, so leftover input after a complete expression is reported as Expected end of expression, where the full compiler would complain about a missing ;. And the explorer caps input at 200 characters and 32 levels of nesting, so that a pasted or shared expression can’t freeze the page.

Try it

1. 01

   a + b * 2 · precedence

   Before you press Next step, predict the shape of the tree for a + b * 2. Then step through it and note which rule is active when * is consumed.

2. 02

   (a + b) * 2 · parentheses

   Now parse (a + b) * 2. The parentheses send primary back to expression. Which node ends up at the root this time?

3. 03

   a - b - c · left associativity

   Step through a - b - c at Token granularity. Is the first BinaryExpression - created before or after the second - is consumed, and why does that make it the left child?

4. 04

   a < b == c · mixed levels

   Parse a < b == c, then change it to a == b < c. In both trees, comparison sits below equality. Why does the order in the source make no difference?

5. 05

   a + * b · syntax error

   Step a + * b until it fails. Which frames are on the call stack when the error is raised, and which token does the message point at?

Each one opens the matching scenario in the explorer above.

Answer to experiment 2

BinaryExpression * is the root. The parentheses force a + b to be parsed completely inside primary before multiplicative sees the *, so the addition becomes the multiplication’s left operand. Without parentheses, the multiplication is nested inside the addition instead. Same tokens, different tree.

What the full compiler does next

The tree you see here is where the rest of the compiler starts. In chapter 5, semantic analysis gives every name and every node a type and rejects programs such as 1 + true, which this explorer accepts because they are grammatically correct. Chapter 6 lowers the checked tree into three-address instructions, and from chapter 7 onwards those become x86-64 assembly. The full series builds the complete Si compiler in C++.