Stork，第2部分：创建表达式解析器

在本系列的这一部分中, 我们将介绍编写语言引擎脚本的一个棘手的(至少在我看来)组件, 这是每种编程语言的基本构建块：表达式解析器。

读者可能会(当然是这样)会问的一个问题是：为什么我们不仅仅使用一些已经成熟的工具或库？

为什么我们不使用Lex, YACC, Bison, Boost Spirit或至少使用正则表达式？

在我们的整个关系中, 我的妻子注意到了我无法否认的一个特征：每当遇到一个难题时, 我都会列出一个清单。如果你考虑一下, 那将是很有意义的-我使用数量来弥补我回答中缺乏质量。

我现在将做同样的事情。

1. 我想使用标准的C ++。在这种情况下, 它将是C ++ 17。我认为该语言本身就很丰富, 而且我正在努力消除将标准库之外的任何内容添加到组合中的冲动。
2. 当我开发第一种脚本语言时, 我没有使用任何复杂的工具。我面临着很大的压力, 而且期限紧迫, 但是我不知道如何使用Lex, YACC或类似工具。因此, 我决定手动开发所有内容。
3. 后来, 我找到了一位经验丰富的编程语言开发人员写的博客, 建议不要使用任何这些工具。他说, 这些工具解决了语言开发中比较容易的部分, 因此无论如何, 你都将面临困难。就像很久以前, 当我和互联网都还很年轻时, 我现在找不到该博客。
4. 同时, 有一个模因说：”你遇到了一个问题, 决定使用正则表达式来解决。现在你有两个问题。”
5. 我不认识Lex, YACC, Bison或其他类似人。我知道Boost Spirit, 它是一个方便且令人赞叹的库, 但是我仍然希望更好地控制解析器。
6. 我喜欢手动做这些组件。实际上, 我可以给出答案并完全删除此列表。

完整代码可在我的GitHub页面上找到。

令牌迭代器

第1部分中的代码有一些更改。

这些大多是简单的修复和小的更改, 但是对现有解析代码的一个重要补充是类token_iterator。它使我们能够评估当前令牌, 而无需将其从流中删除, 这非常方便。

class tokens_iterator {
private:
  push_back_stream& _stream;
  token _current;
public:
  tokens_iterator(push_back_stream& stream);

  const token& operator*() const;
  const token* operator->() const;

  tokens_iterator& operator++();

  explicit operator bool() const;
};

使用push_back_stream对其进行初始化, 然后可以取消引用并对其进行递增。可以使用显式布尔转换来检查它, 当当前令牌等于eof时, 布尔转换将为false。

静态还是动态类型语言？

在这一部分中, 我必须做出一个决定：该语言是静态还是动态类型？

静态类型语言是一种在编译时检查其变量类型的语言。

另一方面, 动态类型语言不会在编译期间(如果有编译, 这对于动态类型语言不是必需的)进行检查, 而是在执行期间进行检查。因此, 潜在错误可以存在于代码中, 直到被击中。

这是静态类型语言的明显优势。每个人都喜欢尽快发现他们的错误。我一直想知道动态类型语言的最大优点是什么, 而答案在最近几周给我留下了深刻的印象：它更容易开发！

我开发的以前的语言是动态键入的。我对结果或多或少感到满意, 并且编写表达式解析器并不难。基本上, 你不必检查变量类型, 而是依靠运行时错误, 几乎可以自发地编写这些错误。

例如, 如果必须编写二进制+运算符, 并且要对数字进行运算, 则只需在运行时将该运算符的两端都视为数字。如果双方均无法评估该数字, 则只抛出一个异常。我什至通过检查表达式中变量的运行时类型信息来实现运算符重载, 而运算符是该运行时信息的一部分。

在我开发的第一门语言(这是我的第三门语言)中, 我在编译时进行了类型检查, 但是我没有充分利用这一点。表达式评估仍然取决于运行时类型信息。

现在, 我决定开发一种静态类型的语言, 事实证明这比预期的要困难得多。但是, 由于我不打算将其编译为二进制或任何一种模拟的汇编代码, 因此某些类型的信息将隐式存在于已编译的代码中。

类型

作为我们必须支持的最少类型, 我们将从以下内容开始：

• 号码
• 弦乐
• 函数
• 数组

尽管将来可能会添加它们, 但一开始我们将不支持结构(或类, 记录, 元组等)。但是, 请记住, 以后可能会添加它们, 因此我们不会用难以更改的决定来密封命运。

首先, 我想将类型定义为字符串, 这将遵循一些约定。每个标识符在编译时都会按值保留该字符串, 有时我们将不得不对其进行解析。例如, 如果我们将数字数组的类型编码为” [number]”, 则必须修整第一个和最后一个字符, 以获取内部类型, 在这种情况下为” number”。如果考虑一下, 这是一个非常糟糕的主意。

然后, 我尝试将其实现为一个类。该类将具有有关该类型的所有信息。每个标识符将保留指向该类的共享指针。最后, 我考虑过在编译过程中使用所有类型的注册表, 因此每个标识符都具有指向其类型的原始指针。

我喜欢这个主意, 因此得出以下结论：

using type = std::variant<simple_type, array_type, function_type>;
using type_handle = const type*;

简单类型是枚举的成员：

enum struct simple_type {
  nothing, number, string, };

枚举成员在这里什么都没有作为void的占位符, 我不能使用它, 因为它是C ++中的关键字。

数组类型用具有type_handle唯一成员的结构表示。

struct array_type {
  type_handle inner_type_id;
};

显然, 数组长度不是array_type的一部分, 因此数组将动态增长。这意味着我们将以std :: deque或类似的内容结束, 但稍后再进行处理。

函数类型由其返回类型, 每个参数的类型以及是否通过值或引用传递这些参数组成。

struct function_type {
  struct param {
    type_handle type_id;
    bool by_ref;
  };
  type_handle return_type_id;
  std::vector<param> param_type_id;
};

现在, 我们可以定义将保留这些类型的类。

class type_registry {
private:
  struct types_less{
    bool operator()(const type& t1, const type& t2) const;
  };
  std::set<type, types_less> _types;

  static type void_type;
  static type number_type;
  static type string_type;
public:
  type_registry();

  type_handle get_handle(const type& t);

  static type_handle get_void_handle() {
    return &void_type;
  }

  static type_handle get_number_handle() {
    return &number_type;
  }

  static type_handle get_string_handle() {
    return &string_type;
  }
};

类型保存在std :: set中, 因为该容器是稳定的, 这意味着即使在插入新类型之后, 指向其成员的指针仍然有效。有一个函数get_handle, 它注册传递的类型并返回指向它的指针。如果类型已经被注册, 它将返回现有类型的指针。还有一些便利函数来获取基本类型。

至于类型之间的隐式转换, 数字将可转换为字符串。它不应该是危险的, 因为不可能进行反向转换, 并且字符串连接的运算符与数字加法运算符不同。即使在该语言开发的后期阶段取消了这种转换, 这也将是目前的练习。为此, 我不得不修改数字解析器, 因为它总是被解析。作为小数点。它可能是串联运算符的第一个字符…

编译器上下文

在编译期间, 不同的编译器功能需要获取有关到目前为止已编译代码的信息。我们将把这些信息保存在一个类editor_context中。由于我们将要实现表达式解析, 因此我们需要检索有关遇到的标识符的信息。

在运行时, 我们会将变量保存在两个不同的容器中。其中一个将是全局变量容器, 另一个将是堆栈。当我们调用函数并输入作用域时, 堆栈将增长。随着我们从函数返回并离开范围, 它将缩小。当我们调用某个函数时, 我们将推入函数参数, 然后函数将执行。它的返回值离开时将被推到栈顶。因此, 对于每个函数, 堆栈将如下所示：

该函数将保留返回变量的绝对索引, 并且将相对于该索引找到每个变量或参数。

现在, 我们将函数视为常量全局标识符。

这是用作标识符信息的类：

class identifier_info {
private:
  type_handle _type_id;
  size_t _index;
  bool _is_global;
  bool _is_constant;
public:
  identifier_info(type_handle type_id, size_t index, bool is_global, bool is_constant);

  type_handle type_id() const;

  size_t index() const;

  bool is_global() const;

  bool is_constant() const;
};

对于局部变量和函数参数, 函数索引返回相对于返回值的索引。如果是全局标识符, 它将返回绝对全局索引。

我们将在compile_context中进行三种不同的标识符查找：

1. 全局标识符查找, 它将按值保存compile_context, 因为在整个编译过程中都是相同的。
2. 本地标识符查找, 作为unique_ptr, 在全局范围内将为nullptr并将在任何函数中初始化。每当我们进入作用域时, 新的本地上下文都将使用旧的本地上下文作为其父级进行初始化。当我们离开示波器时, 它将被其父级替换。
3. 函数标识符查找, 这将是原始指针。在全局范围内它将为nullptr, 并且与任何函数中最外部的局部范围具有相同的值。

class compiler_context {
private:
  global_identifier_lookup _globals;
  function_identifier_lookup* _params;
  std::unique_ptr<local_identifier_lookup> _locals;
  type_registry _types;
public:
  compiler_context();
  type_handle get_handle(const type& t);
  const identifier_info* find(const std::string& name) const;
  const identifier_info* create_identifier(std::string name, type_handle type_id, bool is_constant);
  const identifier_info* create_param(std::string name, type_handle type_id);
  void enter_scope();
  void enter_function();
  bool leave_scope();
};

表达树

解析表达式标记后, 它们将转换为表达式树。与所有树类似, 该树也由节点组成。

有两种不同的节点：

1. 叶子节点, 可以是：
   a)标识符
   b)数字
   c)琴弦
2. 内部节点, 代表对其子节点的操作。它将其子项保留为unique_ptr。

对于每个节点, 都有关于其类型以及是否返回左值(可以出现在=运算符左侧的值)的信息。

创建内部节点时, 它将尝试将其子级的返回类型转换为期望的类型。允许以下隐式转换：

1. 从左值到非左值
2. 任何虚空的东西
3. 字符串编号

如果不允许转换, 将引发语义错误。

这是类定义, 没有一些辅助函数和实现细节：

enum struct node_operation {
  ...
};

using node_value = std::variant<
  node_operation, std::string, double, identifier
>;

struct node {
private:
  node_value _value;
  std::vector<node_ptr> _children;
  type_handle _type_id;
  bool _lvalue;
public:
  node(
    compiler_context& context, node_value value, std::vector<node_ptr> children
  );

  const node_value& get_value() const;
  const std::vector<node_ptr>& get_children() const;
  type_handle get_type_id() const;
  bool is_lvalue() const;
  void check_conversion(type_handle type_id, bool lvalue);
};

除了功能check_conversion之外, 方法的功能是不言自明的。它将通过遵循类型转换规则来检查类型是否可转换为传递的type_id和布尔左值, 否则将引发异常。

如果节点使用std :: string或double初始化, 则其类型分别为字符串或数字, 并且不是左值。如果使用标识符初始化, 则它将采用该标识符的类型, 如果标识符不是常数, 则为左值。

但是, 如果使用节点操作对其进行了初始化, 则其类型将取决于该操作, 有时还取决于其子代的类型。让我们在表格中写下表达式类型。我将使用＆后缀表示左值。如果多个表达式具有相同的处理方式, 我将在圆括号中编写其他表达式。

一元运算

二元运算

三元运算

函数调用

当涉及到函数调用时, 事情变得有些复杂。如果函数具有N个参数, 则函数调用操作具有N + 1个子代, 其中第一个子代是函数本身, 其余子代对应于函数自变量。

但是, 我们不允许通过引用隐式传递参数。我们将要求呼叫者在其前面加上＆符号。目前, 这将不是附加的运算符, 而是函数调用的解析方式。如果我们不解析与号, 则在期望参数时, 我们将通过添加一个称为node_operation :: param的伪一元操作来从该参数中删除左值。该操作与其子级具有相同的类型, 但不是左值。

然后, 当我们使用该调用操作构建节点时, 如果有一个左值, 但函数不希望使用的参数, 则会生成错误, 因为这意味着调用方意外键入了”＆”号。令人惊讶的是, 如果将＆视为运算符, 它的优先级最低, 因为如果在表达式内部进行解析, 它在语义上就没有意义。我们可能会在以后更改它。

表达式解析器

著名的计算机科学哲学家埃德斯·迪克斯特拉(Edsger Dijkstra)在谈到程序员潜力时说过：

“实际上, 不可能向事先接触过BASIC的学生教授良好的编程。作为潜在的程序员, 他们在精神上被肢解, 无法重生。”

