Stork：如何用C++编写编程语言

本文概述

• 第1部分：分词器
• 我们真的需要一种新的编程语言吗？
• Tokenizer的小帮手
• 保留代币
• 分词器
• 例外情况

第1部分：分词器

在本系列中, 我们将开发一种新的脚本语言并逐步描述该过程。

任何想知道的读者都会想到的第一个问题可能是：”我们真的需要一种新的编程语言吗？”

我们真的需要一种新的编程语言吗？

为了回答这个问题, 我将提出一点题外话。

假设你是一位建筑师(实际的实体建筑师, 而不是软件设计师), 而你不幸地出生在一个官僚主义的国家。你对在欠发达的家乡的购物中心有个不错的主意, 因此你可以创建项目并申请建筑许可。当然, 他们会以你没有注册公司为由立即拒绝你。因此, 你注册了一家公司。为此, 你需要存一些钱。然后, 你想出公司的名称, 但该名称被拒绝。在你的第五次尝试中, 它被接受, 并且你的应用程序进入堆的底部。最终, 你要么放弃, 要么意识到有人在此期间建造了购物中心。

但是我们不是真正的建筑师。我们是软件工程师, 我们有幸在没有任何许可或官僚主义的情况下将我们的想法付诸实践。我们唯一需要的是业余时间, 并愿意将其用于编程而不是数独谜题。

如果你仍然坚持认为编程的动机不能纯粹是出于好奇心, 那么我只想提一下, 我设计的第一门编程语言是由于必要性而不仅仅是好奇心而开发的。但是, 这不应该是阅读此博客的第一动机。我认为, 即使你实际上不需要创建自己的编程语言, 你在这里会遇到的许多想法也很有趣且富有创意, 可以使你保持兴趣。

我们开发一种小型脚本语言的目标启发了我将其命名为” Stork”。幸运的是, 我们不需要说服任何官僚批准这个名字。

在学习本系列文章时, 我将开发编程语言, 因此, 我也有可能会开发一些bug。当我们接近本系列的结尾时, 应该解决它们。

此处描述的所有内容的完整源代码均可从GitHub免费获得。

最后, 要回答本段标题中的问题-不, 我们实际上不需要新的编程语言, 但是由于我们试图演示如何用C ++编写编程语言, 因此我们将创建一种用于演示的语言。

Tokenizer的小帮手

我不知道其他程序员是否经常遇到相同的问题, 但是我经常遇到此问题：

我需要一个键值容器, 该容器应该以对数时间快速检索值。但是, 一旦我初始化了容器, 就不想再向其添加新值了。因此, std :: map <Key, Value>(或std :: unordered_map <Key, Value>)会过时, 因为它也允许快速插入。

我完全反对不必要的优化, 但是在这种情况下, 我感觉很多内存都浪费在了什么上。不仅如此, 而且以后, 我们将需要在这种容器之上实现最大的munch算法, 而map并不是实现此目的的最佳容器。

第二个选择是std :: vector <std :: pair <Key, Value>>, 在插入后排序。这种方法的唯一问题是代码的可读性较低, 因为我们需要记住向量是排序的, 因此我开发了一个小的类来确保该约束。

(所有函数, 类等都在名称空间stork中声明。为了可读性, 我将省略该名称空间。)

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();
  }
};

如你所见, 此类的实现非常简单。我并不想实现所有可能的方法, 而只是我们需要的方法。基础容器是向量, 因此可以使用预先填充的向量或initializer_list对其进行初始化。

分词器将从输入流中读取字符。在项目的这个阶段, 我很难决定输入流是什么, 所以我将改用std :: function。

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

我将使用C样式流函数中的众所周知的约定, 例如getc, 该约定将返回int而不是char以及负数来表示文件结束。

但是, 在假定令牌生成器中的令牌类型之前, 预先读取几个字符确实很方便。为此, 我实现了一个流, 该流将允许我们未读一些字符。

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;
};

为了节省空间, 我将省略实现细节, 你可以在我的GitHub页面上找到这些细节。

如你所见, push_back_stream是从get_character函数初始化的。重载的operator()用于检索下一个字符, 而push_back用于将字符返回到流中。 line_number和char_number是用于错误报告的便捷方法。

请记住, char_index不是当前行中字符的索引, 而是整体。否则, 我们必须将所有过去的字符保留在某个容器中, 才能正确实现push_back函数。

保留代币

标记器是最低级别的编译器组件。它必须读取输入和”吐出”令牌。我们感兴趣的令牌有四种：

• 预留令牌
• 身份标识
• 号码
• 弦乐

我们对评论不感兴趣, 因此令牌生成器将”吃掉”它们, 而不会通知任何人。

为了确保这种语言的吸引力和广泛的流行性, 我们将使用众所周知的类似C的语法。它对于C, C ++, JavaScript, Java, C＃和Objective-C都非常有效, 因此它也必须对Stork也有效。如果你需要进修课程, 可以查阅我们以前的一篇文章, 其中涉及C / C ++学习资源。

这是保留的令牌枚举：

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, };

前缀为” kw_”的枚举成员是关键字。我必须给它们加上前缀, 因为它们通常与C ++关键字相同。没有前缀的是运算符。

它们几乎都遵循C约定。没有的是：

-concat和concat_assign(..和.. =), 将用于串联

