No code in this step. If you already know what a token is, tick it and move on.
A computer reading source code has the same problem you have reading a sentence. The text arrives as one long run of characters, and before you can do anything with it you have to chop it into words.
Take 12 + 3. That is six characters. But 1 and
2 belong together. They are one number, twelve. And the space in the
middle means nothing at all. It only sits there so people can read the line. So six
characters really come down to three pieces: the number 12, a plus sign, and the number
3. Those pieces are called tokens, and the part of the compiler that produces
them is the lexer.
Every stage after this one works on tokens instead of characters, which is the reason this stage exists. The parser in chapter two never has to think about spaces or about whether two digits belong together. That problem got solved here, once.
A lexer does not care whether your program makes sense. Feed it
+ + ) 9 and it will happily hand back PLUS, PLUS, RPAREN, NUMBER. That
is not a bug. Deciding whether an arrangement of tokens is legal belongs to the
parser, and keeping those two jobs apart is what keeps both of them small.
Checkpoint
Make a folder to work in, with somewhere to put the compiled output:
Start with the header file, because everything else refers back to it.
src/lexer.h · new file
/* Token definitions and the lexer's public interface.A header file is a list of promises. It says what exists, so other files can use it without seeing how it works.
The lexer turns source text into a flat stream of tokens. */ #ifndef IZVOR_LEXER_HThis and the next line are an include guard. If two files both include this header, the second time through IZVOR_LEXER_H is already defined and everything down to #endif gets skipped. Without it you get "redefinition" errors that are confusing the first time you see them.
#define IZVOR_LEXER_H typedef enum {An enum is a list of names for numbers. I never care what the numbers are. I care that the compiler will not let me confuse one for another, and that it can warn me when I forget to handle one.
TOK_NUMBER,A run of digits, like 12.
TOK_PLUS, TOK_MINUS, TOK_STAR,Called STAR and not MULTIPLY on purpose. The lexer knows it saw the character *. It has no idea yet whether that means multiplication, and it is not its job to guess.
TOK_SLASH, TOK_LPAREN, TOK_RPAREN, TOK_EOF,End of file. The input running out is a real event that the parser needs to be told about, so it gets a token like everything else instead of being a special case.
TOK_ERRORSomething I do not recognise, like @. Giving it a token type instead of crashing is a decision I will come back to in step 9.
} TokenType;Checkpoint
Nothing to run yet. The file will not compile on its own until step 4.
Four fields. The second and third are the most important design decision in this chapter, and it affects every file I write after it.
src/lexer.h · under the enum
typedef struct {A struct is a box holding several values that belong together. typedef just means I can write Token later instead of struct Token.
TokenType type;Which of the nine kinds this is.
const char *start;A pointer to where this token begins inside the original source string. Not a copy of the text. A finger pointing at it.
int length;How many characters belong to it. Together with start, these two say "the text runs from here, this far" without ever copying anything.
long value;For a number, the actual numeric value. For everything else this sits at zero and goes unused. A union would be tidier and I noted that as a possible cleanup rather than doing it now.
} Token;
The obvious thing is to give each token its own copy of its text with
malloc and strcpy. I did not, and there are two reasons.
One, an allocation for every token is a lot of allocations, and every one of them is something you can forget to free. Pointing at text that already exists costs nothing and leaks nothing.
Two, and this is the one that pays off later, keeping the position means I can find my way back to the source. In chapter three I print the exact line an error happened on with a caret under the exact character. That is only possible because a token still knows where it came from. A copied string would have thrown that away.
There are two costs, and you should know both. A token is only valid while the source
string is still alive, so the source has to outlive every token made from it. And the
text is not zero terminated at the end of the token, so ordinary string functions
like strcmp will read straight past it. Chapter four runs into that
head first.
Checkpoint
The whole lexer is two fields. That is not a simplification for teaching, that is the real thing.
src/lexer.h · finish the file
typedef struct { const char *src;The whole program text. The lexer borrows it and never writes to it, which is what const says.
int pos;How far in it has read. That is the entire state. No buffer, no list of tokens, no history.
} Lexer; const char *token_type_name(TokenType type);Turns a token type into a printable name. Used by error messages and by the debugging tool in step 10.
void lexer_init(Lexer *lx, const char *src);Token lexer_next(Lexer *lx);The only function that matters. Call it, get one token. Call it again, get the next one. It hands back a Token by value, not a pointer, because a Token is four small fields and copying it is cheaper than managing where it lives.
#endifCloses the include guard from step 2.
Notice what is missing. There is no function that gives you all the tokens at once, and nowhere that stores them. The lexer produces one token at a time and forgets it immediately. The parser asks for the next one when it wants it. That means the memory used does not grow with the size of the file, and it means there is no rewind. If the parser needs to look at a token twice, the parser has to hold onto it. Chapter two does exactly that, with a single field.
Checkpoint
The header should now compile by itself:
New file. This function is boring and it is the one I use most while debugging.
src/lexer.c · new file
/* Lexer implementation: scans characters into tokens. Handles integer literals, + - * / and parentheses; anything else becomes TOK_ERROR rather than aborting the scan. */ #include <ctype.h>For isspace in step 7. Angle brackets mean a system header.
#include "lexer.h"Quotes mean my own file, sitting next to this one.
const char *token_type_name(TokenType type) {Returns a pointer to a string literal. Those live for the whole run of the program, so handing the address out is safe and there is nothing to free.
switch (type) { case TOK_NUMBER: return "NUMBER";One case per type, all nine of them, in the same shape.
/* ... the other seven ... */ case TOK_ERROR: return "ERROR"; } return "???";Unreachable if every case is covered, but C wants a return on every path out of the function. Putting the fallback here rather than in a default: is the point of the trap below.
}
It looks wrong to write a switch over an enum with no default:. It is
the most useful thing in this file.
With no default, clang checks that you handled every value in the enum and warns you
by name about any you missed. That warning is how I find every place in the compiler
that needs updating each time I add a token type, and I add token types for the rest
of the project. Write default: return "???"; instead and the compiler
goes quiet forever, and the next time you add a token you find out by seeing
??? in an error message six months later.
Checkpoint
The first test only checks these names. Write it yourself or take it from the repo:
-fsanitize=undefined is worth turning on now and leaving on. It makes
things like reading past the end of an array crash loudly with the line number
instead of quietly returning garbage.
Four tiny functions. Everything after this is written in terms of them, so the rest of
the file never touches lx->pos directly.
src/lexer.c · under token_type_name
void lexer_init(Lexer *lx, const char *src) { lx->src = src;lx->src means "follow the pointer, then take the src field". Same as (*lx).src, just easier to read.
lx->pos = 0;} static char peek(const Lexer *lx) {static makes the function private to this file. Nothing outside can call it, and no other file can accidentally define something with the same name.
return lx->src[lx->pos];Look at the current character without moving. Safe at the end of the string, because C strings end with a zero byte and reading that is legal. That zero is what tells me the input is finished.
} static char advance(Lexer *lx) {Note there is no const here. This one changes the lexer, and the missing const is how the type says so.
return lx->src[lx->pos++];Returns the current character, then moves past it. The ++ after the name means "use the old value, then add one". If it were ++lx->pos you would skip a character and the bug would be very annoying to find.
} static Token make_token(const Lexer *lx, TokenType type, int start_pos) {Builds a finished token. Every branch in step 8 and 9 ends by calling this, which is why they all agree about how start and length get filled in.
Token t; t.type = type; t.start = lx->src + start_pos;Pointer arithmetic. The address of the string plus an offset is the address of that character. This is the finger from step 3.
t.length = lx->pos - start_pos;Where it stopped minus where it started. The caller does not pass a length, the lexer works it out from how far it moved, so the two can never disagree.
t.value = 0;Zeroed here so the number branch is the only place that ever has to set it.
return t;}Checkpoint
Expect warnings that peek, advance and make_token
are unused. Nothing calls them yet. They go away in step 8.
Two more small ones.
src/lexer.c · under make_token
static int is_digit(char c) {Returns int rather than a boolean because C did not have a real one until C99, and plain int is the convention the rest of this file follows.
return c >= '0' && c <= '9';Digits sit next to each other in order in the character set, so this really is two comparisons. Writing it myself instead of calling isdigit keeps the language's own alphabet out of the reach of the operating system's locale settings.
} static void skip_whitespace(Lexer *lx) {Spaces, tabs and newlines carry no meaning in this language, so they get thrown away before scanning starts rather than becoming tokens nobody wants.
while (isspace((unsigned char)peek(lx))) advance(lx);The (unsigned char) cast is not decoration. isspace is undefined behaviour if you hand it a negative number, and a plain char can be negative on some machines for bytes above 127. This is the correct way to call every function in ctype.h.
}Treating a newline as ordinary whitespace is a language design decision, and I am making it right here on line 6. It means izvor statements cannot be ended by pressing return, the way they are in Python. Chapter four comes back to what that costs.
Checkpoint
The function everything else exists to support. It is shorter than you would guess.
src/lexer.c · the first half of lexer_next
Token lexer_next(Lexer *lx) { skip_whitespace(lx);Always first. By the time the next line runs, the lexer is sitting on something that matters.
int start = lx->pos;Remember where this token begins, because make_token needs it at the end and lx->pos will have moved by then.
char c = peek(lx);Look at the first character without consuming it. One character is enough to decide what kind of token this is.
if (c == '\0') return make_token(lx, TOK_EOF, start);The zero byte at the end of the string. Note that it is not consumed, so calling lexer_next again just returns EOF again forever. The parser relies on that.
if (is_digit(c)) { long value = 0; while (is_digit(peek(lx))) value = value * 10 + (advance(lx) - '0');This one line is the whole of number parsing. Read it right to left. advance gives back a character like '7'; subtracting '0' turns that character into the number 7, because the digits are consecutive. Then value * 10 + digit shifts what you had over one place and adds the new digit. Scanning "123" walks value through 1, then 12, then 123.
Token t = make_token(lx, TOK_NUMBER, start); t.value = value;The only place value is ever set. Every other token leaves it at the zero that make_token put there.
return t; }
Line 11 has no overflow check. Feed it forty digits and value runs past
what a long can hold, which in C is undefined behaviour. Under the
sanitizer build it aborts loudly, which is at least honest.
I left it because fixing it properly means deciding what the language should do about a number that is too big, and that is a language design question I did not want to answer in chapter one. It is written down in the repo's roadmap as real debt rather than pretended away. Knowing where your compiler is wrong is worth more than a compiler you think is right.
Checkpoint
The rest of the function, and the decision in its last line.
src/lexer.c · the second half of lexer_next
advance(lx);Everything left is a single character, so consume it before the switch. That is why make_token below sees a length of one.
switch (c) {Switching on c, which was read before the advance, so it still holds the character just consumed.
case '+': return make_token(lx, TOK_PLUS, start); case '-': return make_token(lx, TOK_MINUS, start); case '*': return make_token(lx, TOK_STAR, start); case '/': return make_token(lx, TOK_SLASH, start); case '(': return make_token(lx, TOK_LPAREN, start); case ')': return make_token(lx, TOK_RPAREN, start); } return make_token(lx, TOK_ERROR, start);Anything I do not recognise. The character was already consumed on line 1, which matters more than it looks.
}
The easy thing on line 10 is to print "unexpected character" and call
exit. I made it hand back a token instead, and the reason is on line 1.
Because the bad character was consumed, the lexer is now sitting on whatever came
after it, and the next call carries on normally.
So 1 @ 2 produces NUMBER, ERROR, NUMBER, EOF. The scan never stops. That
lets the compiler eventually report several problems in one run instead of making you
fix them one at a time, and it means the lexer has no way to kill the program, which
makes it much easier to test. A lexer that calls exit cannot be tested
at all without starting a separate process.
The cost is that an error token has to be handled somewhere downstream, or a bad character turns into a confusing parser message. Chapter three is where that gets handled properly.
Checkpoint
Thirty lines that are not part of the compiler and that I have used more than anything else in it.
src/lexer_main.c · new file
Tests tell you whether something is right. This tells you what it is actually doing, which is a different and sometimes more useful thing. It takes an expression and prints the token stream.
Lexer lx; lexer_init(&lx, argv[1]);&lx is the address of lx. The function takes a pointer so it can write into the thing you own, rather than a copy.
for (;;) {A loop with no condition, which means forever. The exit is inside.
Token t = lexer_next(&lx); if (t.type == TOK_EOF) { printf("EOF\n"); break; } printf("%-8s '%.*s'", token_type_name(t.type), t.length, t.start);%.*s is the piece worth learning. It prints a string with the length supplied as an argument, so it stops after exactly t.length characters. That is how you print a token's text when the text is not zero terminated. %-8s just pads the name to eight columns so the output lines up.
if (t.type == TOK_NUMBER) printf(" value=%ld", t.value); printf("\n"); }Checkpoint
Try "1 @ 2" too, and watch the scan carry on past the ERROR token.
Those clang commands get old fast. This is the last housekeeping in the chapter.
Makefile · new file, in the project root
A Makefile is a list of named recipes. make test runs the one called test.
The only thing that will catch you out is that the indented lines must start with a
real tab character, not spaces, and make will tell you "missing separator" if you get
it wrong.
CC := clangA variable. Used as $(CC) below.
CFLAGS := -std=c11 -Wall -Wextra -g -fsanitize=undefined-Wall -Wextra turn on the warnings that catch real mistakes, and they are the reason the missing default case in step 5 is useful. -fsanitize=undefined is the one that turns quiet corruption into a loud crash with a line number.
TEST_SRC := $(wildcard tests/test_*.c)Finds the test files by name. It means adding a new test is just adding a file, with nothing to wire up here, which removes the main excuse for not writing one.
The full Makefile in the repo also has targets for golden tests, fuzzing and the sanitizer builds. Those all belong to chapter three, so do not worry about them yet.
Checkpoint
If you are building from scratch rather than working in a clone, the repo's Makefile expects files that do not exist yet, so keep using the clang commands until chapter three.