因此, 对于所有尚未接触过BASIC的人, 请多加感谢, 因为你摆脱了”精神残害”。

我们其余的人, 残缺不全的程序员, 让我们回想起用BASIC编码的时代。有一个运算符\, 用于积分除法。在你没有整数和浮点数的单独类型的语言中, 这非常方便, 因此我在Stork中添加了相同的运算符。我还添加了运算符\ =, 如你所料, 它将执行整数除法然后赋值。

我认为例如JavaScript程序员会喜欢这种运算符。我什至都无法想象, 如果迪杰斯特拉(Dijkstra)活得足够长, 看到JS越来越流行, 他会怎么说呢。

说到这些, 我对JavaScript的最大问题之一就是以下表达式的差异：

• ” 1″-” 1″计算为0
• ” 1″ *” 1″等于1
• ” 1″ /” 1″等于1
• ” 1″ +” 1″等于” 11″

克罗地亚嘻哈二人组” Tram 11″以连接萨格勒布郊区的电车而得名, 其歌曲大致翻译为：”一个和一个不是两个, 而是11个。”它是在90年代后期问世的, 因此它不是对JavaScript的引用, 但可以很好地说明这种差异。

为避免这些差异, 我禁止从字符串到数字的隐式转换, 并为串联添加了..运算符(为带赋值的串联添加了.. =)。我不记得我对那个接线员有什么想法。它不是来自BASIC或PHP, 并且我不会搜索” Python串联”一词, 因为在Google上搜索有关Python的任何信息都会使我的脊柱发冷。我有蛇恐惧症, 并将其与”串联”结合使用-不, 谢谢！也许以后, 使用一些基于旧文本的浏览器, 而不使用ASCII艺术。

但是回到本节的主题-我们的表达式解析器。我们将使用”调车场算法”的改编版。

这是任何普通程序员在思考问题10分钟左右后想到的算法。它可以用于评估中缀表达式或将其转换为波兰语的相反符号, 而我们不会这样做。

该算法的思想是从左到右读取操作数和运算符。读取操作数时, 会将其压入操作数堆栈。读取运算符时, 我们无法立即对其进行评估, 因为我们不知道以下运算符的优先级是否会更高。因此, 我们将其推入运算符堆栈。

但是, 我们首先检查堆栈顶部的运算符的优先级是否比我们刚刚阅读的优先级高。在这种情况下, 我们从堆栈的顶部对操作数进行评估, 并在操作数堆栈上进行操作数的计算。我们将结果压入操作数堆栈。我们一直保留它, 直到我们读完所有内容, 然后对操作数堆栈左侧的所有运算符以及操作数堆栈上的操作数进行求值, 将结果推回操作数堆栈, 直到没有任何运算符并且只有一个操作数为止, 即结果。

当两个运算符具有相同的优先级时, 如果这些运算符是左关联的, 我们将采用左一个。否则, 我们选择正确的。具有相同优先级的两个运算符不能具有不同的关联性。

原始算法也处理圆括号, 但是我们将以递归方式进行处理, 因为这样可以使算法更简洁。

Edsger Dijkstra将算法命名为”调车场”, 因为它类似于铁路调车场的操作。

但是, 原始的调车场算法几乎不执行错误检查, 因此很有可能将无效的表达式解析为正确的表达式。因此, 我添加了布尔变量, 该变量检查我们是否期望运算符或操作数。如果我们期望操作数, 那么我们也可以解析一元前缀运算符。这样, 无效的表达式就无法通过, 表达式语法检查也就完成了。

包起来

当我开始为该系列的这一部分编写代码时, 我计划编写有关表达式构建器的文章。我想构建一个可以求值的表达式。但是, 对于一篇博客而言, 结果太复杂了, 所以我决定将其分成两半。在这一部分中, 我们结束了对表达式的解析, 并且我将在下一篇文章中介绍构建表达式对象。

如果我记得正确, 大约15年前, 我花了一个周末写了我的第一语言的第一版, 这让我怀疑这次出了什么问题。

为了不让我变老, 减少机智, 我会怪我两岁的儿子在业余时间过分苛刻。

与第1部分相同, 欢迎你从我的GitHub页面阅读, 下载甚至编译代码。