Capstone B: the tokens

The second capstone is a calculator: a line of text goes in, a number comes out, and every step between them is a lesson. The first step is the lexer, which turns characters into tokens. A parser cannot work on characters, because 12 is two characters and one number, and a minus is either a sign or a subtraction depending on what came before it.

The lexer

The lexer walks the text once with an index. Whitespace is skipped, a run of digits and points becomes one number token, a single operator becomes its own token, and the end of the text is a token as well, so the parser never has to ask whether the list is over. The whole program lexes two inputs and then one it must refuse:

Console.WriteLine("calc 1.0"); Show("1 + 2 * (3.5 - 4) / 5"); Show("12/3"); try { Show("1 $ 2"); } catch (FormatException ex) { Console.WriteLine($"error: {ex.Message}"); } static void Show(string input) { Console.WriteLine($"input [{input}]"); foreach (var token in Lex(input)) { Console.WriteLine($" {token}"); } } 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; } enum TokenKind { Number, Operator, End, } record Token(TokenKind Kind, double Value, int Position, string Text) { public override string ToString() => Kind switch { TokenKind.Number => $"{Position}: Number {Text} = {Value}", TokenKind.Operator => $"{Position}: Operator {Text}", _ => $"{Position}: End", }; }

dotnet run
echo "status: $?"

calc 1.0
input [1 + 2 * (3.5 - 4) / 5]
  0: Number 1 = 1
  2: Operator +
  4: Number 2 = 2
  6: Operator *
  8: Operator (
  9: Number 3.5 = 3.5
  13: Operator -
  15: Number 4 = 4
  16: Operator )
  18: Operator /
  20: Number 5 = 5
  21: End
input [12/3]
  0: Number 12 = 12
  2: Operator /
  3: Number 3 = 3
  4: End
input [1 $ 2]
error: unexpected '$' at 2
status: 0

The second input, 12/3, has no spaces at all and still gives three tokens and an end marker. The first one shows why the position of a token is worth carrying: the number 3.5 starts at index nine, which is where an error about that number would point.

Positions

The token is a record, and its ToString is declared inside the record itself: a record generates a ToString that lists its members, and a record with its own method replaces that. That is why the output reads 0: Number 1 = 1 and not the four members of the record with their names.

A character the lexer refuses

The third input holds a dollar sign, which is not part of the language. The lexer throws a FormatException with the character and its position, and the program catches it and prints the message. The exception carries the position in the text of its message, which lesson 124 replaces with an exception that carries it as a property, so the caller can draw a caret under the character instead of repeating the message.

The next lesson takes the token list and builds a tree from it, with the precedence of multiplication over addition written as three methods.

Exercises

  1. Add a token kind for an identifier and lex a letter run as one token.
  2. Lex a number with an exponent, 1e3, and decide whether the lexer or the parser should handle it.
  3. Print the character at the position of every token, so the token list and the original line can be compared by eye.
  4. Make the lexer skip a comment that starts with # to the end of the line.

Questions

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

  1. What does a lexer produce?

    Answer

    A list of tokens, each with a kind, a value and a position

    The parser is the next step, and it reads the tokens, not the text.

  2. Why does the token list end with TokenKind.End?

    Answer

    So the parser never has to check whether the list is over

    A marker with a position is simpler than an index check at every step.

  3. What does this program print? var text = "abc"; Console.WriteLine(text[0..2]);

    Answer

    ab

    The range starts at zero and stops before index two.

  4. What is the position of the number 3.5 in 1 + 2 * (3.5 - 4) / 5?

    Answer

    9

    The measured token line reads 9: Number 3.5 = 3.5.

  5. What does this program print? Console.WriteLine(double.Parse("3.5", System.Globalization.CultureInfo.InvariantCulture));

    Answer

    3.5

    The invariant culture reads the point as the decimal separator.

  6. Why is the position of a token kept at all?

    Answer

    An error message points at the character of the original line

    Lesson 124 draws a caret under the position.

  7. What does this program print? object value = 12; Console.WriteLine(value.GetType().Name);

    Answer

    Int32

    GetType answers the runtime type of the boxed value, which is Int32.

  8. Which character ends the first input in the token list?

    Answer

    The end of the text, token at 21

    The measured End token of the first input is at 21, the length of the line.

  9. What does this program print? Console.WriteLine("12/3".Length);

    Answer

    4

    Two digits, a slash and a digit are four characters.

  10. What does the lexer do with whitespace?

    Answer

    It skips it, because the parser does not need it

    Positions come from the original text, so the spaces are still where they were.

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