在 Boost Spirit 解析器框架中实现语义操作

• 下载源文件 - 14.2 Kb
• 下载演示项目 - 11.8 Kb

引言

在我上一篇 Code Project 文章《Boost Spirit 解析器框架简介》中，我介绍了一些 boost::spirit 解析器框架的基本概念。在那篇文章中，我创建了成功解析简单模运算计算器输入的必要代码。在本文中，我将添加必要的代码来对输入执行语义动作，从而提供一个功能齐全的模运算计算器。

背景

解析文件、命令行或其他来源的输入有多种方法。尽管如此，所有这些技术都必须执行两个基本功能。要执行的第一个动作是理解输入的结构，确保它符合该输入规定的规范。在此之后，我们必须执行语义动作。什么是语义动作？语义学是从某物中提取意义的科学，因此语义动作涉及基于某物的意义来执行动作。在解析器的上下文中，语义动作是在每次成功解析出输入的一部分时被调用的代码。

在 Spirit 框架中，添加语义动作非常简单。在语法定义的任何规则的任何部分之后，都可以添加一个语义动作。每当规则的特定部分成功匹配时，都会调用此语义动作。这个过程是许多其他解析器（例如 Yacc）所能实现的功能的强大扩展。对于熟悉 Yacc 的人来说，您会知道语法中的每个规则后面都可以跟随一些嵌入的伪 C 代码。Spirit 更进一步，允许将语义动作附加到规则的任何部分。以下是一个处理逗号分隔的有符号整数列表的示例：

integers = int_p[ProcessInt()] >>
    *( ',' int_p[ProcessInt()] )
    ;

这段代码说明，整数规则被定义为一个整数，后跟零个或多个附加整数，以逗号分隔。每处理一个整数后，框架都会调用函数对象 ProcessInt()，并将已处理的整数传递给它。我将在本文后面的部分详细介绍这些函数对象的细节。

处理输入的方式有很多种。对于简单的命令行计算器，通常可以像接收输入一样直接处理输入，并使用求值堆栈。事实上，Spirit 库附带的演示项目中的计算器就使用了这个概念。我决定在这种情况下，演示一种与解析相关的另一种常用工具，即将输入转换为复合树。

使用复合模式建模输入

许多输入格式可以通过从解析器生成复合树来成功解析。XML 或 VRML 解析器等显而易见的例子立即浮现，但还有其他文件格式也可以合理地解析为树。例如：SQL 脚本或数学表达式。一旦有了复合树，执行各种操作就变成了一个编写适当的复合访问者的问题。访问者可以轻松地将树重新输出为新的文件格式，或输出程序编辑过的数据。另一个访问者可以用于将树转换为不同的数据结构，或求值树。可能性是无穷的。

在本文中，我使用了之前我写的一篇题为《Composites and Visitors - a Templatised Approach》的文章中的代码。这篇文章提供了一个通用的复合基类，并提供了各种以特定顺序访问整个复合树的方案。

为了编写我的模运算计算器，我编写了一个具有多个不同节点的复合树。其中最重要的是一个根节点，它位于树的根部，所有其他节点都位于其下方。编写这个根节点的原因涉及编写将输入转换为复合树的解析器的一个特定细节。通常，在编写生成复合树的解析器时，您倾向于从叶节点开始创建树，而不是从根节点开始。我倾向于通过在一个自定义的根节点下增长树来解决这个问题。每当创建树中的一个节点时，它都会被添加到根节点。最初，添加叶节点，但随着复合节点的添加，它们会将某些叶节点从根节点下方分离出来，并将它们添加到自己的子节点列表中。这就从根节点开始增长树，逐渐将其他节点推向下层。对于熟悉构建平衡二叉树过程的人来说，这个过程非常相似。下图演示了这个过程

通过这个过程，我们可以看到前两个步骤涉及将数字叶节点添加到根节点。下一步涉及添加一个加法运算符，该运算符负责两个子节点，并将它们附加到根节点下方。因此，根节点包含一个执行此操作的函数：

