Part 1: Tokenizer

This series will guide you through the step-by-step development of a new scripting language.

The first question that might pop into your head is: “Do we really need another programming language?”

Do We Really Need a New Programming Language?

Let’s take a detour to answer this question.

Imagine yourself as an architect (someone who designs buildings, not software). You’re stuck in a country drowning in red tape. You have a fantastic idea for a shopping mall in your underdeveloped hometown. You meticulously craft the project and confidently submit your building permit application. As expected, it’s immediately rejected because you don’t have a registered company. Determined, you start the company registration process, which involves depositing a hefty sum. You then try to find a suitable name for your company, but every suggestion is met with disapproval. Finally, after five attempts, your company name is accepted, and your application is placed at the bottom of a massive pile. Exhausted and defeated, you either give up or discover that someone else has already built a shopping mall, capitalizing on your brilliant idea.

Thankfully, we are software engineers, not architects bound by physical limitations. We have the power to bring our ideas to life without the need for permits or navigating bureaucratic nightmares. All we need is some free time and the dedication to spend it coding instead of solving sudoku puzzles.

If you’re still not convinced that pure curiosity is a valid reason to create a programming language, let me share my own experience. My first foray into language design was driven by necessity, not just curiosity. However, that shouldn’t be your primary motivation for reading this blog. I believe the concepts presented here are intriguing and innovative enough to keep you engaged, even if you don’t plan on developing your own programming language.

Inspired by our goal of creating a compact scripting language, we’ve decided to name it “Stork.” And the best part is, we don’t need to seek approval from any bureaucratic entity for the name!

This series will document the programming language’s development as it unfolds, so there might be a few bugs along the way. Rest assured, these will be addressed as we approach the series’ conclusion.

You can access the complete source code for everything discussed here at GitHub.

To finally address the question posed in this section’s title — no, we don’t necessarily need a new programming language. However, since this series aims to demonstrate how to create one using C++, we’ll be building one for illustrative purposes.

Tokenizer’s Little Helpers

As a programmer, I frequently encounter this issue: I need a key-value container with fast, logarithmic-time value retrieval. However, once the container is initialized, I don’t intend to add any new values. This makes std::map<Key, Value> (or std::unordered_map<Key, Value>) excessive, as they prioritize fast insertion as well.

While I’m generally against unnecessary optimization, in this instance, I feel like a significant amount of memory is wasted. Moreover, we’ll eventually need to implement a maximal munch algorithm on top of this container, and map isn’t the most suitable choice.

Another option is to use std::vector<std::pair<Key,Value>> and sort it after insertions. However, this approach compromises code readability, as we need to constantly remember that the vector is sorted. To address this, I developed a simple class that enforces this constraint.

