c++ - 帮助提升精神 AST

Question

作为大学研究工作的一部分，我正在编写一个用于分析简单 B 机替代的小工具。该代码成功解析了 mySubst := var1 + var2 形式的测试输入。但是，我收到一条弹出错误消息，指出“此应用程序已请求运行时以异常方式终止它。”在命令提示符窗口中，我收到一条“断言失败消息”。主要程序如下:

// BMachineTree.cpp : Defines the entry point for the console application.
//

/*=============================================================================
    Copyright (c) 2010 Temitope Onunkun
=============================================================================*/
///////////////////////////////////////////////////////////////////////////////
//
//  UUsing Boost Spririt Trees (AST) to parse B Machine Substitutions.
//
///////////////////////////////////////////////////////////////////////////////
#define BOOST_SPIRIT_DUMP_PARSETREE_AS_XML

#include <boost/spirit/core.hpp>
#include <boost/spirit/tree/ast.hpp>
#include <boost/spirit/tree/tree_to_xml.hpp>
#include "BMachineTreeGrammar.hpp"

#include <iostream>
#include <stack>
#include <functional>
#include <string>
#include <cassert>
#include <vector>

#if defined(BOOST_SPIRIT_DUMP_PARSETREE_AS_XML)
#include <map>
#endif

// Using AST to parse B Machine substitutions
////////////////////////////////////////////////////////////////////////////
using namespace std;
using namespace boost::spirit;

typedef char const*         iterator_t;
typedef tree_match<iterator_t> parse_tree_match_t;
typedef parse_tree_match_t::tree_iterator iter_t;

////////////////////////////////////////////////////////////////////////////
string evaluate(parse_tree_match_t hit);
string eval_machine(iter_t const& i);

vector<string> dx;
string evaluate(tree_parse_info<> info)
{
    return eval_machine(info.trees.begin());
}

string eval_machine(iter_t const& i)
{
    cout << "In eval_machine. i->value = " <<
        string(i->value.begin(), i->value.end()) <<
        " i->children.size() = " << i->children.size() << endl;

    if (i->value.id() == substitution::leafValueID)
    {
        assert(i->children.size() == 0);

        // extract string tokens
        string leafValue(i->value.begin(), i->value.end());

                dx.push_back(leafValue.c_str());
        return leafValue.c_str();
    }
    //
    else if (i->value.id() == substitution::termID)
    {
        if ( (*i->value.begin() == '*') || (*i->value.begin() == '/') )
        {
            assert(i->children.size() == 2);

                        dx.push_back( eval_machine(i->children.begin()) );
                        dx.push_back( eval_machine(i->children.begin()+1) );
            return eval_machine(i->children.begin()) + " " +
                eval_machine(i->children.begin()+1);
        }
                //
       else
            assert(0);
    }
    else if (i->value.id() == substitution::expressionID)
    {
        if ( (*i->value.begin() == '+') || (*i->value.begin() == '-') )
        {
            assert(i->children.size() == 2);

                        dx.push_back( eval_machine(i->children.begin()) );
                        dx.push_back( eval_machine(i->children.begin()+1) );
            return eval_machine(i->children.begin()) + " " +
                eval_machine(i->children.begin()+1);
        }
                else
           assert(0);
        }
        //
        else if (i->value.id() == substitution::simple_substID)
    {
                if (*i->value.begin() == (':' >> '=') )
                {
                        assert(i->children.size() == 2);

                        dx.push_back( eval_machine(i->children.begin()) );
                        dx.push_back( eval_machine(i->children.begin()+1) );
            return eval_machine(i->children.begin()) + "|->" +
                eval_machine(i->children.begin()+1);

                }
        else
            assert(0);
    }
    else
    {
        assert(0); // error
    }

    return 0;
}

////////////////////////////////////////////////////////////////////////////
int
main()
{
    // look in BMachineTreeGrammar for the definition of BMachine
    substitution BMach_subst;

    cout << "/////////////////////////////////////////////////////////\n\n";
    cout << "\t\tB Machine Substitution...\n\n";
    cout << "/////////////////////////////////////////////////////////\n\n";
    cout << "Type an expression...or [q or Q] to quit\n\n";

    string str;
    while (getline(cin, str))
    {
        if (str.empty() || str[0] == 'q' || str[0] == 'Q')
            break;

        tree_parse_info<> info = ast_parse(str.c_str(), BMach_subst, space_p);

        if (info.full)
        {
#if defined(BOOST_SPIRIT_DUMP_PARSETREE_AS_XML)
            // dump parse tree as XML
            std::map<parser_id, std::string> rule_names;
                        rule_names[substitution::identifierID] = "identifier";
            rule_names[substitution::leafValueID] = "leafValue";
            rule_names[substitution::factorID] = "factor";
            rule_names[substitution::termID] = "term";
            rule_names[substitution::expressionID] = "expression";
                        rule_names[substitution::simple_substID] = "simple_subst";
            tree_to_xml(cout, info.trees, str.c_str(), rule_names);
#endif

            // print the result
                        cout << "Variables in Vector dx: " << endl;
                        for(vector<string>::iterator idx = dx.begin(); idx < dx.end(); ++idx)
                                cout << *idx << endl;
            cout << "parsing succeeded\n";
            cout << "result = " << evaluate(info) << "\n\n";
        }
        else
        {
            cout << "parsing failed\n";
        }
    }

    cout << "Bye... :-) \n\n";
    return 0;
}