void 
CTreeRoot::AddParent( CExpressionTree *node )
{
    // Take the last 2 children from the root, add them to the new node
    CExpressionTree *last1 = NULL, *last2 = NULL;
    shallow_iterator iter = begin_shallow();
    for ( ; iter != end_shallow(); ++iter )
    {
        last2 = last1;
        last1 = *iter;
    }
    if ( last1 == NULL || last2 == NULL )
    {
        assert( false );
        delete node;
        return;
    }
    node->push_back( remove( last2 ) );
    node->push_back( remove( last1 ) );
    // Now add the new node to the tree
    push_back( node );
}

您可以看到，这个函数查找根节点下的最后两个节点，将它们从根节点移除，并将它们添加到新节点，然后将新节点添加到根节点下方。

复合树中的其他节点代表表达式语法中的各种基本实体，例如整数，以及加号或减号等各种运算符。

我为复合树编写了两个访问者。第一个是左到右访问者，它将打印树所表示的表达式。第二个是自底向上访问者，它求值树所表示的表达式。

class CCalculateTreeVisitor :
    public CVisitorBase,
    public Types::CVisitorBottomToTop<CCalculateTreeVisitor, CExpressionTree>
{
public:
    CCalculateTreeVisitor( unsigned int modular ) : m_modular( modular ) {}
    virtual ~CCalculateTreeVisitor() {}

    virtual void Visit( COperatorPlus &node );
    virtual void Visit( COperatorMinus &node );
    virtual void Visit( COperatorMultiply &node );
    virtual void Visit( COperatorDivide &node );
    virtual void Visit( COperatorUnaryMinus &node );
    virtual void Visit( CValue &node );

    int pop();
    void push( int value );

protected:
    int ReturnModular( int value ) const;

private:
    unsigned int m_modular;
    std::stack<INT> m_eval;
};

此访问者的类定义不言自明。当复合结构从树的底部到顶部进行访问时，访问每个节点的结果会被放入堆栈中。运算符节点的工作方式与 Forth 解释器非常相似；例如，加法节点会从堆栈中弹出顶部两个元素，计算它们的和，然后将结果推入堆栈。

void 
CCalculateTreeVisitor::Visit( COperatorPlus &node )
{
    int b = pop(), a = pop();
    push( ReturnModular( a + b ) );
}

其他运算符节点也大同小异。

向 Spirit 解析器添加语义动作

定义表达式树的复合结构和访问者的准备工作使我们能够进行将语义动作添加到现有计算器解析器的重要工作。正如我已经说过的，向 Spirit 解析器添加语义动作的过程非常简单。它依赖于使用函数指针，或者以更面向对象的方式，使用函数对象来从解析器回调到父应用程序。

定义语义动作函数对象

函数对象（Functor）本质上是实现了函数调用运算符 operator() 的类。这意味着它们可以同时作为类和函数指针使用。Spirit 框架使用函数指针或函数对象来从解析器回调到您的应用程序。我个人推荐使用函数对象，因为它们具有更强的面向对象特性。函数对象本身必须遵循一个固定的格式，Spirit 框架支持其中几种。以下演示了其中两种：

struct AddChild
{
public:
    AddChild( CParser &parser, createPtr create ) :
        m_parser( parser ), m_create( create ) {}
    template <typename IteratorT>
    void operator()( IteratorT, IteratorT ) const
    {
        m_parser.GetRoot()->AddChild( m_create() );
    }
    template <typename IteratorT>
    void operator()( IteratorT ) const
    {
        m_parser.GetRoot()->AddChild( m_create() );
    }
private:
    CParser &m_parser;
    createPtr m_create;
};

这里，我们有两个 operator()，一个接受单个 IteratorT，另一个接受一对 IteratorTs。如果您正在解析标准字符串，Spirit 框架将使用这些的 char const* 特化。当您将动作附加到单个字符解析器（例如 ch_p 解析器）时，将调用单参数版本。在大多数其他情况下，将使用双参数版本。迭代器参数允许您访问刚刚解析的输入，尽管在此示例中我不需要输入。

在设计函数对象时，了解这些函数对象的生命周期很重要。每次使用语义动作时，都不会创建新的函数对象，而是同一个函数对象存在于语法对象的整个生命周期内。因此，我使用函数指针 createPtr 来构建示例函数对象，该函数指针可用于创建新的必要表达式树节点，而不是在构造时传递新对象，否则系统将尝试在每次调用函数对象时添加相同的对象。作为一般经验法则，您应该保持这些函数对象轻量级。Spirit 框架可以按值传递它们很多次，所以不要给它们加载大量成员变量，除非您想牺牲解析速度。函数对象应该真正被视为解析器与应用程序其余部分之间的通信点。

