Capstone B: the parser

A parser reads the token list from the previous lesson and builds a tree, and the shape of the tree is the meaning of the expression. Recursive descent writes that shape as a method per rule of the grammar, which is the smallest parser a person can read. The program below parses five inputs: three it accepts and two it refuses, and the output states the root operator and the number of nodes of each tree.

Three rules

The grammar of the calculator has three rules, and each one becomes one method:

The methods call each other in the order of the rules, so the operator that binds tightest is asked first. A loop inside Term makes it left-associative: every pass takes the tree built so far as the left side of the next node.

Console.WriteLine("calc 1.0"); Show("1 + 2 * 3"); Show("(1 + 2) * 3"); Show("2 * 3 + 4 * 5"); Show("1 +"); Show("1 + (2"); static void Show(string text) { try { var node = Parse(Lex(text)); Console.WriteLine($"{text,-12} root {Root(node),-5} nodes {Count(node)}"); } catch (FormatException ex) { Console.WriteLine($"{text,-12} error: {ex.Message}"); } } static string Root(Node node) => node switch { Binary binary => binary.Op.ToString(), Unary unary => $"unary {unary.Op}", _ => "number", }; static int Count(Node node) => node switch { Binary binary => 1 + Count(binary.Left) + Count(binary.Right), Unary unary => 1 + Count(unary.Operand), _ => 1, }; static List<Token> Lex(string text) { var tokens = new List<Token>(); var i = 0; while (i < text.Length) { var c = text[i]; if (char.IsWhiteSpace(c)) { i++; continue; } if (char.IsDigit(c) || c == '.') { var start = i; while (i < text.Length && (char.IsDigit(text[i]) || text[i] == '.')) { i++; } var number = text[start..i]; var value = double.Parse(number, System.Globalization.CultureInfo.InvariantCulture); tokens.Add(new Token(TokenKind.Number, value, start, number)); continue; } if (c is '+' or '-' or '*' or '/' or '(' or ')') { tokens.Add(new Token(TokenKind.Operator, 0, i, c.ToString())); i++; continue; } throw new FormatException($"unexpected '{c}' at {i}"); } tokens.Add(new Token(TokenKind.End, 0, text.Length, "end")); return tokens; } static Node Parse(List<Token> tokens) => Parser.Parse(tokens); enum TokenKind { Number, Operator, End, } record Token(TokenKind Kind, double Value, int Position, string Text); abstract record Node; sealed record Number(double Value) : Node; sealed record Unary(char Op, Node Operand) : Node; sealed record Binary(char Op, Node Left, Node Right) : Node; sealed class Parser { private readonly List<Token> _tokens; private int _index; private Parser(List<Token> tokens) => _tokens = tokens; public static Node Parse(List<Token> tokens) => new Parser(tokens).Expression(); private Token Current => _tokens[_index]; private Node Expression() { var left = Term(); while (Current.Kind == TokenKind.Operator && Current.Text is "+" or "-") { var op = Current.Text[0]; _index++; left = new Binary(op, left, Term()); } return left; } private Node Term() { var left = Factor(); while (Current.Kind == TokenKind.Operator && Current.Text is "*" or "/") { var op = Current.Text[0]; _index++; left = new Binary(op, left, Factor()); } return left; } private Node Factor() { var token = Current; switch (token.Kind) { case TokenKind.Number: _index++; return new Number(token.Value); case TokenKind.Operator when token.Text == "-": _index++; return new Unary('-', Factor()); case TokenKind.Operator when token.Text == "(": _index++; var inner = Expression(); Expect(")"); return inner; default: throw new FormatException($"expected a number at {token.Position}"); } } private void Expect(string text) { if (Current.Kind != TokenKind.Operator || Current.Text != text) { throw new FormatException($"expected '{text}' at {Current.Position}"); } _index++; } }

dotnet run
echo "status: $?"

calc 1.0
1 + 2 * 3    root +     nodes 5
(1 + 2) * 3  root *     nodes 5
2 * 3 + 4 * 5 root +     nodes 7
1 +          error: expected a number at 3
1 + (2       error: expected ')' at 6
status: 0

The first line is the banner of the program; the five lines under it are one per input.

Precedence in the tree

The root operator of a tree is the operation that happens last, so it is also the operation with the lowest precedence in that expression:

The node count is the size of the tree: five nodes for three numbers and two operators, seven for five numbers and two operators. A count that differs from the arithmetic is the first sign that a token was dropped or read twice.

An error with a position

The last two inputs are broken in the two ways a calculator must expect. 1 + ends where a number should begin, and 1 + (2 ends without the closing parenthesis. Both errors are the same shape: the message names the token that was expected, and the position is the index of the token where the parser stopped. For 1 + that index is three, which is the end of the line; for 1 + (2 it is six, one past the last character, where the ) would go.

Current is a property over the token list and _index is the position in it. No method checks whether the list is over, because the lexer always appends an End token, and reading past it would be a defect of the parser rather than an input error.

The next lesson gives this tree a readable form: a printer that puts every operator in parentheses, and a round trip that parses the printed text again and compares the two trees.

Exercises

  1. Add a rule for a power operator that binds tighter than multiplication and is right-associative.
  2. Print, for each input, the operator of every node of depth two, and check by hand that the order is the order of evaluation.
  3. Reject an empty input with an error at position zero and a message that says so.
  4. Count the nodes without recursion and compare the number with the recursive count.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Why does Term call Factor and not Expression?

    Answer

    Because multiplication binds tighter than addition, and the tighter rule is asked first

    The order of the calls is the order of precedence.

  2. What is the root operator of 2 * 3 + 4?

    Answer

    The plus

    The multiplication is evaluated first, so the addition is the last operation.

  3. What does this program print? static int Depth(string text, int level) => level == 0 ? text.Length : Depth(text, level - 1); Console.WriteLine(Depth("abcd", 2));

    Answer

    4

    The recursion stops at level zero and answers the length.

  4. Why does the loop in Expression make the operator left-associative?

    Answer

    Each pass wraps the tree built so far on the left of the new node

    1 - 2 - 3 becomes ((1 - 2) - 3), which is what a reader expects.

  5. What does this program print? Console.WriteLine(1 - 2 - 3);

    Answer

    -4

    Left-associative subtraction gives (1 - 2) - 3.

  6. Which input does the parser refuse with expected a number at 3?

    Answer

    1 +

    The end of the line is where the missing number would be.

  7. What does this program print? var text = "1 + (2"; Console.WriteLine(text.Length);

    Answer

    6

    The closing parenthesis would sit at index six.

  8. What does a tree of five nodes for 1 + 2 * 3 contain?

    Answer

    Three numbers and two operator nodes

    Every number is a leaf and every operator is a node with two children.

  9. What does this program print? Console.WriteLine(2 * 3 + 4 * 5);

    Answer

    26

    Six plus twenty, because the multiplications happen first.

  10. Why is the End token a token and not a null?

    Answer

    The parser reads Current without a null check, and End carries the position of the end

    A marker with a position keeps every step of the parser the same shape.

The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev