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

第 1 部分：分词器

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

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

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

为了回答这个问题，我允许自己稍微题外话。

想象一下，您是一名建筑师（实际的实体建筑师，而不是软件建筑师），而您不幸出生在一个非常官僚的国家。 你有一个在你不发达的家乡开一个购物中心的好主意，所以你创建了这个项目并申请了建筑许可证。 当然，他们会立即以你没有注册公司为由拒绝你。 所以，你注册了一家公司。 为此，您需要存入一些钱。 然后，您想出一个公司名称，但被拒绝。 在你第五次尝试时，它被接受了，你的应用程序进入了堆的底部。 最终，您要么放弃，要么意识到其他人在此期间建立了购物中心。

但我们不是真正的建筑师。 我们是软件工程师，我们有幸在没有许可或官僚主义的情况下将我们的想法变为现实。 我们唯一需要的就是业余时间和将其用于编程而不是数独游戏的意愿。

如果您仍然坚持认为编程的动机不能纯粹是出于好奇，那么我只想提一下，我设计的第一个编程语言是出于需要而开发的，而不仅仅是出于好奇。 但是，这不应该是阅读此博客的第一个动机。 我认为您将在这里遇到的许多想法都相当有趣和创新，即使您实际上并不需要创建自己的编程语言，也能保持您的兴趣。

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

在我们完成这个系列的过程中，我将开发编程语言，所以我也有可能会开发一些错误。 当我们接近系列赛结束时，它们应该被解决。

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

最后，回答本段标题中的问题——不，我们实际上并不需要一种新的编程语言，但由于我们试图演示如何用 C++ 制作编程语言，我们将创建一个用于演示目的.

Tokenizer 的小帮手

我不知道其他程序员是否经常遇到同样的问题，但我经常遇到这个问题：

我需要一个键值容器，它应该在对数时间内快速检索值。 但是，一旦我初始化了容器，我就不想向它添加新值。 因此， std::map<Key, Value> （或std::unordered_map<Key, Value> ）是多余的，因为它也允许快速插入。

我完全反对不必要的优化，但在这种情况下，我觉得很多内存都被浪费了。 不仅如此，以后我们还需要在这样的容器之上实现一个最大咀嚼算法，而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(); } };

如您所见，这个类的实现非常简单。 我不想实现所有可能的方法，只是我们需要的那些。 底层容器是一个vector ，因此可以使用预先填充的vector或 initializer_list 对其进行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不同的令牌类型，即：

• 保留令牌
• 标识符
• 数字
• 细绳
• 文件结束

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

identifier只是一个具有std::string类型的单个成员的类。 它的存在是为了方便，因为在我看来，如果std::variant的所有替代品都是不同的类型，它会更干净。

现在，我们可以编写分词器了。 这将是一个接受push_back_stream并返回下一个令牌的函数。

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

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

下面是 tokenize 函数的实现。 我将省略它调用的函数的实现细节。

 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 页面。

进一步阅读 Toptal 工程博客：

• 如何从头开始编写解释器