使用 Parser 实现一个计算器

这件事的缘起要说到这学期的第一个大作业：“一元稀疏多项式计算器”，简单的说，就是要求我们用线性表存储多项式，并实现简单的多项式加减。当时和学长聊起，学长提起既然写计算器那不如写个 parser，便给我一篇文章Crafting Interpreters令我看看，试着写一下。

彼时的我听到这个名词并不知其含义，但简单说来，所谓 parser 即把某种格式的字符串转换成某种数据结构的过程。有的 parser 可以将 JSON、XML 此类的序列化数据转换为对象化数据，而最常见的 parser 则是把程序文本转换为编译器内部的一种叫做“抽象语法树”(AST)的数据结构。

暂且不论有关 parser 引起的任何争论、发展出的任何技术，在这篇文章里，我希望通过我编写这一“计算器”的过程，与你认识一下 parser 的基本原理，并且实现这一简单的“解释器”。

鉴于篇幅与精力原因，这篇文章是在我写好了 V2.2 版本之后才进行书写的，项目源码在这里：MiniCalculator，欢迎前去翻阅。

The First Step

在迈出第一步之前，我想你有必要认识一下表达式树是什么。

对于这样一个表达式：(3 + 2) * (5 - 1)，在一定的优先级的控制下，我们可以把它建立为这样的一棵树：

     *
   /   \
  +     -
 / \   / \
3   2 5   1

当我们计算的时候，从叶子节点开始，向着根节点计算：首先 2 + 3 = 5，5 - 1 = 4 而后计算 5 * 4 = 20，于是，我们就得到了这一表达式的值。对表达式树进行后序遍历的结果便是大名鼎鼎的“逆波兰式”，也即“后缀表达式”。

这个例子中的 +、-、*均为二元运算符，因此建立出的树也是呈现出满二叉树的形式，然而在真正实现的时候，我们还有可能遇到一元、甚至三元的表达式。

另一个方面，这里的叶子节点都是整数，而在我们设计一个多项式计算器的时候，每一个叶子节点应该是一个单项式、而非现在的简单的整数。在结果上，我们期望的是得到一个多项式。

出于多项式除法、多项式非正整数次方的难度原因，这里我们限制：

1. 作为除数的部分必需为常数
2. 作为指数的部分必需为正整数，除非是仅做多项式求导，此时允许负整数指数幂

Expression

在设计上，我们设定一个表达式基类Expr，它有以下方法：

/// <summary>
/// 表达式的基类
/// </summary>
class Expr
{
public:
    /// <summary>
    /// 计算表达式
    /// </summary>
    /// <returns>返回多项式</returns>
    virtual Polyomial Eval();

    /// <summary>
    /// 带入自变量计算多项式
    /// </summary>
    /// <param name="x">自变量</param>
    /// <returns>多项式的值</returns>
    virtual long double Eval(long double x);

    /// <summary>
    /// 计算表达式
    /// </summary>
    /// <param name="poly">多项式</param>
    /// <returns>返回多项式</returns>
    virtual Polyomial Eval(Polyomial poly);
};

这三者分别实现了三个我们想要实现的功能：计算表达式、代入值给表达式求值以及表达式的复合运算。

对于我的需求，我将其派生出7个子类：

名称	用途	成员
BinaryExpr 二元表达式	用于实现二元运算	左右表达式、二元运算符
GroupingExpr 分组表达式	用于实现括号	括号内表达式
CompoundExpr 复合表达式	用于复合多项式	基表达式、待复合表达式
UnaryExpr 一元表达式	用于负号开头的表达式	右表达式、一元运算符
MonomialExpr 单项式表达式	用于记录一个单项式	指数、系数
NumberExpr 数字表达式	其实可以被单项式代替	数字
DerivativeExpr 求导表达式	为表达式求导	表达式

将其运算过程递归调用，并根据运算符进行结合，返回结果，实现三个函数，基于此便可实现表达式树节点的构建。

对于运算本身，我实现的 Polyomial 类用于维护一个指数到系数的对应关系，也即一个 std::map<int, long double> 的实例，并基于此实现了多项式的加减乘、常数除法、求导、快速幂以及格式化输出。具体代码可见Polyomial.cpp

