# C99 - Lexer for the Monkey Programming Language from the book "Writing An Interpreter In Go"

Below is a C version of a lexer for the Monkey programming language, originally written in Go, as presented in the book Writing An Interpreter In Go.

LOC: 371. (Excluding the tests.)

## Language:

Copy pasting from the book:

Here is how we bind values to names in Monkey:

let age = 1;
let name = "Monkey";
let result = 10 * (20 / 2);


Besides integers, booleans and strings, the Monkey interpreter we’re going to build will also support arrays and hashes. Here’s what binding an array of integers to a name looks like:

let myArray = [1, 2, 3, 4, 5];


And here is a hash, where values are associated with keys:

let thorsten = {"name": "Thorsten", "age": 28};


Accessing the elements in arrays and hashes is done with index expressions:

myArray[0] // => 1
thorsten["name"] // => "Thorsten"


The let statements can also be used to bind functions to names. Here’s a small function that adds two numbers:

let add = fn(a, b) { return a + b; };


But Monkey not only supports return statements. Implicit return values are also possible, which means we can leave out the return if we want to:

let add = fn(a, b) { a + b; };


And calling a function is as easy as you’d expect:

add(1, 2);


A more complex function, such as a fibonacci function that returns the Nth Fibonacci number, might look like this:

let fibonacci = fn(x) {
if (x == 0) {
0
} else {
if (x == 1) {
1
} else {
fibonacci(x - 1) + fibonacci(x - 2);
}
}
};


Note the recursive calls to fibonacci itself! Monkey also supports a special type of functions, called higher order functions. These are functions that take other functions as arguments. Here is an example:

let twice = fn(f, x) { return f(f(x)); };
let addTwo = fn(x) { return x + 2; };


## Directory Structure:

.
├── lexer
│   ├── lexer.c
│   └── lexer.h
├── Makefile
├── repl
│   └── repl.c
├── struct.txt
├── tests
│   ├── bin
│   └── lexer_test.c
├── token
│   ├── token.c
│   └── token.h
└── util
├── util.c
└── util.h

6 directories, 11 files


## Code:

lexer.h:

#ifndef LEXER_H
#define LEXER_H 1

#include "../token/token.h"

typedef struct lexer {
const char *input;
size_t      input_len;
size_t      pos;        /* Current position in input (points to current char). */
size_t      read_pos;   /* Current reading position in input (after current char). */
char        ch;         /* Current char under examination. */
} Lexer;

Lexer lexer_new(const char input[static 1]);
Token lexer_next(Lexer l[static 1]);

#endif /* LEXER_H */


lexer.c:

// TODO: Change the API to hide the lexer's internals.

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "lexer.h"
#include "../token/token.h"
#include "../util/util.h"

{
}

static char peek_char(Lexer l)
{
}

static int is_letter(char ch)
{
return ch == '_' || isalpha((unsigned char)ch) != 0;
}

static const char *read_ident(Lexer l[static 1], size_t len[static 1])
{
const size_t orig_pos = l->pos;
for (; is_letter(l->ch) != 0; read_char(l)) ;
*len = l->pos - orig_pos;
return l->input + orig_pos;
}

static const char *read_int(Lexer l[static 1], size_t len[static 1])
{
const size_t orig_pos = l->pos;
for (; isdigit((unsigned char)l->ch) != 0; read_char(l)) ;
*len = l->pos - orig_pos;
return l->input + orig_pos;
}

static const char *read_string(Lexer l[static 1], size_t len[static 1])
{
/* Monkey doesn't support escape characters.
* TODO: Perhaps return NULL on EOF.
*/
const size_t orig_pos = l->pos + 1;

do {
} while (l->ch != '"' && l->ch != '\0');

*len = l->pos - orig_pos;
return l->input + orig_pos;
}

static void skip_whitespace(Lexer l[static 1])
{
for (; isspace((unsigned char)l->ch) != 0; read_char(l)) ;
}

Lexer lexer_new(const char input[static 1])
{
Lexer l = {
.input = input,
.input_len = strlen(input),
};
return l;
}

Token lexer_next(Lexer l[static 1])
{
Token t;
skip_whitespace(l);

switch (l->ch) {
case '=':
if (peek_char(*l) == '=') {
t = token_new(TOK_EQ, "==");
} else {
t = token_new(TOK_ASSIGN, "=");
}
break;

case '+':
t = token_new(TOK_PLUS, "+");
break;

case '-':
t = token_new(TOK_MINUS, "-");
break;

case '*':
t = token_new(TOK_ASTERISK, "*");
break;

case '/':
t = token_new(TOK_SLASH, "/");
break;

case '!':
if (peek_char(*l) == '=') {
t = token_new(TOK_NOT_EQ, "!=");
} else {
t = token_new(TOK_BANG, "!");
}
break;

case '<':
t = token_new(TOK_LT, "<");
break;

case '>':
t = token_new(TOK_GT, ">");
break;

case ',':
t = token_new(TOK_COMMA, ",");
break;

case ';':
t = token_new(TOK_SEMICOLON, ";");
break;

case ':':
t = token_new(TOK_COLON, ":");
break;

case '(':
t = token_new(TOK_LPAREN, "(");
break;

case ')':
t = token_new(TOK_RPAREN, ")");
break;

case '{':
t = token_new(TOK_LBRACE, "{");
break;

case '}':
t = token_new(TOK_RBRACE, "}");
break;

case '[':
t = token_new(TOK_LBRACKET, "[");
break;

case ']':
t = token_new(TOK_RBRACKET, "]");
break;

case '\0':
t = token_new(TOK_EOF, "");
break;

case '"': {
size_t len = 0;
t.type = TOK_STRING;
t.lit = util_memstr(len, t.lit);
} break;

default:
if (is_letter(l->ch) != 0) {
size_t len = 0;
t.type = token_lookup_ident(len, t.lit);
t.lit = util_memstr(len, t.lit);
return t;
} else if (isdigit((unsigned char)l->ch) != 0) {
size_t len = 0;
t.type = TOK_INT;
t.lit = util_memstr(len, t.lit);
return t;
}
t = token_new(TOK_ILLEGAL, util_memstr(1, &l->ch));
}

return t;
}


token.h:

#ifndef TOKEN_H
#define TOKEN_H 1

#include <stddef.h>

#define FOREACH_TOK(_) \
_(TOK_ILLEGAL)      \
_(TOK_EOF)          \
_(TOK_IDENT)        \
_(TOK_INT)          \
_(TOK_STRING)       \
_(TOK_ASSIGN)       \
_(TOK_PLUS)         \
_(TOK_MINUS)        \
_(TOK_BANG)         \
_(TOK_ASTERISK)     \
_(TOK_SLASH)        \
_(TOK_LT)           \
_(TOK_GT)           \
_(TOK_EQ)           \
_(TOK_NOT_EQ)       \
_(TOK_COMMA)        \
_(TOK_SEMICOLON)    \
_(TOK_COLON)        \
_(TOK_LPAREN)       \
_(TOK_RPAREN)       \
_(TOK_LBRACE)       \
_(TOK_RBRACE)       \
_(TOK_RBRACKET)     \
_(TOK_LBRACKET)     \
_(TOK_FUNCTION)     \
_(TOK_LET)          \
_(TOK_TRUE)         \
_(TOK_FALSE)        \
_(TOK_IF)           \
_(TOK_ELSE)         \
_(TOK_RETURN)       \

#define GEN_ENUM(ENUM) ENUM,

typedef enum {
FOREACH_TOK(GEN_ENUM)
} TokenType;

typedef struct Token {
TokenType   type;
const char *lit;
} Token;

TokenType token_lookup_ident(size_t len, const char ident[static len]);
Token token_new(TokenType type, const char lit[static 1]);
void token_delete(Token t);
const char *token_to_str(TokenType t);

#endif /* TOKEN_H */


token.c:

#include "token.h"

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define GEN_STR(STR) #STR,

static const char *const tok_strs[] = {
FOREACH_TOK(GEN_STR)
};

static const size_t tok_strs_count = sizeof tok_strs / sizeof *tok_strs;

const char *token_to_str(TokenType t)
{
return t < 0 || t > tok_strs_count ? NULL : tok_strs[t];
}

TokenType token_lookup_ident(size_t len, const char ident[static len])
{
static struct keyword {
const char *const kw;
TokenType kw_type;
} const kws[] = {
{ "fn",     TOK_FUNCTION },
{ "let",    TOK_LET      },
{ "true",   TOK_TRUE     },
{ "false",  TOK_FALSE    },
{ "if",     TOK_IF       },
{ "else",   TOK_ELSE     },
{ "return", TOK_RETURN   },
};

static const size_t kws_count = sizeof kws / sizeof kws[0];

for (size_t i = 0; i < kws_count; ++i) {
if (strncmp(ident, kws[i].kw, len) == 0) {
return kws[i].kw_type;
}
}

}

Token token_new(TokenType type, const char lit[static 1])
{
return (Token) {
.type = type,
.lit = lit,
};
}

static bool is_kw(TokenType t)
{
static const TokenType kws[] = {
TOK_FUNCTION,
TOK_LET,
TOK_TRUE,
TOK_FALSE,
TOK_IF,
TOK_ELSE,
TOK_RETURN,
};

return memchr(kws, t, sizeof kws) != NULL;
}

static bool is_dynamic_alloc(TokenType t)
{
return (t == TOK_INT
|| t == TOK_ILLEGAL
|| t == TOK_IDENT
|| t == TOK_STRING
|| is_kw(t));
}

void token_delete(Token t)
{
if (is_dynamic_alloc(t.type)) {
free((char *)t.lit);
}
}


util.h:

#ifndef UTIL_H
#define UTIL_H 1

#include "stdio.h"

char *util_memstr(size_t n, const char s[static n]);
char *util_readline(FILE stream[static 1], size_t len[static 1]);

#endif /* UTIL_H */


util.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *util_memstr(size_t n, const char s[static n])
{
char *const p = malloc(n + 1);

if (p != NULL) {
memcpy(p, s, n);
p[n] = '\0';
}

return p;
}

char *util_readline(FILE stream[static 1], size_t len[static 1])
{
size_t count = 0;
size_t capacity = 0;
char *line = NULL;

for (;;) {
if (count >= capacity) {
capacity = capacity < BUFSIZ ? BUFSIZ : capacity * 2;
char *const tmp = realloc(line, capacity + 1);

if (tmp == NULL) {
free(line);
return NULL;
}

line = tmp;
}

const int c = getc(stream);

if (c == EOF || c == '\n') {
if (c == EOF) {
if (feof(stream)) {
if (!count) {
free(line);
return NULL;
}
/* Return what was read. */
break;
}
free(line);
return NULL;
} else {
break;
}
} else {
line[count] = (char) c;
}
++count;
}

*len = count;
return line;
}


### REPL:

repl.c:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "../lexer/lexer.h"
#include "../token/token.h"
#include "../util/util.h"

int main(void)
{
printf("Hello! This is the Monkey Programming Language!\n"
"Type in commands:\n");

while (true) {
fputs(">> ", stdout);
fflush(stdout);

size_t len = 0;
char *const line = util_readline(stdin, &len);

if (line == NULL) {
if (feof(stdin)) {
break;
} else {
fprintf(stderr, "error: an unexpected error occured.\n");
return EXIT_FAILURE;
}
}
len[line] = '\0';
Lexer l = lexer_new(line);

for (Token t = lexer_next(&l); t.type != TOK_EOF; token_delete(t), t = lexer_next(&l)) {
printf("{Type: %s, Literal: %s}\n", token_to_str(t.type), t.lit);
}
free(line);
}

return EXIT_SUCCESS;
}


### Tests:

And tests for the lexer; lexer_test.c:

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "../lexer/lexer.h"
#include "../token/token.h"

#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L
#include <stdnoreturn.h>
#elif defined(__GNUC__) || defined(__clang__) || defined(__INTEL_LLVM_COMPILER)
#define noreturn        __attribute__((noreturn))
#else
#define noreturn        /**/
#endif

typedef struct {
const TokenType   expected_type;
const char *const expected_lit;
} test;

static size_t tests_run = 0;

static noreturn void fatal(const char fmt[static 1], ...)
{
va_list ap;
va_start(ap, fmt);
vfprintf(stderr, fmt, ap);
putchar('\n');
va_end(ap);
exit(EXIT_FAILURE);
}

static void run_test(const char input[static 1],
const test tests[static 1])
{
++tests_run;
fprintf(stderr, "[INFO]: Running test suite %zu...\n", tests_run);
Lexer l = lexer_new(input);

for (const test *p_tests = tests; p_tests->expected_lit != NULL; ++p_tests) {
const Token t = lexer_next(&l);

if (t.lit == NULL) {
fprintf(stderr, "[FAIL]: error: failed to allocate memory for token.\n");
exit(EXIT_FAILURE);
}

const test tt = *p_tests;

if (t.type != tt.expected_type) {
fatal("[FAIL]: tests[%zu] - Tokentype wrong. Expected '%s', Got '%s'.\n",
p_tests - tests, token_to_str(tt.expected_type), token_to_str(t.type));
}

if (strcmp(t.lit, tt.expected_lit) != 0) {
fatal("[FAIL]: tests[%zu] - Literal wrong. Expected '%s', Got '%s'.\n",
p_tests - tests, tt.expected_lit, t.lit);
}

token_delete(t);
}

fprintf(stderr, "[INFO]: All tests passed!\n");
}

