I'm writing a programming language. It's something I've been working on and off on for the last year or so, but recently, I've decided to buckle down and do it.
As part of the language, I wrote a tokenizer. Its job is to turn a stream of human-readable characters into data the language can do something with. That allows for a couple of neat abstractions, as well as separating my concerns (the parsing code doesn't have to worry about the actual in-text layout of the code, just the tokens; the tokenizer doesn't parse, it just tokenizes)
I realize I could have let yacc
do the work, but half the point of this project is to fill out my lackluster resume be able to say "I made this from scratch".
Quick note beforehand (as opposed to the previous paragraphs): This uses StringBuilder. I've already put it up for review, and actually incorporated a few suggestions from that into this.
tokenizer.h
#ifndef CONCATEN_TOKENIZER_H
#define CONCATEN_TOKENIZER_H
#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>
#ifndef TKNR_FILE_BUF_SIZE
# define TKNR_FILE_BUF_SIZE 256
#endif
#if TKNR_FILE_BUF_SIZE <= 0
# error TKNR_FILE_BUF_SIZE cannot be <= 0
#endif
struct FileSource {
FILE *fptr;
unsigned char next_chars[TKNR_FILE_BUF_SIZE];
size_t next_chars_pos;
size_t eof; // if we're at EOF, this marks where in next_chars it is
};
struct StringSource {
char *begin;
char *end;
char *cur_pos;
};
struct Tokenizer {
union {
struct StringSource string;
struct FileSource file;
} source;
bool is_from_file;
char next_char;
char *origin;
size_t origin_len;
size_t line, index;
int error;
bool just_started;
};
enum TokenType {
TKN_UNKNOWN, TKN_WORD, TKN_STRING, TKN_REGEX,
TKN_INTEGER, TKN_REAL, TKN_IDENTIFIER
};
struct Token {
char *raw;
size_t raw_len;
char *origin;
size_t origin_len;
size_t line, index;
enum TokenType type;
};
struct Token tkn_empty(size_t line, size_t index);
char *tkn_type_name(int);
void tkn_free(struct Token *);
// object_t tkn_value(Token) // defined in object.h
struct Tokenizer tknr_from_string(const char *, const char *origin);
struct Tokenizer tknr_from_filepath(const char *path);
bool tknr_next(struct Tokenizer *, struct Token *);
char *tknr_err_to_string(int);
bool tknr_end(struct Tokenizer *);
void tknr_free(struct Tokenizer *);
#endif // ndef CONCATEN_TOKENIZER_H
tokenizer.c
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "tokenizer.h"
#include "stringbuilder.h"
#define ERROR(code) do{\
printf("Tokenizer error %d unhandled at " __FILE__ ":%d", code, __LINE__);\
exit(code % 100);\
}while(0)
//define TOKENIZER_OPS_FAIL 1000
// define CTOR_FAIL 1100
// define CTOR_STR_FAIL 1110
# define CTOR_STR_MALLOC_FAIL 1111
# define CTOR_STR_BAD_STRLEN_FAIL 1112
# define CTOR_STR_NULL_ARG_FAIL 1113
// define CTOR_FILE_FAIL 1120
# define CTOR_FILE_MALLOC_FAIL 1121
# define CTOR_FILE_BAD_STRLEN_FAIL 1122
# define CTOR_FILE_NULL_ARG_FAIL 1123
# define CTOR_FILE_FOPEN_FAIL 1124
// define READ_CHAR_FAIL 1200
# define FILE_READ_FAIL 1210
# define FILE_READ_EOF_FAIL 1211
// define STRING_READ_FAIL 1220
# define STRING_READ_EOS_FAIL 1221
// define NEXT_TOKEN_FAIL 1300
# define NT_MALLOC_FAIL 1301
# define NT_NEW_SB_FAIL 1302
# define NT_SB_FREE_COPY_FAIL 1303
//define TOKENIZER_SYNTAX_FAIL 1500
# define SYN_NO_SEPARATION_FAIL 1501
# define SYN_UNEXPECTED_END_FAIL 1502
// define SYN_STR_FAIL 1510
# define SYN_STR_MULTILINE_FAIL 1511
// define SYN_NUM_FAIL 1520
# define SYN_NUM_ILLEGAL_DIGIT_FAIL 1521
// define SYN_RGX_FAIL 1530
# define SYN_RGX_BAD_FLAG_FAIL 1531
struct Token tkn_empty(size_t line, size_t index) {
return (struct Token) {
.type = TKN_UNKNOWN,
.index = index,
.line = line,
.origin = NULL,
.raw = NULL,
.origin_len = 0,
.raw_len = 0,
};
}
char *tkn_type_name(int t) {
switch (t) {
case TKN_UNKNOWN:
return "unknown";
case TKN_WORD:
return "word";
case TKN_STRING:
return "string";
case TKN_REGEX:
return "regex";
case TKN_INTEGER:
return "integer";
case TKN_REAL:
return "real";
case TKN_IDENTIFIER:
return "identifier";
default:
abort();
}
}
void tkn_free(struct Token *t) {
free(t->raw);
t->raw = NULL;
free(t->origin);
t->origin = NULL;
}
char read_char(struct Tokenizer *);
struct Tokenizer tknr_from_string(const char *mem, const char *origin) {
struct Tokenizer ret = (struct Tokenizer) {
.origin = NULL,
.is_from_file = false,
.source.string = (struct StringSource) {
.begin = NULL,
.end = NULL,
.cur_pos = NULL
},
.next_char = '\0',
.just_started = true,
.error = 0
};
if (!mem || !origin) {
ret.error = CTOR_STR_NULL_ARG_FAIL;
return ret;
}
size_t mem_len = strlen(mem);
size_t origin_len = strlen(origin);
if (!mem_len || !origin_len) {
ret.error = CTOR_STR_BAD_STRLEN_FAIL;
return ret;
}
// .source
char *mem_c = malloc(mem_len + 1);
if (!mem_c) {
ret.error = CTOR_STR_MALLOC_FAIL;
return ret;
}
strcpy(mem_c, mem);
ret.source.string = (struct StringSource) {
.begin = mem_c,
.end = mem_c + mem_len + 1,
.cur_pos = mem_c
};
// location
char *origin_c = malloc(origin_len * sizeof(char) + 1);
if (!origin_c) {
free(ret.source.string.begin);
ret.error = CTOR_STR_MALLOC_FAIL;
return ret;
}
strcpy(origin_c, origin);
ret.origin = origin_c;
read_char(&ret);
ret.line = 1;
ret.index = 0;
return ret;
}
struct Tokenizer tknr_from_filepath(const char *path) {
struct Tokenizer ret = (struct Tokenizer) {
.origin = NULL,
.source.file = (struct FileSource) {
.eof = TKNR_FILE_BUF_SIZE,
.fptr = NULL,
.next_chars = {0},
.next_chars_pos = 0
},
.is_from_file = true,
.next_char = '\0',
.just_started = true,
.error = 0
};
if (!path) {
ret.error = CTOR_FILE_NULL_ARG_FAIL;
return ret;
}
size_t path_len = strlen(path);
if (!path_len) {
ret.error = CTOR_FILE_BAD_STRLEN_FAIL;
return ret;
}
// .source
FILE *fptr = fopen(path, "rb");
if (!fptr) {
ret.error = CTOR_FILE_FOPEN_FAIL;
return ret;
}
ret.source.file.fptr = fptr;
// location
char *path_c = malloc(path_len * sizeof(char) + 1);
if (!path_c) {
fclose(fptr);
ret.error = CTOR_FILE_MALLOC_FAIL;
return ret;
}
strcpy(path_c, path);
ret.origin = path_c;
struct FileSource *fs = &ret.source.file;
size_t count = fread(fs->next_chars, sizeof(char), TKNR_FILE_BUF_SIZE, fs->fptr);
if (count != TKNR_FILE_BUF_SIZE) {
if (feof(fs->fptr)) {
fs->eof = count;
} else {
fclose(fptr);
free(ret.origin);
ret.origin = NULL;
ret.error = FILE_READ_FAIL;
return ret;
}
}
ret.next_char = fs->next_chars[0];
fs->next_chars_pos = 1;
ret.line = 1;
ret.index = 0;
return ret;
}
void tknr_free(struct Tokenizer *freeing) {
// is this it? wow!
if (freeing->origin) {
free(freeing->origin);
freeing->origin = NULL;
}
if (freeing->is_from_file) {
if (freeing->source.file.fptr) {
fclose(freeing->source.file.fptr);
freeing->source.file.fptr = NULL;
}
} else {
free(freeing->source.string.begin);
freeing->source.string.begin = NULL;
freeing->source.string.end = NULL;
freeing->source.string.cur_pos = NULL;
}
}
int get_next_char_file(struct Tokenizer *from) {
struct FileSource *fs = &from->source.file;
if (tknr_end(from)) {
ERROR(FILE_READ_EOF_FAIL);
} else if (fs->next_chars_pos == TKNR_FILE_BUF_SIZE) {
size_t count = fread(fs->next_chars, sizeof(char), TKNR_FILE_BUF_SIZE, fs->fptr);
if (count != TKNR_FILE_BUF_SIZE) {
if (feof(fs->fptr)) {
fs->eof = count;
} else {
return FILE_READ_FAIL;
}
}
fs->next_chars_pos = 0;
}
from->next_char = fs->next_chars[fs->next_chars_pos++];
return 0;
}
int get_next_char_string(struct Tokenizer *from) {
struct StringSource *ss = &from->source.string;
if (tknr_end(from)) {
ERROR(STRING_READ_EOS_FAIL);
} else {
from->next_char = *ss->cur_pos;
++ss->cur_pos;
}
return 0;
}
char read_char(struct Tokenizer *reading) {
if (reading->error) {
ERROR(reading->error);
}
char ret = reading->next_char;
int err = 0;
if (reading->is_from_file) {
err = get_next_char_file(reading);
} else {
err = get_next_char_string(reading);
}
if (err) {
reading->error = err;
// note that it's possible that '\0' is the next character. That's why the functions
// that use this one not only check the return value of this but tknr_err(Tokenizer)
return 0;
}
if (ret == '\n') {
reading->index = 0;
++reading->line;
} else {
++reading->index;
}
return ret;
}
char peek_char(struct Tokenizer *peeking) {
if (peeking->error) {
ERROR(peeking->error);
}
return peeking->next_char;
}
bool is_ws(char c) {
return c == ' ' || c == '\t' ||
c == '\n' || c == '\r';
}
bool skip_ws(struct Tokenizer *from) {
bool skipped = false;
while (is_ws(peek_char(from)) && !tknr_end(from)) {
skipped = true;
read_char(from);
}
return skipped;
}
bool skip_slc(struct Tokenizer *from) {
if (peek_char(from) != '#') {
return false;
}
while (peek_char(from) != '\n' && !tknr_end(from)) {
read_char(from);
}
read_char(from); // take the newline
return true;
}
bool skip_between(struct Tokenizer *from) {
bool skipped = false;
while (skip_ws(from) || skip_slc(from)) skipped = true;
return skipped;
}
bool in_ranges(char c, char *begins, char *ends, size_t count) {
for (int i = 0; i < count; ++i) {
if (begins[i] <= c && c <= ends[i]) return true;
}
return false;
}
bool add_while_in_ranges(struct Tokenizer *from, struct StringBuilder *raw, char *next_char,
char *begins, char *ends, size_t num_ranges) {
*next_char = peek_char(from);
while (in_ranges(*next_char, begins, ends, num_ranges)) {
sb_append(raw, read_char(from));
*next_char = peek_char(from);
if (!(*next_char) && from->error) {
return false;
}
}
return true;
}
bool add_while_in_range(struct Tokenizer *from, struct StringBuilder *raw, char *next_char,
char begin, char end) {
return add_while_in_ranges(from, raw, next_char, &begin, &end, 1);
}
#define STARTING_RAW_MEM 16
bool get_string(struct Tokenizer *from, char *next_char, struct Token partial, struct Token *out) {
struct StringBuilder raw = sb_new();
if (!sb_init(&raw, STARTING_RAW_MEM)) {
from->error = NT_NEW_SB_FAIL;
return NULL;
}
while (1) {
sb_append(&raw, read_char(from));
if (tknr_end(from)) {
from->error = SYN_UNEXPECTED_END_FAIL;
goto error;
}
*next_char = peek_char(from);
if (*next_char == '\\') {
sb_append(&raw, read_char(from));
if (from->error) {
goto error;
}
sb_append(&raw, read_char(from));
if (from->error) {
goto error;
}
}
if (*next_char == '\n') {
from->error = SYN_STR_MULTILINE_FAIL;
goto error;
}
if (*next_char == '"') {
// add the quote
sb_append(&raw, read_char(from));
break;
}
}
size_t raw_cstr_len = raw.count;
char *raw_cstr = sb_into_string(raw);
if (!raw_cstr) {
from->error = NT_SB_FREE_COPY_FAIL;
goto error;
}
partial.raw = raw_cstr;
partial.raw_len = raw_cstr_len;
partial.type = TKN_STRING;
*out = partial;
return true;
error:;
sb_free(&raw);
tkn_free(&partial);
return false;
}
bool get_number(struct Tokenizer *from, char *next_char, struct Token partial, struct Token *out) {
struct StringBuilder raw = sb_new();
if (!sb_init(&raw, STARTING_RAW_MEM)) {
from->error = NT_NEW_SB_FAIL;
goto error;
}
partial.type = TKN_INTEGER;
enum {
B2, B8, B10, B16
} base = B10;
if (*next_char == '0') {
sb_append(&raw, read_char(from));
*next_char = peek_char(from);
if (*next_char == 'x') {
base = B16;
} else if (*next_char == 'o') {
base = B8;
} else if (*next_char == 'b') {
base = B2;
}
sb_append(&raw, read_char(from));
}
bool decimal = false;
if (base == B16) {
if (!add_while_in_ranges(from, &raw, next_char, "0aA", "9fF", 3)) {
goto error;
}
} else if (base == B8) {
if (!add_while_in_range(from, &raw, next_char, '0', '7')) {
goto error;
}
} else if (base == B2) {
if (!add_while_in_range(from, &raw, next_char, '0', '1')) {
goto error;
}
} else if (base == B10) {
// add decimal digits
if (!add_while_in_range(from, &raw, next_char, '0', '9')) {
goto error;
}
// un punto
if (*next_char == '.') {
decimal = true;
sb_append(&raw, read_char(from));
if (!add_while_in_range(from, &raw, next_char, '0', '9')) {
goto error;
}
}
// exponents
if (*next_char == 'e') {
decimal = true;
sb_append(&raw, read_char(from));
if (!add_while_in_range(from, &raw, next_char, '0', '9')) {
goto error;
}
}
}
if (from->error) {
goto error;
}
if (!is_ws(*next_char) && !tknr_end(from)) {
from->error = SYN_NUM_ILLEGAL_DIGIT_FAIL;
goto error;
}
partial.raw_len = raw.count;
partial.raw = sb_into_string(raw);
if (!partial.raw) {
from->error = NT_SB_FREE_COPY_FAIL;
goto error;
}
partial.type = decimal ? TKN_REAL : TKN_INTEGER;
*out = partial;
return true;
error:;
sb_free(&raw);
tkn_free(&partial);
return false;
}
bool is_flag(char c) {
return c == 'g' || c == 'x' ||
c == 'i' || c == 'a' ||
c == 'm' || c == 's';
}
bool get_regex(struct Tokenizer *from, struct StringBuilder raw, struct Token ret, struct Token *out) {
sb_append(&raw, read_char(from));
char next_char = peek_char(from);
while (true) {
if (next_char == '\\') {
sb_append(&raw, read_char(from));
if (from->error) {
goto error;
} else if (tknr_end(from)) {
from->error = SYN_UNEXPECTED_END_FAIL;
goto error;
}
sb_append(&raw, read_char(from));
if (from->error) {
goto error;
} else if (tknr_end(from)) {
from->error = SYN_UNEXPECTED_END_FAIL;
goto error;
}
}
if (next_char == '/') {
sb_append(&raw, read_char(from));
break;
}
sb_append(&raw, read_char(from));
if (from->error) {
goto error;
} else if (tknr_end(from)) {
from->error = SYN_UNEXPECTED_END_FAIL;
goto error;
}
next_char = peek_char(from);
}
next_char = peek_char(from);
while (is_flag(next_char)) {
sb_append(&raw, read_char(from));
next_char = peek_char(from);
}
if (!is_ws(next_char) && !tknr_end(from)) {
from->error = SYN_RGX_BAD_FLAG_FAIL;
goto error;
}
ret.type = TKN_REGEX;
ret.raw_len = raw.count;
ret.raw = sb_into_string(raw);
if (!ret.raw) {
from->error = NT_SB_FREE_COPY_FAIL;
goto error;
}
*out = ret;
return true;
error:;
sb_free(&raw);
tkn_free(&ret);
return false;
}
bool tknr_next(struct Tokenizer *from, struct Token *out) {
if (from->error) {
ERROR(from->error);
}
if (tknr_end(from)) {
return NULL;
}
if (!skip_between(from)) {
if (from->error) {
return false;
}
// at the very beginning, it's OK not to have separation
// (files don't have to start with code)
if (!from->just_started) {
from->error = SYN_NO_SEPARATION_FAIL;
return false;
}
}
if (from->just_started) {
from->just_started = false;
}
if (tknr_end(from)) {
return false;
}
struct StringBuilder raw = sb_new();
struct Token ret = tkn_empty(from->line, from->index);
ret.origin = malloc(from->origin_len * sizeof(char));
if (!ret.origin) {
from->error = NT_MALLOC_FAIL;
goto error;
}
strcpy(ret.origin, from->origin);
char next_char = peek_char(from);
if (!next_char && from->error) {
goto error;
}
if (next_char == '"') { // single-line string
return get_string(from, &next_char, ret, out);
} else if ('0' <= next_char && next_char <= '9') {
return get_number(from, &next_char, ret, out);
}
if (!sb_init(&raw, STARTING_RAW_MEM)) {
from->error = NT_NEW_SB_FAIL;
goto error;
}
if (next_char == ':') {
ret.type = TKN_IDENTIFIER;
} else if (next_char == 'r') {
sb_append(&raw, read_char(from));
next_char = peek_char(from);
if (next_char == '/') {
return get_regex(from, raw, ret, out);
}
}
while (!is_ws(next_char) && !tknr_end(from)) {
sb_append(&raw, read_char(from));
next_char = peek_char(from);
}
if (ret.type == TKN_UNKNOWN) ret.type = TKN_WORD;
ret.raw_len = raw.count;
ret.raw = sb_into_string(raw);
if (!ret.raw) {
from->error = NT_SB_FREE_COPY_FAIL;
sb_free(&raw);
}
*out = ret;
return true;
error:;
sb_free(&raw);
tkn_free(&ret);
return false;
}
bool tknr_end(struct Tokenizer *t) {
if (t->is_from_file) {
return t->source.file.eof < t->source.file.next_chars_pos;
} else {
return t->source.string.end == t->source.string.cur_pos;
}
}
int tknr_err(struct Tokenizer *t) {
return t->error;
}
Wow that's a lot of code. 623 + 66 = 689 LOC. Plus ~150 for the tests, which you can see here.
As an example, this would turn the Hello World program, "Hello, World!" puts
into two tokens: The string with raw value "Hello, World!"
and the word puts
. There very intentionally isn't a function defined to turn tokens into their Concaten values; that's defined in object.h
and its .c
(which will be up for review once it's done!)
A few things I'm concerned about:
- Performance, both in terms of speed and memory usage. Some things could definitely be improved. I haven't run a profiler yet; I want to finish the whole project to see where the biggest overall gains are. Probably something related to the dynamically-typed objects.
- Bugs! I've tested this code, and it works, but there are some things that concern me, though I'm not sure they're a problem. For example:
*out = ret
doesn't seem like it should work. Is this undefined behavior that happens to be working, or is it well-defined as correct? I'm concerned becauseret
is memory on the stack, which is theoretically freed as soon as the method exits; I'm not convinced because (a) it works and (b) it might be copying the value, which is fine.- I'm not certain I didn't use anything I
free
d. There are a lot of code paths, and while I think I got them all, I obviously don't know about the ones I missed.
- Memory leaks. Did I
free
everything Imalloc
ed? Is there a circumstance where it's possible for that not to happen? - Code style. And, similarly, readability -- I built this in bits and pieces from a groundwork that was... as well laid out as C let it be. It's still not very good. Anyway, because of its less than perfect origins
and my lack of C skillit's not very good C style.- No,
goto
is not being counted as "bad C style", unless you can write afinally
without convoluting things with an extra function call.
- No,
malloc
, or build the RAM with sand and a blowtorch. It doesn't diminish the challenge, and those caveats are understood when the language is specified. Also, I exaggerated; that was only half the point. The other half is to understand how things work behind the scenes; using a code generator doesn't do that. \$\endgroup\$