而对于计算逻辑，则在 Expr 中进行了实现，求导的求导，代入的代入，复合的复合。其详细代码可见Expr.cpp

Lexer

做好了以上的“准备工作”，实际上老师想要的大作业的要求已经达到了，然而对于 Parser 而言，这才刚刚开始。

Lexer 意为“词法分析器”，它的工作是扫描字符串。它接收一个字符序列，将其分组为一系列的“词块”，这些词块被称为Tokens，他们是数字、单词以及一些字符，是用于构成语法的元素。

在我的实现中 Lexer 的构造函数接收一个字符串，并且初始化三个成员：Current 记录当前的解析位置、Length 记录字符串长度、Source 记录字符串的原文。

那么，如何将其取出呢？

标准库中有很多用于判断字符的函数，如isalpha判断字符是否是字母，isdigit判断字符是否是数字，这里想要使用它，我们可以利用C++11加入的std::function来定义：

bool Lexer::Match(std::function<bool(char)> cond)
{
    if (Finished())
        return false;

    if (cond(Source[Current]))
    {
        ++Current;
        return true;
    }

    return false;
}

从这个函数的行为上可以看出，在判断当前位的过程中，如果匹配成功，则前进到下一位，并返回 true ，这一特点会极大的方便我们后半部分的编写。

在此之上，我们能继续去定义两个用于判断单个字符或者一系列字符的函数，利用到lambda表达式：

bool Lexer::Match(char toMatch)
{
    return Match([&](char chr) -> bool {return chr == toMatch; });
}

bool Lexer::Match(std::vector<char> chrs)
{
    return Match([&](char chr) -> bool {
        bool res = false;
        for (auto& _chr : chrs)
            res = res || (chr == _chr);
        return res;
        });
}

于是我们就可以开始写获取 Token 了，这里使用的主要函数名为 Advance ，其功能是获取下一个 Token。

Token Lexer::Advance()
{
    // 跳过全部空白字符
    while (Match(isspace));

    // 匹配单字符
    if (Match('('))
        return Token(TokenType::LEFT_PAREN, Current - 1, Current);

    if (Match(')'))
        return Token(TokenType::RIGHT_PAREN, Current - 1, Current);

    if (Match('+'))
        return Token(TokenType::PLUS, Current - 1, Current);

    if (Match('-'))
        return Token(TokenType::MINUS, Current - 1, Current);

    if (Match('*'))
        return Token(TokenType::STAR, Current - 1, Current);

    if (Match('/'))
        return Token(TokenType::SLASH, Current - 1, Current);

    if (Match('\''))
        return Token(TokenType::RSQUO, Current - 1, Current);

    if (Match('^'))
        return Token(TokenType::TIP, Current - 1, Current);

    if (Match({ 'x' , 'X' }))
        return Token(TokenType::X, Current - 1, Current);

    size_t start = Current;

    // 匹配变量名称
    if (Match(isalpha))
    {
        while (Match(isalpha));
        return Token(TokenType::VAR, start, Current);
    }

    // 匹配数字
    if (Match(isdigit) || Match('.'))
    {
        while (Match(isdigit) || Match('.'));

        if(Current - start == 1 && Source[start] == '.')
            throw UnexpectedNumberException(start);

        return Token(TokenType::NUMBER, start, Current);
    }

    return Token(TokenType::NONE, start, Current);
}

其中 Token 类中含有三个成员：开始的位置、结束的位置以及当前 Token 的类型。在判断数字的时候，倘若只有一个 . 是无法构成任何有意义的数字的，于是需要将其抛出异常。具体的异常处理后文再将。

至此，我们只需要一直循环获取 Token 并将其存入列表，就可以实现词义的解析，并且获取我们需要的 Tokens 了。而当我们获取到一个 TokenType 是 None 的 Token 时，若解析尚未结束，则我们遇到了一个意料外的字符，这种时候也需要抛出异常。

Parser

至此，我们的字符串解析到此结束，下一步就需要根据我们获取到的 Tokens 以及语法规则、优先级顺序构建语法树了。

