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
- text[start..i] is the range operator: the substring from start up to but not including i. It copies the characters, which is right here, because the token keeps its text.
- double.Parse with CultureInfo.InvariantCulture reads the point as a decimal separator on every machine. A culture that writes 3,5 would parse the same text differently, and a calculator must not depend on the locale of the reader.
- The position of a token is its index in the original line, not in the token list. That is the number a message about a bad character quotes.
- TokenKind.End has a position too: the length of the line, which is one past its last character, so an error at the end of the input points where the missing text would go.
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
- Add a token kind for an identifier and lex a letter run as one token.
- Lex a number with an exponent, 1e3, and decide whether the lexer or the parser should handle it.
- Print the character at the position of every token, so the token list and the original line can be compared by eye.
- 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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
What does this program print?
Console.WriteLine("12/3".Length);Answer
4
Two digits, a slash and a digit are four characters.
-
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