int main(void)
{
run_test("=+(){},;#", (const test[]) {
{ TOK_ASSIGN,    "=" },
{ TOK_PLUS,      "+" },
{ TOK_LPAREN,    "(" },
{ TOK_RPAREN,    ")" },
{ TOK_LBRACE,    "{" },
{ TOK_RBRACE,    "}" },
{ TOK_COMMA,     "," },
{ TOK_SEMICOLON, ";" },
{ TOK_ILLEGAL,   "#" },
{ TOK_EOF,       ""  },
{ -1,            NULL},
});

run_test("let five = 5;"
"let ten = 10;"
"let add = fn(x, y) { x + y; };"
(const test[]) {
{ TOK_LET,          "let"   },
{ TOK_IDENT,        "five"  },
{ TOK_ASSIGN,       "="     },
{ TOK_INT,          "5"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_LET,          "let"   },
{ TOK_IDENT,        "ten"   },
{ TOK_ASSIGN,       "="     },
{ TOK_INT,          "10"    },
{ TOK_SEMICOLON,    ";"     },
{ TOK_LET,          "let"   },
{ TOK_ASSIGN,       "="     },
{ TOK_FUNCTION,     "fn"    },
{ TOK_LPAREN,       "("     },
{ TOK_IDENT,        "x"     },
{ TOK_COMMA,        ","     },
{ TOK_IDENT,        "y"     },
{ TOK_RPAREN,       ")"     },
{ TOK_LBRACE,       "{"     },
{ TOK_IDENT,        "x"     },
{ TOK_PLUS,         "+"     },
{ TOK_IDENT,        "y"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_RBRACE,       "}"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_LET,          "let"   },
{ TOK_IDENT,        "result"},
{ TOK_ASSIGN,       "="     },
{ TOK_LPAREN,       "("     },
{ TOK_IDENT,        "five"  },
{ TOK_COMMA,        ","     },
{ TOK_IDENT,        "ten"   },
{ TOK_RPAREN,       ")"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_EOF,          ""      },
{ -1,               NULL    },
});

run_test("let five = 5;"
"let ten = 10;"
"let add = fn(x, y) {"
"x + y;"
"};"
"!-/*5;"
"5 < 10 > 5;"
"if (5 < 10) {"
"return true;"
"} else {"
"return false;"
"}"
"10 == 10;"
"10 != 9;",
(const test[]) {
{ TOK_LET,          "let"   },
{ TOK_IDENT,        "five"  },
{ TOK_ASSIGN,       "="     },
{ TOK_INT,          "5"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_LET,          "let"   },
{ TOK_IDENT,        "ten"   },
{ TOK_ASSIGN,       "="     },
{ TOK_INT,          "10"    },
{ TOK_SEMICOLON,    ";"     },
{ TOK_LET,          "let"   },
{ TOK_ASSIGN,       "="     },
{ TOK_FUNCTION,     "fn"    },
{ TOK_LPAREN,       "("     },
{ TOK_IDENT,        "x"     },
{ TOK_COMMA,        ","     },
{ TOK_IDENT,        "y"     },
{ TOK_RPAREN,       ")"     },
{ TOK_LBRACE,       "{"     },
{ TOK_IDENT,        "x"     },
{ TOK_PLUS,         "+"     },
{ TOK_IDENT,        "y"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_RBRACE,       "}"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_LET,          "let"   },
{ TOK_IDENT,        "result"},
{ TOK_ASSIGN,       "="     },
{ TOK_LPAREN,       "("     },
{ TOK_IDENT,        "five"  },
{ TOK_COMMA,        ","     },
{ TOK_IDENT,        "ten"   },
{ TOK_RPAREN,       ")"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_BANG,         "!"     },
{ TOK_MINUS,        "-"     },
{ TOK_SLASH,        "/"     },
{ TOK_ASTERISK,     "*"     },
{ TOK_INT,          "5"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_INT,          "5"     },
{ TOK_LT,           "<"     },
{ TOK_INT,          "10"    },
{ TOK_GT,           ">"     },
{ TOK_INT,          "5"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_IF,           "if"    },
{ TOK_LPAREN,       "("     },
{ TOK_INT,          "5"     },
{ TOK_LT,           "<"     },
{ TOK_INT,          "10"    },
{ TOK_RPAREN,       ")"     },
{ TOK_LBRACE,       "{"     },
{ TOK_RETURN,       "return"},
{ TOK_TRUE,         "true"  },
{ TOK_SEMICOLON,    ";"     },
{ TOK_RBRACE,       "}"     },
{ TOK_ELSE,         "else"  },
{ TOK_LBRACE,       "{"     },
{ TOK_RETURN,       "return"},
{ TOK_FALSE,        "false" },
{ TOK_SEMICOLON,    ";"     },
{ TOK_RBRACE,       "}"     },
{ TOK_INT,          "10"    },
{ TOK_EQ,           "=="    },
{ TOK_INT,          "10"    },
{ TOK_SEMICOLON,    ";"     },
{ TOK_INT,          "10"    },
{ TOK_NOT_EQ,       "!="    },
{ TOK_INT,          "9"     },
{ TOK_SEMICOLON,    ";"     },
{ TOK_EOF,          ""      },
{ -1,               NULL    },
});

return EXIT_SUCCESS;
}


## Makefile:

CC  := gcc-13

CFLAGS  += -std=c99
CFLAGS  += -DNDEBUG
CFLAGS  += -g3
CFLAGS  += -ggdb
CFLAGS  += -fPIC
CFLAGS  += -gdwarf-4
CFLAGS  += -Wall
CFLAGS  += -Wextra
CFLAGS  += -Wwrite-strings
CFLAGS  += -Wno-parentheses
CFLAGS  += -Wpedantic
CFLAGS  += -Warray-bounds
CFLAGS  += -Wconversion
CFLAGS  += -Wno-unused-function
CFLAGS  += -Wstrict-prototypes
CFLAGS  += -fanalyzer

BINDIR      := bin
TEST_BINDIR := tests/bin