当您解析数值时，可以使用其他函数对象签名。如果您使用内置的数字解析器，例如 uint_p 解析器将需要一个接受单个 unsigned int 的函数对象。这可以在下图中看到：

struct AddNumericChild
{
public:
    AddNumericChild( CParser &parser ) : m_parser( parser ) {}
    void operator()( unsigned int num ) const
    {
        m_parser.GetRoot()->AddChild( new CValue( (int) num ) );
    }
private:
    CParser &m_parser;
};

在解析器和应用程序之间进行通信

解析器和应用程序之间的通信通常涉及两个阶段。首先，您需要将函数对象放置在语法中的合适位置。其次，您需要确保函数对象能够将任何操作适当地传递给应用程序。如果您回顾上面定义的两个函数对象，它们都接受对 CParser 的引用，在当前应用程序的情况下，CParser 是整体的管理类。通过存储此引用，函数对象获得了一种轻量级的方式来回传到应用程序，在这两种情况下都是将新子节点添加到复合树。

为了演示将函数对象放置在语法中的过程，我将向您展示语法的一部分：

definition( Syntax const &self )
{
    // Parse a single integer, calling the AddNumericChild functor
    integer =
        uint_p[ Private::AddNumericChild( self.m_parser ) ]
        ;
    // Parse a bracketed expression, a single integer, or a unary
    // plus or minus.  The unary minus is dealt with by adding
    // appropriate nodes into the tree
    factor =
        integer |
        '(' >> expression >> ')' |
        ( ch_p('-')[ Private::AddChild( self.m_parser, &CEmpty::Create ) ] >> factor )
            [ Private::AddParent( self.m_parser, &COperatorUnaryMinus::Create ) ] |
        ( '+' >> factor )
        ;
    // Parse a multiply or divide expression, adding appropriate
    // nodes into the tree
    term =
        factor
        >> *( ( '*' >> factor )
                [ Private::AddParent( self.m_parser, &COperatorMultiply::Create ) ]
            | ( '/' >> factor )
                [ Private::AddParent( self.m_parser, &COperatorDivide::Create ) ]
            )
        ;
    // Parse a plus or minus expression, adding appropriate nodes
    // into the tree
    expression =
        term
        >> *( ( '+' >> term )
                [ Private::AddParent( self.m_parser, &COperatorPlus::Create ) ]
            | ( '-' >> term )
                [ Private::AddParent( self.m_parser, &COperatorMinus::Create ) ]
            )
        ;
}

所有函数对象都已在 Private 命名空间中定义。

一旦输入被解析，表达式树将存在于 m_parser 对象中。您可以访问此树以获取表达式的结果，或以格式化的方式打印树。例如：

CCalculateTreeVisitor value( m_parser.GetModular() );
value( m_parser.GetRoot() );
int result = value.pop();

此代码将模运算的基数设置在 CCalculateTreeVisitor 上，在表达式树上运行访问者，并从访问者堆栈的顶部获取结果。

兼容性

本文的代码依赖于 boost::spirit 库和 Loki 库。这两个库都应该已安装并设置在您的 include 路径中，以便代码能够编译。此外，由于这两个库都依赖于尖端的语言特性，因此代码只能在 Visual C++ 7.1 或更高版本上编译。还要注意，许多简单的编译错误即使在最新的 Microsoft 编译器中也会以奇怪的方式报告。例如，如果您使用的函数对象尚未定义，您经常会遇到 C1001，内部编译器错误。

结论

一旦您在 Spirit 框架中创建了一个解析器，插入语义动作就非常容易了。只要您遵循将函数对象保持轻量级的规则，并且您记住了解析器通过这些函数对象回调到主应用程序的方式，您应该不会遇到太多问题。Spirit 框架是创建高度面向对象的解析器的一个非常强大的方法。复杂的语法和尖端语言特性的使用并不适合胆小者，但我认为学习该框架所需的努力将得到丰厚的回报。

历史

2004 年 10 月 10 日：版本 1 发布。