Capstone B: testing and extending

The calculator is finished as a program, and the last lesson proves it and then extends it. The proof is a table of expressions with the value each one must produce, and the extension is a name in place of a number: the lexer learns one more character rule, the parser one more node, and the evaluator a dictionary to look the name up in.

A table of expressions

Each row is an expression and the number it must evaluate to. The driver parses, evaluates and compares, prints one line per row and returns one when any row failed, which is the status that makes the table a test instead of a demonstration:

var variables = new Dictionary<string, double> { ["x"] = 3, ["y"] = 4 }; var cases = new (string Text, double Expected)[] { ("1 + 2 * 3", 7), ("(1 + 2) * 3", 9), ("-2 + 10 / 5", 0), ("x * y", 12), ("x - y * 2", -5), ("1 / 4", 0.25), }; var failed = 0; foreach (var (text, expected) in cases) { var actual = Eval(Parse(Lex(text)), variables); var ok = Math.Abs(actual - expected) < 1e-9; if (!ok) { failed++; } Console.WriteLine($"{(ok ? "ok " : "FAIL")} {text,-14} expected {expected,6} got {actual,6}"); } Console.WriteLine($"cases {cases.Length} failed {failed}"); return failed == 0 ? 0 : 1; static double Eval(Node node, Dictionary<string, double> variables) => node switch { Number number => number.Value, Identifier identifier => variables.TryGetValue(identifier.Name, out var value) ? value : throw new SyntaxException(identifier.Position, $"unknown name '{identifier.Name}'"), Unary unary => -Eval(unary.Operand, variables), Binary binary => binary.Op switch { '+' => Eval(binary.Left, variables) + Eval(binary.Right, variables), '-' => Eval(binary.Left, variables) - Eval(binary.Right, variables), '*' => Eval(binary.Left, variables) * Eval(binary.Right, variables), _ => Eval(binary.Left, variables) / Eval(binary.Right, variables), }, _ => throw new SyntaxException(0, "unknown node"), }; 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 (char.IsLetter(c)) { var start = i; while (i < text.Length && char.IsLetter(text[i])) { i++; } tokens.Add(new Token(TokenKind.Identifier, 0, start, text[start..i])); continue; } if (c is '+' or '-' or '*' or '/' or '(' or ')') { tokens.Add(new Token(TokenKind.Operator, 0, i, c.ToString())); i++; continue; } throw new SyntaxException(i, $"unexpected '{c}'"); } tokens.Add(new Token(TokenKind.End, 0, text.Length, "end")); return tokens; } static Node Parse(List<Token> tokens) => Parser.Parse(tokens); enum TokenKind { Number, Identifier, Operator, End, } record Token(TokenKind Kind, double Value, int Position, string Text); sealed class SyntaxException(int position, string message) : FormatException(message) { public int Position { get; } = position; } abstract record Node; sealed record Number(double Value) : Node; sealed record Identifier(string Name, int Position) : 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.Identifier: _index++; return new Identifier(token.Text, token.Position); 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 SyntaxException(token.Position, "expected a number"); } } private void Expect(string text) { if (Current.Kind != TokenKind.Operator || Current.Text != text) { throw new SyntaxException(Current.Position, $"expected '{text}'"); } _index++; } }

dotnet run
echo "status: $?"

ok   1 + 2 * 3      expected      7 got      7
ok   (1 + 2) * 3    expected      9 got      9
ok   -2 + 10 / 5    expected      0 got      0
ok   x * y          expected     12 got     12
ok   x - y * 2      expected     -5 got     -5
ok   1 / 4          expected   0.25 got   0.25
cases 6 failed 0
status: 0

The six rows cover the three shapes of the grammar: a mixed expression with precedence, a parenthesised one, a unary minus, a division that is not whole, and one row with a name in it, from the extension the next section explains.

Comparing doubles

The comparison is Math.Abs(actual - expected) < 1e-9 and not actual == expected, because two double values that a person would call equal can differ in their last bit, as lesson 015 measured with additions of 0.1. Every expected value of this table happens to be exact, so the tolerance costs nothing here; it is there for the row a reader will add tomorrow, where a comparison with == would fail for no reason.

An extension: names

A name is a letter run, so the lexer gets one more rule and one more token kind; the parser turns the token into an Identifier node that keeps the name and the position; and the evaluator takes a dictionary of names and values. The structure of the program does not change, which is the point of the three separate pieces: a new kind of thing in the language touches one method in each of them.

An unknown name is an error with a position, like an unknown character, and it is thrown from the evaluator rather than from the parser, because only the evaluator knows which names exist.

Using the extension

The second program uses the extension on its own: an expression over two names with values, and one name that is not in the dictionary:

