使用 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 = 55 - 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 了。而当我们获取到一个 TokenTypeNoneToken 时,若解析尚未结束,则我们遇到了一个意料外的字符,这种时候也需要抛出异常。

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^bx^( Expr )x^baxx六种多项式的形式由 Token 数量由高到低依次判定,最后判定 NumberVar ( 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 的误解 - 王垠