SRCDIRS     := lexer repl token util
SRCS        := $(filter-out repl/repl.c,$(wildcard $(addsuffix /*.c,$(SRCDIRS))))

TESTDIR     := tests
TEST_SRCS   := $(wildcard$(TESTDIR)/*.c)

TARGET      := $(BINDIR)/repl TEST_TARGET :=$(TEST_BINDIR)/lexer_test

all: $(TARGET)$(TARGET): repl/repl.c $(SRCS) |$(BINDIR)
$(CC)$(CFLAGS) -o $@$^

$(TEST_TARGET):$(SRCS) $(TEST_SRCS) |$(TEST_BINDIR)
$(CC)$(CFLAGS) -o $@$^

test: $(TEST_TARGET) @echo "Running tests..." @./$<

$(BINDIR)$(TEST_BINDIR):
mkdir -p $@ rclean: rm -rf$(BINDIR)

tclean:
rm -rf $(TEST_BINDIR) fclean_repl: rm$(TARGET)

fclean_test:
rm \$(TEST_TARGET)

.PHONY: all test clean fclean_repl fclean_test

.DELETE_ON_ERROR:


## Review Request:

• project structure
• filenaming/code splitting
• naming and design
• makefile

In trying to avoid dynamic memory allocation, I have defined the structure for the lexer in the header file. Do you see a way around that?

Is there some standard function I can use instead of util_memstr()?

It'd also be nice if I could cut down on LOC.

For ease, here's the github repository: lexer-c.

Run make to build the REPL (it'll be in the bin directory), and make test to build and run the tests.

For the curious, here's the Go version: lexer-go.

• Next one would likely be a C++ version. Mar 30 at 22:19
• Too many unknowns. Does Monkey have comments? string literals? escape characters? Does it allow identifiers like xyz123? Underscores in identifieres? I'd rather see a formal definition of the language.
– vnp
Mar 31 at 3:12
• @vnp There is no formal definition of the language, but I have added a description from the book. Yes, it supports underscores in identifiers, but not digits. It doesn't have comments. Strings don't support escape characters. Apr 2 at 15:04

Here's a few suggestions that are not specific to the Monkey language:

Treat input as a stream
To read the characters from the input, you should only use read_char() and peek_char(). read_char() should return the character it reads. You should be able to easily substitute these for functions that read from a FILE*. Fields pos and ch in Lexer are redundant.

Parse integers
There's no reason for TOK_INT to store the integer as a string. You can parse it into an ìnt (or some other suitable type) and store that in the token. That'll make life easier when writing the parser. You can use a union in Token to store values of different types, depending on type.

Don't have Token manage memory
This pertains to TOK_IDENT and TOK_STRING. Having Token manage its own allocations of these will make it much harder to work with tokens. What if you want to make a copy of a token?

Make a separate 'arena' allocator that allocates all strings and deallocates all of them at once after you're done.

For TOK_IDENT it might be good to create a 'symbol table', which stores unique identifiers. Then the token would store a symbol ID, which is guaranteed to be the same for identical identifiers. This will be very helpful when writing the parser.

Add location data to the token
Tokens should at least contain the start and the end locations of the corresponding lexeme in the input stream. You might wish to store the line number as well. This will make it possible to print more useful error messages that can say where the error occurred. You'll need to modify skip_whitespace() to count line numbers.

Keywords and symbols don't need a payload
You don't need to store the string lit for keywords and symbols in the token. You can make a lookup table of those for printing. Having a dedicated function for returning a printable string for a token would be better than the lit field.

Opaque type for Lexer
You could declare typedef struct Lexer_s Lexer in lexer.h, and have the concrete struct Lexer_s {/* ... */}; in lexer.c. Then of course lexer_new() must return a pointer and you need a lexer_free() function.

The same could be done to Token as well, but there are some tradeoffs with that.

If needed, have a string type with length
Doing the above changes should make this unnecessary, but you could have a String type that contains char *ptr & size_t len fields. Then you could return that from functions like read_string(), instead of passing a pointer to store the length.

Use bool for boolean
I don't think anyone has been using straight int for boolean values in decades. C99 introduced stdbool.h, and before that people would #define BOOL int. Also you don't need to test for (boolean_expression != 0) as (boolean_expression) works the same.