var variables = new Dictionary<string, double> { ["speed"] = 60, ["hours"] = 3 }; Console.WriteLine($"speed * hours + 10 = {Eval(Parse(Lex("speed * hours + 10")), variables)}"); try { Console.WriteLine(Eval(Parse(Lex("speed * minutes")), variables)); } catch (SyntaxException ex) { Console.WriteLine($"error at {ex.Position}: {ex.Message}"); } static double Eval(Node node, Dictionary<string, double> variables) => node switch { Number number => number.Value, Identifier identifier => variables.TryGetValue(identifier.Name, out var value) ? value : throw new SyntaxException(identifier.Position, $"unknown name '{identifier.Name}'"), Unary unary => -Eval(unary.Operand, variables), Binary binary => binary.Op switch { '+' => Eval(binary.Left, variables) + Eval(binary.Right, variables), '-' => Eval(binary.Left, variables) - Eval(binary.Right, variables), '*' => Eval(binary.Left, variables) * Eval(binary.Right, variables), _ => Eval(binary.Left, variables) / Eval(binary.Right, variables), }, _ => throw new SyntaxException(0, "unknown node"), }; 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 (char.IsLetter(c)) { var start = i; while (i < text.Length && char.IsLetter(text[i])) { i++; } tokens.Add(new Token(TokenKind.Identifier, 0, start, text[start..i])); continue; } if (c is '+' or '-' or '*' or '/' or '(' or ')') { tokens.Add(new Token(TokenKind.Operator, 0, i, c.ToString())); i++; continue; } throw new SyntaxException(i, $"unexpected '{c}'"); } tokens.Add(new Token(TokenKind.End, 0, text.Length, "end")); return tokens; } static Node Parse(List<Token> tokens) => Parser.Parse(tokens); enum TokenKind { Number, Identifier, Operator, End, } record Token(TokenKind Kind, double Value, int Position, string Text); sealed class SyntaxException(int position, string message) : FormatException(message) { public int Position { get; } = position; } abstract record Node; sealed record Number(double Value) : Node; sealed record Identifier(string Name, int Position) : 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.Identifier: _index++; return new Identifier(token.Text, token.Position); 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 SyntaxException(token.Position, "expected a number"); } } private void Expect(string text) { if (Current.Kind != TokenKind.Operator || Current.Text != text) { throw new SyntaxException(Current.Position, $"expected '{text}'"); } _index++; } }

dotnet run
echo "status: $?"

speed * hours + 10 = 190
error at 8: unknown name 'minutes'
status: 0

The error is at position eight, which is where minutes begins in speed * minutes: five letters, a space, the star and another space come before it. That is the same position the caret of lesson 124 would point at, and it is why the identifier node carries one.

Capstone B ends here. Capstone C takes the other direction: not one program that reads a line and answers it, but many jobs at once, a channel between them, and a shutdown that waits for every worker.

Exercises

  1. Add rows for x / y and x + y * 2 to the table with the values the dictionary gives.
  2. Add an assignment form, x = 3, as a statement the REPL understands, and make it change the dictionary.
  3. Add a function call min(a, b) with one builtin and one test row for it.
  4. Change the table to a text file, one case per line, and report the file line of a failing case.

Questions

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

  1. Why is a tolerance used in the table?

    Answer

    Two doubles that should be equal can differ in the last bit

    An absolute tolerance of 1e-9 is large enough for a wrong operator to fail.

  2. What does the driver return when a row fails?

    Answer

    1

    return failed == 0 ? 0 : 1 is the policy of the driver.

  3. What does this program print? Console.WriteLine(Math.Abs(0.1 + 0.2 - 0.3) < 1e-9);

    Answer

    True

    The difference is about 5.5e-17, far below the tolerance.

  4. Which piece of the calculator turns a letter run into a token?

    Answer

    The lexer

    The parser receives an Identifier token and builds the node.

  5. What does this program print? var values = new Dictionary<string, double> { ["x"] = 3 }; Console.WriteLine(values.TryGetValue("y", out var y));

    Answer

    False

    TryGetValue answers whether the key was found and writes the value to the out parameter.

  6. Where is an unknown name detected?

    Answer

    In the evaluator, because only it knows which names have values

    The measured error comes from the lookup in the dictionary.

  7. What does this program print? Console.WriteLine("speed * minutes".IndexOf("minutes"));

    Answer

    8

    That is the position the measured error reports.

  8. What does one row of the table hold?

    Answer

    An expression and its expected value

    The tuple type is (string Text, double Expected).

  9. What does this program print? var total = 0; foreach (var value in new[] { 1, 2, 3 }) { total += value; } Console.WriteLine(total);

    Answer

    6

    The loop adds the three values.

  10. What makes this lesson the end of the capstone?

    Answer

    A table of cases proves the parser and the evaluator together, on the program a reader can run

    Six measured rows cover the grammar and the extension, and the status says the table passed.

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