由于我们的目标是构建一个多项式表达式的解析器，因此核心以及唯一要做的工作也就是如何实现表达式的解析了——不用关心复杂语句的解析。对于栈模拟的计算器，遇到低优先级的运算符，总是需要将更高优先级的运算符先行弹出进行运算，以此实现不同优先级计算中的先后关系。

而在构建表达式 Parser 的过程中，这一过程变得更加灵活，优先级由函数递归产生的栈结构所控制，运算符的结合性也可以由其算法决定。在 Parser 的实现中，其构造函数初始化四个成员：Tokens 列表的当前与尾迭代器、原字符串以及一个变量映射——这相当于一个全局的变量列表，由 main 函数传入并由其管理生命周期。

在构建表达式的过程中，由于调用复杂且不易管理，因此采取 std::shared_ptr 进行表达式对象的管理，它使用引用计数的方式管理对象的生命周期，及时释放对象的内存。

不过在进行下一步之前，先看一下两个工具函数的使用：Peek 以及 Match（又是它）

Peek 的作用是判读接下来的几个 Token 是不是预计的类型，这里我最深用到了 4 层的判断，即从当前位置开始判断接下来的 4 个 Token 是否是指定的类型：

bool Peek(TokenType type);
bool Peek(TokenType type, TokenType next);
bool Peek(TokenType type, TokenType next, TokenType next1);
bool Peek(TokenType type, TokenType next, TokenType next1, TokenType next2);

其实现大同小异，但是需要时刻注意当前的迭代器是否越界：

bool Parser::Peek(TokenType type)
{
    if (Current == End)
        return false;
    return (*Current).Type == type;
}

而 Match 的作用则是获取当前的 Token，并且进行一些类型检查、判断截至的操作：

Token Parser::Match()
{
    if (Current >= End)
        throw UnexpectedEOFException();

    return *(Current++);
}

Token Parser::Match(TokenType type)
{
    if (Current >= End)
        throw UnexpectedEOFException();

    auto& token = *Current;
    if (token.Type != type)
        throw UnexpectedTokenException(token.Start);

    ++Current;
    return token;
}

是时候考虑一下优先级了，我们的表达式中按照由低到高一共含有 6 种：

1. Expr (+ | -) Expr 即二元加减法为最低优先级
2. Expr (* | / | '(' ) Expr 即二元乘除法、以及直接跟着左括号的情况，这也需要处理为乘法
3. Expr ^ Expr 即乘方运算，优先级高于乘除法
4. (-) Expr 即运算符在左侧的一元表达式，用于给整个表达式取反
5. Expr ' 即求导运算，由于不是很确定优先级，我将其放在仅次于基本表达式的位置
6. MonomialExpr | GroupingExpr | Expr ( Expr ) | Number 即分组表达式、单项式、数字以及表达式复合这些构建我们表达式树的基本元素

这里我采取的方法是左结合的写法，这里使用不同的处理会有不同的结合效果，读者可以自行探索。现在我们看看加减法的匹配函数：

std::shared_ptr<Expr> Parser::GetPlusExpr()
{
    auto ret = GetMutiExpr();
    while (Peek(TokenType::PLUS) || Peek(TokenType::MINUS))
    {
        Token _operator = Match();
        ret = std::make_shared<BinaryExpr>(ret, _operator, GetMutiExpr());
    }
    return ret;
}

这会递归建立一颗表达式树：先获取更高级的表达式，再判断下一个 Token 是否为 + 或 - 之后进行左结合，建立一个新节点后，继续循环递归。

对于乘法而言，其中读者可能会有问题的是省略乘号的行为如何判断，稍作考量可以得知，省略 * 作为乘法的的情况无外乎 ( Expr )( Expr ) 以及 Something ( Expr ) 因此在这一优先级有一些额外的操作：

std::shared_ptr<Expr> Parser::GetMutiExpr()
{
    auto ret = GetPowExpr();
    while (Peek(TokenType::STAR) || Peek(TokenType::SLASH) || Peek(TokenType::LEFT_PAREN))
    {
        if (Peek(TokenType::LEFT_PAREN))
        {
            // 这里不会 Match，因此不会将迭代器后移，此处会继续执行，匹配到分组表达式
            Token _operator = Token(TokenType::STAR, 0, 0);
            ret = std::make_shared<BinaryExpr>(ret, _operator, GetPowExpr());
        }
        else
        {
            Token _operator = Match();
            ret = std::make_shared<BinaryExpr>(ret, _operator, GetPowExpr());
        }
    }
    return ret;
}

乘方与求导的操作与加减很相似，因此我们直接来看看一元表达式的处理：

std::shared_ptr<Expr> Parser::GetUnaryExpr()
{
    Token op = Token(TokenType::NONE, 0, 0);
    bool after = true;

    if (Peek(TokenType::MINUS))
        op = Match(TokenType::MINUS);
    else if (Peek(TokenType::PLUS))
        op = Match(TokenType::PLUS);

    auto expr = GetDerivativeExpr();

    // 如果未匹配到运算符则直接返回
    if (op.Type == TokenType::NONE)
        return expr;

    return std::make_shared<UnaryExpr>(op, expr);
}

之后便是基本表达式的处理了：首先判断 '(' Expr ')' ，接下来将ax^( Expr )、ax^b、x^( Expr )、x^b、ax、x六种多项式的形式由 Token 数量由高到低依次判定，最后判定 Number 及 Var ( Expr )、Var，若至此没有遇到合适的语法，那么则会抛出Unexpected Expression异常。

对于括号产生的分组表达式，在这一步会递归调用回到加减表达式的函数，以此来保证括号改变优先级的正确性。

std::shared_ptr<Expr> Parser::GetBaseExpr()
{
    // ( Expr )
    if (Peek(TokenType::LEFT_PAREN))
    {
        Match(TokenType::LEFT_PAREN);
        auto expr = GetPlusExpr();
        Match(TokenType::RIGHT_PAREN);
        return std::make_shared<GroupingExpr>(expr);
    }
    // ax^( Expr )
    else if (Peek(TokenType::NUMBER, TokenType::X, TokenType::TIP, TokenType::LEFT_PAREN))
    {
        auto token = Match(TokenType::NUMBER);
        auto factor = std::stold(token.GetValue(Source));

        Match(TokenType::X);
        Match(TokenType::TIP);

        Match(TokenType::LEFT_PAREN);
        auto expr = GetPlusExpr();
        Match(TokenType::RIGHT_PAREN);

        auto exp = expr->Eval().AsNum();

        return std::make_shared<MonomialExpr>(factor, exp);
    }
    // ax^b
    else if (Peek(TokenType::NUMBER, TokenType::X, TokenType::TIP, TokenType::NUMBER))
    {
        auto token = Match(TokenType::NUMBER);
        auto factor = std::stold(token.GetValue(Source));

        Match(TokenType::X);
        Match(TokenType::TIP);

        token = Match(TokenType::NUMBER);
        auto exp = std::stold(token.GetValue(Source));

        return std::make_shared<MonomialExpr>(factor, exp);
    }
    // x^( Expr )
    else if (Peek(TokenType::X, TokenType::TIP, TokenType::LEFT_PAREN))
    {
        Match(TokenType::X);
        Match(TokenType::TIP);

        Match(TokenType::LEFT_PAREN);
        auto expr = GetPlusExpr();
        Match(TokenType::RIGHT_PAREN);

        auto exp = expr->Eval().AsNum();

        return std::make_shared<MonomialExpr>(1.0L, exp);
    }
    // x^b
    else if (Peek(TokenType::X, TokenType::TIP, TokenType::NUMBER))
    {
        Match(TokenType::X);
        Match(TokenType::TIP);

        auto token = Match(TokenType::NUMBER);
        auto exp = std::stold(token.GetValue(Source));

        return std::make_shared<MonomialExpr>(1.0L, exp);
    }
    // ax
    else if (Peek(TokenType::NUMBER, TokenType::X))
    {
        auto token = Match(TokenType::NUMBER);
        auto factor = std::stold(token.GetValue(Source));

        Match(TokenType::X);

        return std::make_shared<MonomialExpr>(factor, 1);
    }
    // x
    else if (Peek(TokenType::X))
    {
        Match(TokenType::X);
        return std::make_shared<MonomialExpr>(1.0L , 1);
    }
    // Number
    else if (Peek(TokenType::NUMBER))
    {
        auto token = Match(TokenType::NUMBER);
        auto number = std::stold(token.GetValue(Source));
        return std::make_shared<NumberExpr>(number);
    }
    // Var ( Expr )
    else if (Peek(TokenType::VAR, TokenType::LEFT_PAREN))
    {
        auto token = Match(TokenType::VAR);
        auto iter = Vars->find(token.GetValue(Source));

        if (iter == Vars->end())
            throw UnexpectedExpressionException(token.Start);

        Match(TokenType::LEFT_PAREN);
        auto expr = GetPlusExpr();
        Match(TokenType::RIGHT_PAREN);

        return std::make_shared<CompoundExpr>((*iter).second, expr);
    }
    // Var
    else if (Peek(TokenType::VAR))
    {
        auto token = Match(TokenType::VAR);
        auto iter = Vars->find(token.GetValue(Source));

        if(iter == Vars->end())
            throw UnexpectedExpressionException(token.Start);

        return Vars->at(token.GetValue(Source));
    }
    if (Current == End)
        throw UnexpectedEOFException();
    throw UnexpectedExpressionException((*Current).Start);
}

