Capstone B: the syntax tree

The parser of the previous lesson builds a tree and the page only reported its root, because the tree had no readable form. This lesson gives it one: every operator wrapped in parentheses, so the text of the tree states the order of evaluation without a precedence table. Then the text is parsed again, and the result is compared with the tree it came from.

The tree

The tree is four records: an abstract Node, a Number, a Unary for the sign and a Binary for the five operators. A record is the right shape here because two trees built from the same input must compare equal by their contents and not by their address, which is what record equality does.

var inputs = new[] { "1 + 2 * 3", "(1 + 2) * 3", "2 * 3 + 4 * 5", "-(2 + 3) * 4", "10 / (2 - 2)", }; foreach (var input in inputs) { var tree = Parse(Lex(input)); var text = Describe(tree); var again = Parse(Lex(text)); Console.WriteLine($"{input,-14} {text,-24} same {again.Equals(tree)}"); } var sample = Parse(Lex("1 + 2")); Console.WriteLine($"record ToString {sample}"); Console.WriteLine($"printed {Describe(sample)}"); var a = Parse(Lex("1+2")); var b = Parse(Lex("(1 + 2)")); Console.WriteLine($"two spellings of one tree equal {a.Equals(b)}"); static string Describe(Node node) => node switch { Number number => number.Value.ToString(System.Globalization.CultureInfo.InvariantCulture), Unary unary => $"-{Describe(unary.Operand)}", Binary binary => $"({Describe(binary.Left)} {binary.Op} {Describe(binary.Right)})", _ => "?", }; 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: $?"

1 + 2 * 3      (1 + (2 * 3))            same True
(1 + 2) * 3    ((1 + 2) * 3)            same True
2 * 3 + 4 * 5  ((2 * 3) + (4 * 5))      same True
-(2 + 3) * 4   (-(2 + 3) * 4)           same True
10 / (2 - 2)   (10 / (2 - 2))           same True
record ToString  Binary { Op = +, Left = Number { Value = 1 }, Right = Number { Value = 2 } }
printed          (1 + 2)
two spellings of one tree equal True
status: 0

Five inputs are parsed, printed and parsed again, and the same column is the comparison of the two trees. The last two lines are the two spellings of one addition: the printer ignores the spaces of the input and the redundant parentheses, so both give the same text and the same tree.

A readable form

Describe is a switch expression over the three node types. A number prints with the invariant culture, a unary node prints its operator before its operand, and a binary node prints both children inside one pair of parentheses with the operator between them.

The round trip

Parsing the printed text again gives a tree that must equal the original, and the comparison is the record equality of the whole structure: each node type compares its own members, and a binary node compares both children recursively. Two separately parsed trees of the same text are equal, and so are two spellings that differ only in spaces or in parentheses that the grammar does not need.

A round trip is the cheapest shape of a test for a printer: the parser was written first and is trusted, so the printer is checked against it instead of against a table of expected strings. If the printer dropped a node, the second tree would differ and the column would read False.

The ToString of a record

The line that begins record ToString is what a record prints without any help: Binary { Op = +, Left = Number { Value = 1 }, Right = ... }. It lists the members, which is useful in a debugger and wrong for a reader of the expression. The printer is therefore a method of its own and not an override: a record that overrides ToString would also change the text a debugger shows, and the two uses want different text.

The next lesson evaluates the tree. Division by zero in double is not an exception, so the evaluator has to decide what to do with Infinity and NaN.

Exercises

  1. Print without the outermost pair of parentheses and check that the round trip still holds.
  2. Add a printer that writes the expression with as few parentheses as possible, using the precedence of the operators.
  3. Print the tree with indentation, one node per line, and compare it with the record ToString.
  4. Compare two trees of the same shape but different numbers and explain which member makes the equality false.

Questions

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

  1. What does the printer put around every operation?

    Answer

    A pair of parentheses, so the text needs no precedence table

    The measured text is (1 + (2 * 3)).

  2. Why is the tree made of records?

    Answer

    Two trees of the same contents compare equal by value

    The round trip compares the old tree with the new one by equality of records.

  3. What does this program print? Console.WriteLine(new Point(1, 2) == new Point(1, 2)); record Point(int X, int Y);

    Answer

    True

    A record compares its members, and both points hold the same numbers.

  4. Which text does 1 + 2 * 3 print as?

    Answer

    (1 + (2 * 3))

    The multiplication is the child of the addition, so it is printed inside it.

  5. What does this program print? Console.WriteLine(new[] { 1, 2 } == new[] { 1, 2 });

    Answer

    False

    An array compares by reference, unlike a record.

  6. What does the same column of the output prove?

    Answer

    That parsing the printed text gives a tree equal to the original

    Five True lines are five successful round trips.

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

    Answer

    1 + 2

    Trim removes the characters it is given from both ends.

  8. Why is the printer not an override of ToString on the node types?

    Answer

    A record has a useful ToString for a debugger, and the expression text is a different use

    The measured record line shows the member dump the debugger wants.

  9. What does this program print? Console.WriteLine(1.5.ToString(System.Globalization.CultureInfo.InvariantCulture));

    Answer

    1.5

    The invariant culture writes the point, whatever the machine locale is.

  10. What is the fixed point of a round trip?

    Answer

    The printed text parses to a tree that prints to the same text

    Five inputs print a text whose second printing is the same string.

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

Banner image