BMachineTreeGrammar.hpp 文件中定义的语法如下:

/*=============================================================================
    Copyright (c) 2010 Temitope Onunkun
    http://www.dcs.kcl.ac.uk/pg/onun

    Use, modification and distribution is subject to the Boost Software
    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
#ifndef BOOST_SPIRIT_BMachineTreeGrammar_HPP_
#define BOOST_SPIRIT_BMachineTreeGrammar_HPP_

using namespace boost::spirit;

///////////////////////////////////////////////////////////////////////////////
//
//  Using Boost Spririt Trees (AST) to parse B Machine Substitutions.
//
///////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////
//
//  B Machine Grammar
//
////////////////////////////////////////////////////////////////////////////
struct substitution : public grammar<substitution>
{
        static const int identifierID = 1;
    static const int leafValueID = 2;
    static const int factorID = 3;
    static const int termID = 4;
    static const int expressionID = 5;
        static const int simple_substID = 6;


    template <typename ScannerT>
    struct definition
    {
        definition(substitution const& )
        {
            //  Start grammar definition
            identifier   = alpha_p >> (+alnum_p | ch_p('_') )
                                                ;

                        leafValue        = leaf_node_d[
                                                        lexeme_d[ identifier | +digit_p ] ]
                                                ;

                        factor          = leafValue
                                                | inner_node_d[ ch_p( '(' ) >> expression
                                                >> ch_p(')' ) ]
                                                ;

                        term            = factor >>
                                                  *(  (root_node_d[ch_p('*') ] >> factor )
                                                    | (root_node_d[ch_p('/') ] >> factor )
                                                   );

                        expression       = term >>
                                                  *(  (root_node_d[ch_p('+') ] >> term )
                                                    | (root_node_d[ch_p('-') ] >> term )
                                                   );

                        simple_subst= leaf_node_d[
                                                        lexeme_d[ identifier ] ]
                                                >> root_node_d[str_p(":=")] >> expression
                                                ;

            //  End grammar definition

            // turn on the debugging info.
                        BOOST_SPIRIT_DEBUG_RULE(identifier);
            BOOST_SPIRIT_DEBUG_RULE(leafValue);
            BOOST_SPIRIT_DEBUG_RULE(factor);
            BOOST_SPIRIT_DEBUG_RULE(term);
            BOOST_SPIRIT_DEBUG_RULE(expression);
                        BOOST_SPIRIT_DEBUG_RULE(simple_subst);
        }

                rule<ScannerT, parser_context<>, parser_tag<simple_substID> > simple_subst;
        rule<ScannerT, parser_context<>, parser_tag<expressionID> >   expression;
        rule<ScannerT, parser_context<>, parser_tag<termID> >         term;
        rule<ScannerT, parser_context<>, parser_tag<factorID> >       factor;
        rule<ScannerT, parser_context<>, parser_tag<leafValueID> >    leafValue;
                rule<ScannerT, parser_context<>, parser_tag<identifierID> >   identifier;

        rule<ScannerT, parser_context<>, parser_tag<simple_substID> > const&
        start() const { return simple_subst; }
    };
};

#endif

我运行程序得到的输出是:

/////////////////////////////////////////////////////////

                B Machine Substitution...

/////////////////////////////////////////////////////////

Type an expression...or [q or Q] to quit

mySubst := var1 - var2

parsing succeeded
In eval_machine. i->value = := i->children.size() = 2
Assertion failed: 0, file c:\redmound\bmachinetree\bmachinetree\bmachinetree.cpp
, line 114

对于解决此问题的任何帮助，我将不胜感激。

Answer 1

您的断言在第 114 行失败，因为您假设每个节点都有一个关联的 ID。它们不会:在这种情况下，您定义的运算符(:=、+、- 等)都没有 ID与他们相关。

FWIW，@hkaiser 是对的:您真的应该使用 Spirit V2。它的 AST 概念比经典的 Spirit 好得多(也更容易使用)。