至此，我们转换整个表达式树的代码已经完成。

以一个例子测试：当我们的 Parser 遇到 3x^2(3x'-6)+7 时，就会产生如下的调用链，你可以在运行时输入-d的参数启用我的程序的此项输出功能：

 > 3x^2(3x'-6)+7
>> Enter Plus Expr
  >> Enter Muti Expr
    >> Enter Pow Expr
      >> Enter Unary Expr
        >> Enter Derivative Expr
          >> Enter Base Expr
            [*] expr = 3.00x^2
          << Leave Base Expr
        << Leave Derivative Expr
      << Leave Unary Expr
    << Leave Pow Expr
    [*] expr = 3.00x^2
    [*] Match Star
    >> Enter Pow Expr
      >> Enter Unary Expr
        >> Enter Derivative Expr
          >> Enter Base Expr
            >> Enter Plus Expr
              >> Enter Muti Expr
                >> Enter Pow Expr
                  >> Enter Unary Expr
                    >> Enter Derivative Expr
                      >> Enter Base Expr
                        [*] expr = 3.00x
                      << Leave Base Expr
                      [*] expr = 3.00x
                      [*] Match Single quotation
                    << Leave Derivative Expr
                  << Leave Unary Expr
                << Leave Pow Expr
              << Leave Muti Expr
              [*] expr = 3.00
              [*] Match Minus
              >> Enter Muti Expr
                >> Enter Pow Expr
                  >> Enter Unary Expr
                    >> Enter Derivative Expr
                      >> Enter Base Expr
                        [*] expr = 6.00
                      << Leave Base Expr
                    << Leave Derivative Expr
                  << Leave Unary Expr
                << Leave Pow Expr
              << Leave Muti Expr
            << Leave Plus Expr
            [*] expr = - 3.00
          << Leave Base Expr
        << Leave Derivative Expr
      << Leave Unary Expr
    << Leave Pow Expr
  << Leave Muti Expr
  [*] expr = - 9.00x^2
  [*] Match Plus
  >> Enter Muti Expr
    >> Enter Pow Expr
      >> Enter Unary Expr
        >> Enter Derivative Expr
          >> Enter Base Expr
            [*] expr = 7.00
          << Leave Base Expr
        << Leave Derivative Expr
      << Leave Unary Expr
    << Leave Pow Expr
  << Leave Muti Expr
<< Leave Plus Expr
 | 3x^2(3x'-6)+7 = 7.00 - 9.00x^2

Others

对于其他的代码欢迎在MiniCalculator中查看，关于问题也欢迎提交你的issue，如在能力范围之内，我会尽量解答。

至此本文告一段落，我写的并不详尽，仅仅挑出了我认为最主要的算法部分予以呈现。对于其他如错误处理、变量系统的处理、合法性的验证以及主函数控制等相关内容并未呈现，毕竟此文的重点并非这些问题。

希望本文能给你带来帮助，并且让你理解相关的逻辑。引用的文章十分值得一读，在此推荐给你。

Reference

1. Crafting Interpreters
2. 对 Parser 的误解 - 王垠