(Note: All functions, classes, etc., are declared within the stork namespace. For better readability, I’ll omit this namespace.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

template <typename Key, typename Value>
class lookup {
public:
  using value_type = std::pair<Key, Value>;
  using container_type = std::vector<value_type>;
private:
  container_type _container;
public:
  using iterator = typename container_type::const_iterator;
  using const_iterator = iterator;
	
  lookup(std::initializer_list<value_type> init) :
    _container(init)
  {
    std::sort(_container.begin(), _container.end());
  }
	
  lookup(container_type container) :
    _container(std::move(container))
  {
    std::sort(_container.begin(), _container.end());
  }
	
  const_iterator begin() const {
    return _container.begin();
  }
	
  const_iterator end() const {
    return _container.end();
  }
	
  template <typename K>
    const_iterator find(const K& key) const {
      const_iterator it = std::lower_bound(
        begin(),
        end(),
        key,
        [](const value_type& p, const K& key) {
          return p.first < key;
        }
    );
    return it != end() && it->first == key ? it : end();
  }
	
  size_t size() const {
    return _container.size();
  }
};

The class implementation is quite straightforward. I chose to implement only the necessary methods for our purposes. As the underlying container is a vector, it can be initialized with a pre-populated vector or an initializer_list.

The tokenizer will process characters from an input stream. At this stage, the exact nature of this input stream is still undecided, so I’ll utilize std::function.

1

using get_character = std::function<int()>;

We’ll adhere to the established conventions of C-style stream functions, such as getc, which returns an int instead of char, using negative values to signify the end of the file.

However, in a tokenizer, it’s beneficial to read a few characters ahead before determining the token type. To achieve this, I implemented a stream that allows us to “unread” characters.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class push_back_stream {
private:
  const get_character& _input;
  std::stack<int> _stack;
  size_t _line_number;
  size_t _char_index;
public:
  push_back_stream(const get_character& input);
	
  int operator()();
	
  void push_back(int c);
	
  size_t line_number() const;
  size_t char_index() const;
};

For brevity, I’ll omit the implementation details, which can be found on my GitHub page.

As you can see, push_back_stream is initialized using the get_character function. The overloaded operator() retrieves the next character, while push_back returns a character back to the stream. For error reporting, we have the convenience methods line_number and char_number.

It’s essential to remember that char_index represents the overall index of the character, not just its position within the current line. Otherwise, correctly implementing the push_back function would require storing all previous characters in a separate container.

Reserved Tokens

The tokenizer, the lowest-level compiler component, is responsible for reading the input and generating “tokens.” We’re interested in four token types:

• Reserved tokens
• Identifiers
• Numbers
• Strings

Comments are disregarded; the tokenizer will simply consume them without any notification.

To ensure widespread adoption and familiarity, we’ll embrace the widely recognized C-like syntax. Given its success in languages like C, C++, JavaScript, Java, C#, and Objective-C, it’s a safe bet for Stork. If you need a refresher, you can refer to one of our previous articles on C/C++ learning resources.

Let’s take a look at the reserved tokens enumeration:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

enum struct reserved_token {
  inc,
  dec,
	
  add,
  sub,
  concat,
  mul,
  div,
  idiv,
  mod,
	
  bitwise_not,
  bitwise_and,
  bitwise_or,
  bitwise_xor,
  shiftl,
  shiftr,
	
  assign,
	
  add_assign,
  sub_assign,
  concat_assign,
  mul_assign,
  div_assign,
  idiv_assign,
  mod_assign,

  and_assign,
  or_assign,
  xor_assign,
  shiftl_assign,
  shiftr_assign,
  
  logical_not,
  logical_and,
  logical_or,
  
  eq,
  ne,
  lt,
  gt,
  le,
  ge,
  
  question,
  colon,
  
  comma,
  
  semicolon,
  
  open_round,
  close_round,
  
  open_curly,
  close_curly,
  
  open_square,
  close_square,
  
  kw_if,
  kw_else,
  kw_elif,

  kw_switch,
  kw_case,
  kw_default,

  kw_for,
  kw_while,
  kw_do,

  kw_break,
  kw_continue,
  kw_return,

  kw_var,
  kw_fun,
  
  kw_void,
  kw_number,
  kw_string,
};

Enumeration members prefixed with “kw_” represent keywords. This prefix distinguishes them from C++ keywords that might share the same name. Members without a prefix are operators.

Most of them adhere to the C convention. Exceptions include: -concat and concat_assign (.. and ..=), employed for concatenation - idiv and idiv_assign (\ and \=), used for integer division - kw_var for variable declaration - kw_fun for function declaration - kw_number for numeric variables - kw_string for string variables

We’ll introduce additional keywords as needed.

One noteworthy new keyword is kw_elif. Personally, I’m not a fan of single-statement blocks (without curly braces). I rarely use them and don’t feel like they add much value, except in two specific scenarios:

1. When I accidentally type a semicolon right after a for, while, or if statement before the intended block. Sometimes, I’m lucky and get a compile-time error. Other times, it results in a redundant if-statement and a block that always executes. Fortunately, years of coding have taught me to avoid this mistake, so it rarely happens anymore. Even Pavlov’s dog eventually learned.
2. When I have a chain of if-statements, comprising an if-block followed by one or more else-if blocks, and potentially an else-block. Technically, when I write else if, it’s essentially an else block containing a single if-statement.

By introducing elif, we can potentially eliminate braceless statements entirely. However, the decision to allow or disallow them can wait for now.

Two helper functions assist in retrieving reserved tokens:

1
2

std::optional<reserved_token> get_keyword(std::string_view word);
std::optional<reserved_token> get_operator(push_back_stream& stream);

The get_keyword function checks if a provided word corresponds to a reserved keyword. This “word” is a sequence of letters, digits, and underscores, beginning with either a letter or an underscore. If it matches a keyword, the function returns a reserved_token. Otherwise, the tokenizer assumes it’s an identifier.

The get_operator function attempts to read as many characters as possible, as long as the sequence forms a valid operator. If it reads more characters than necessary, it “unreads” any extra characters after the longest recognized operator.

To implement these functions efficiently, we require two lookups between string_view and reserved_keyword.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

const lookup<std::string_view, reserved_token> operator_token_map {
  {"++", reserved_token::inc},
  {"--", reserved_token::dec},
  {"+", reserved_token::add},
  {"-", reserved_token::sub},
  {"..", reserved_token::concat},
  /*more exciting operators*/
};

const lookup<std::string_view, reserved_token> keyword_token_map {
  {"if", reserved_token::kw_if},
  {"else", reserved_token::kw_else},
  {"elif", reserved_token::kw_elif},

  {"switch", reserved_token::kw_switch},
  {"case", reserved_token::kw_case},
  {"default", reserved_token::kw_default},

  {"for", reserved_token::kw_for},
  {"while", reserved_token::kw_while},
  {"do", reserved_token::kw_do},

  {"break", reserved_token::kw_break},
  {"continue", reserved_token::kw_continue},
  {"return", reserved_token::kw_return},

  {"var", reserved_token::kw_var},
  {"fun", reserved_token::kw_fun},
  
  {"void", reserved_token::kw_void},
  {"number", reserved_token::kw_number},
  {"string", reserved_token::kw_string}
};

Implementing get_keyword is fairly simple. However, get_operator requires a custom comparator that compares a given character with potential operators, considering only the n-th character.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class maximal_munch_comparator{
private:
  size_t _idx;
public:
  maximal_munch_comparator(size_t idx) :
  _idx(idx)
  {
  }
  
  bool operator()(char l, char r) const {
  return l < r;
  }
  
  bool operator()(
    std::pair<std::string_view, reserved_token> l,
    char r
  ) const {
    return l.first.size() <= _idx || l.first[_idx] < r;
  }
  
  bool operator()(
    char l,
    std::pair<std::string_view, reserved_token> r
  ) const {
    return r.first.size() > _idx && l < r.first[_idx];
  }
  
  bool operator()(
    std::pair<std::string_view, reserved_token> l,
    std::pair<std::string_view, reserved_token> r
  ) const {
    return r.first.size() > _idx &&
    (
        l.first.size() < _idx ||
        l.first[_idx] < r.first[_idx]
    );
  }
};

This is a standard lexical comparator that focuses solely on the character at position idx. If a string is shorter than idx, it treats it as if it has a null character at that position, which is considered lesser than any other character.

With this understanding of the maximal_munch_operator class, let’s examine the implementation of get_operator:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

std::optional<reserved_token> get_operator(push_back_stream& stream) {
  auto candidates = std::make_pair(
    operator_token_map.begin(),
    operator_token_map.end()
  );
  
  std::optional<reserved_token> ret;
  size_t match_size = 0;
  
  std::stack<int> chars;
  
  for (size_t idx = 0; candidates.first != candidates.second; ++idx) {
    chars.push(stream());
  	
    candidates = std::equal_range(
      candidates.first,
      candidates.second,
      char(chars.top()),
      maximal_munch_comparator(idx)
    );
	
    if (
      candidates.first != candidates.second && candidates.first->first.size() == idx + 1
    ) {
      match_size = idx + 1;
      ret = candidates.first->second;
    }
  }

  while (chars.size() > match_size) {
    stream.push_back(chars.top());
      chars.pop();
  }

  return ret;
}

Initially, we treat all operators as potential candidates. We then read characters one by one, filtering the candidates using equal_range and comparing only the n-th character. There’s no need to compare preceding characters as they have already been evaluated. Similarly, we avoid comparing subsequent characters as they are irrelevant at this stage.

If the resulting range is not empty, we check if the first element (if one exists) has any remaining characters. If such an element exists, it always appears at the beginning of the range due to the sorted nature of the lookup. Finding such an element indicates a match with a valid operator. We return the longest matched operator and “unread” any extra characters read beyond it.

Tokenizer

Given the heterogeneous nature of tokens, we define a convenient token class. This class utilizes std::variant to encapsulate different token types:

• Reserved token
• Identifier
• Number
• String
• End of file

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class token {
private:
  using token_value = std::variant<reserved_token, identifier, double, std::string, eof>;

  token_value _value;
  size_t _line_number;
  size_t _char_index;
public:
  token(token_value value, size_t line_number, size_t char_index);

  bool is_reserved_token() const;
  bool is_identifier() const;
  bool is_number() const;
  bool is_string() const;
  bool is_eof() const;

  reserved_token get_reserved_token() const;
  std::string_view get_identifier() const;
  double get_number() const;
  std::string_view get_string() const;
	
  size_t get_line_number() const;
  size_t get_char_index() const;
};

The identifier is a simple class with a single member of type std::string, introduced for convenience. Using distinct types for each alternative in std::variant enhances code clarity.

Now, let’s create the tokenizer. It will be a single function that accepts a push_back_stream and returns the next token.

The key is to branch based on the type of the first character read:

• If we encounter the end-of-file character, we return from the function.
• If the character is whitespace, we skip it.
• If it’s an alphanumeric character (letter, digit, or underscore), we read all consecutive characters of that type, including dots if the first character is a digit. If the first character is indeed a digit, we attempt to parse the sequence as a number. Otherwise, we use the get_keyword function to determine if it’s a keyword or an identifier.
• A quotation mark signifies a string; we’ll treat it as such, unescaping any escaped characters.
• If we encounter a slash character (/), we check the next character. If it’s another slash or an asterisk (*), we skip the line/block comment.
• For any other character, we utilize the get_operator function.

Here’s the implementation of the tokenize function. I’ll omit the implementation details of the functions it calls.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

token tokenize(push_back_stream& stream) {
  while (true) {
    size_t line_number = stream.line_number();
    size_t char_index = stream.char_index();
    int c = stream();
    switch (get_character_type(c)) {
      case character_type::eof:
        return {eof(), line_number, char_index};
      case character_type::space:
        continue;
      case character_type::alphanum:
        stream.push_back(c);
        return fetch_word(stream);
      case character_type::punct:
        switch (c) {
          case '"':
            return fetch_string(stream);
          case '/':
          {
            char c1 = stream();
            switch(c1) {
            case '/':
                skip_line_comment(stream);
                continue;
              case '*':
                skip_block_comment(stream);
                continue;
              default:
                stream.push_back(c1);
            }
          }
          default:
            stream.push_back(c);
            return fetch_operator(stream);
        }
        break;
    }
  }
}

Notice that the function pushes back characters it reads before calling lower-level functions. While this might seem like a performance hit, the impact is negligible, and it significantly improves the code readability of the lower-level functions.

Exceptions

During one of his rants about exceptions, my brother proclaimed:

“There are two types of people: those who throw exceptions and those who have to catch them. I always find myself in the latter group.”

I share his sentiment. I’m not particularly fond of exceptions; throwing them often makes code harder to maintain and understand.

However, I’ve decided to make an exception (pun intended) to this rule. Throwing exceptions in a compiler can be quite useful for unwinding from deeply nested compilation stages.

Here’s the exception implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class error: public std::exception {
private:
  std::string _message;
  size_t _line_number;
  size_t _char_index;
public:
  error(std::string message, size_t line_number, size_t char_index) noexcept;
	
  const char* what() const noexcept override;
  size_t line_number() const noexcept;
  size_t char_index() const noexcept;
};

Rest assured, I promise to catch all exceptions in the top-level code. For convenient pretty-printing, I’ve even added line_number and char_index members, along with a dedicated function:

1
2
3
4
5

void format_error(
  const error& err,
  get_character source,
  std::ostream& output
);

Wrapping Up

That concludes the first installment of our series. While it might not have been overly exciting, we now have a functional tokenizer and basic parsing error handling, both of which are essential building blocks for the more captivating topics covered in upcoming articles.

I hope this post sparked some ideas. If you’re eager to delve into the details, you can find them on my GitHub page.