-idiv和idiv_assign(\和\ =), 将用于整数除法

-kw_var用于变量声明

-kw_fun用于函数声明

-kw_number用于数字变量

-kw_string用于字符串变量

我们将根据需要添加其他关键字。

有一个值得描述的新关键字：kw_elif。我坚信单语句块(不带花括号)是不值得的。除以下两种情况外, 我不使用它们(并且我不觉得有任何缺失)：

1. 当我不小心在for, while或if语句之后立即打分号时, 在块之前。如果幸运的话, 它会返回编译时错误, 但有时会导致伪if语句和始终执行的块。幸运的是, 多年来, 我已从自己的错误中学到了东西, 所以这种情况很少发生。最终, 巴甫洛夫的狗也学会了。
2. 当我”链接”了if语句时, 因此我有一个if块, 然后是一个或多个else-if块, 还可以选择一个else块。从技术上讲, 当我编写else if时, 这是一个else块, 只有一个语句, 即if语句。

因此, 可以使用elif完全消除无括号的语句。我们是否允许这个决定现在可以等待。

有两个帮助程序函数返回保留的令牌：

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

函数get_keyword从传递的单词中返回一个可选关键字。 “单词”是由字母, 数字和下划线组成的序列, 从字母或下划线开始。如果单词是关键字, 它将返回reserved_token。否则, 令牌生成器将假定它是一个标识符。

只要序列是有效的运算符, 函数get_operator就会尝试读取尽可能多的字符。如果读取更多, 它将在最长识别的运算符之后不读取已读取的所有其他字符。

为了有效地实现这两个功能, 我们需要在string_view和reserved_keyword之间进行两次查找。

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}
};

get_keyword的实现是非常简单的, 但是对于get_operator, 我们需要一个自定义比较器, 该比较器将给定字符与候选运算符进行比较, 仅考虑第n个字符。

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]
    );
  }
};

那是一个普通的词法比较器, 它只考虑位置idx处的字符, 但是如果字符串较短, 则将其视为在位置idx处具有空字符, 该空字符比其他任何字符都要少。

这是get_operator的实现, 应该使maximal_munch_operator类更清晰：

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;
}

基本上, 我们从一开始就将所有运营商都视为候选人。然后, 我们逐字符读取字符, 并通过调用equal_range, 仅比较第n个字符来过滤当前候选字符。我们不需要比较前面的字符, 因为它们已经不相关了, 我们也不想比较后面的字符, 因为它们仍然无关紧要。

每当范围为非空时, 我们都会检查范围中的第一个元素是否没有更多的字符(如果存在这样的元素, 则在对查询进行排序时, 它始终位于范围的开头)。在这种情况下, 我们有一个合法的运营商匹配。最长的此类运算符是我们返回的运算符。之后, 我们将不读所有最终阅读的字符。

分词器

由于令牌是异构的, 因此令牌是包装std :: variant不同令牌类型的便利类, 即：

• 预留令牌
• 识别
• Number
• String
• 文件结束

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;
};

标识符只是具有std :: string类型的单个成员的类。我觉得它很方便, 因为如果std :: variant的所有替代项都是不同的类型, 则它更干净。

现在, 我们可以编写令牌生成器了。这将是一个接受push_back_stream并返回下一个标记的函数。

诀窍是根据我们读取的第一个字符的字符类型使用不同的代码分支。

• 如果我们读取文件结尾字符, 我们将从函数返回。
• 如果读取空白, 则将其跳过。
• 如果我们读取一个字母数字字符(一个字母, 一个数字或一个下划线), 我们将读取该类型的所有连续字符(如果第一个字符是一个数字, 我们还将读取点)。然后, 如果第一个字符是数字, 我们将尝试将序列解析为数字。否则, 我们将使用get_keyword函数检查它是关键字还是标识符。
• 如果我们读引号, 我们会将其视为字符串, 从中转义转义字符。
• 如果读取斜杠字符(/), 我们将检查下一个字符是斜杠还是星号(*), 在这种情况下, 我们将跳过行/块注释。
• 否则, 我们将使用get_operator函数。

这是标记化函数的实现。我将忽略它正在调用的函数的实现细节。

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;
    }
  }
}

你可以看到它在调用较低级别的函数之前会回退所读取的字符。几乎不存在性能损失, 并且较低级的功能代码更简洁。

例外情况

在对例外的咆哮中, 我的兄弟曾经说过：

“有两种人：抛出异常的人和必须捕获异常的人。我总是在那可悲的第二组。”

我同意那句话的精神。我并不特别喜欢异常, 而抛出异常会使任何代码更难以维护和阅读。几乎总是。

我决定对该规则做一个例外(意为双关语)。从编译器抛出异常以从编译的深度中解脱出来真的很方便。

这是异常实现：

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;
};

但是, 我保证会捕获顶级代码中的所有异常。我什至添加了line_number和char_index成员以进行漂亮的打印, 以及执行此操作的函数：

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

包起来

到此结束我们系列的第一部分。也许这并不太令人兴奋, 但是我们现在有了一个有用的标记器以及基本的解析错误处理。对于我将在以后的文章中写到的更有趣的内容, 两者都是至关重要的基础。

我希望你从这篇文章中得到一些好主意, 如果你想探索细节, 请转到我的GitHub页面。