4

「1.0 + 2.0 + 3.0 + ...」という形式の式を AST に解析しようとしています。バイナリ操作用に次の AST ノードがあります (完全で最小限のコード例は最後にあります)。

struct binop_t
{
    expression_t lhs, rhs;
};

「BOOST_FUSION_ADAPT_STRUCT」マクロを使用して、この構造体を boost:spirit::qi::rule で合成できるようにしたい:

BOOST_FUSION_ADAPT_STRUCT
(
    client::ast::binop_t,
    (client::ast::expression_t, lhs)
    (client::ast::expression_t, rhs)
)

つまり、二項演算 AST ノード (binop_t) には、演算対象の左側 (lhs) 式と右側 (rhs) 式の 2 つのオペランドが必要です。次の qi::grammar を使用して、「1.0+(2.0+(3.0+4.0))」という形式の式をこの AST ノードに解析できます。

qi::rule<Iterator, ast::literal_t(), ascii::space_type> literal;
qi::rule<Iterator, ast::binop_t(), ascii::space_type> binop;
qi::rule<Iterator, ast::expression_t(), ascii::space_type> primary_expr;
qi::rule<Iterator, ast::expression_t(), ascii::space_type> expr;

expr = binop.alias();

binop = primary_expr > qi::lit('+') > primary_expr;

primary_expr = (qi::lit('(') > expr > qi::lit(')')) 
             | literal
             ;

literal = qi::double_;

ただし、括弧を使用せずにそのような式を解析できるように、この文法を変更する方法を理解するのに苦労しています (例: "1+2+3+4+...")。

「calc4.cpp」ブースト スピリットの例を調べたところ、バイナリ操作 (追加など) に次の AST ノードのみを使用していることに気付きました。

struct operation
{
    optoken operator_;
    operand operand_;
};

この例と私がしようとしていることの違いは、この例では、純粋に単項演算のリストに関して、2 項演算ノードを合成するための文法が定義されていることです。単項演算のリストは、「プログラム」と呼ばれる AST ノードに合成されます。

struct program
{
    operand first;
    std::list<operation> rest;
};

この全体は、例の次の文法を使用して合成されています。

    qi::rule<Iterator, ast::program(), ascii::space_type> expression;
    qi::rule<Iterator, ast::program(), ascii::space_type> term;
    qi::rule<Iterator, ast::operand(), ascii::space_type> factor;

        expression =
            term
            >> *(   (char_('+') >> term)
                |   (char_('-') >> term)
                )
            ;

        term =
            factor
            >> *(   (char_('*') >> factor)
                |   (char_('/') >> factor)
                )
            ;

        factor =
                uint_
            |   '(' >> expression >> ')'
            |   (char_('-') >> factor)
            |   (char_('+') >> factor)
            ;

この文法では、「式」ルールは操作のリストである「プログラム」を生成します。「式」の文法ルールから、文法でクリーネ スターを使用していることがわかります。

*((char_('+') >> term)

これは、文法が「1+2+3+4+...」などの連想二項演算のチェーンを解析できる方法です。この文法の属性は list で、これは「program」AST ノードの定義と一致します。次に、電卓の「eval」関数は、「program」内の演算のリストを単純に反復し、左から右に演算をオペランドに適用します。

    int operator()(program const& x) const
    {
        int state = boost::apply_visitor(*this, x.first);
        BOOST_FOREACH(operation const& oper, x.rest)
        {
            state = (*this)(oper, state);
        }
        return state;
    }

「mini-c」Boost Spirit の例も調べましたが、非常によく似た AST 設計で、バイナリ オペレーター AST ノードはありません (単一のオペランドを受け入れる単一の「オペレーター」ノードのみ)。

以下は、これまでに実装したプログラムの完全で最小限のコード例です。要約すると、私の質問は次のとおりです。「1 + 2 + 3 + 4 + ...」のような式からbinop_t ASTノードのツリーを合成できるように、このプログラムを変更するにはどうすればよいですか?入力テキスト：

#include <boost/variant.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <iostream>
#include <string>
#include <exception>

using boost::variant;
using boost::recursive_wrapper;

namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;

namespace client { namespace ast {

    struct literal_t;
    struct binop_t;

    typedef variant< recursive_wrapper<literal_t>,
                     recursive_wrapper<binop_t>
                   > expression_t;

    struct literal_t
    {
        double value;       
    };

    struct binop_t
    {
        expression_t lhs, rhs;
    };
}} // ns

BOOST_FUSION_ADAPT_STRUCT
(
    client::ast::literal_t,
    (double, value)
)

BOOST_FUSION_ADAPT_STRUCT
(
    client::ast::binop_t,
    (client::ast::expression_t, lhs)
    (client::ast::expression_t, rhs)
)

namespace client {
    template <typename Iterator>
    struct grammar_t : qi::grammar<Iterator, ast::expression_t(), ascii::space_type>
    {
        qi::rule<Iterator, ast::literal_t(), ascii::space_type> literal;
        qi::rule<Iterator, ast::binop_t(), ascii::space_type> binop;
        qi::rule<Iterator, ast::expression_t(), ascii::space_type> primary_expr;
        qi::rule<Iterator, ast::expression_t(), ascii::space_type> expr;

        grammar_t() : grammar_t::base_type(expr)
        {
            expr = binop.alias();

            binop = primary_expr > qi::lit('+') > primary_expr;

            primary_expr = (qi::lit('(') > expr > qi::lit(')')) 
                         | literal;

            literal = qi::double_;

            expr.name("expr");
            binop.name("binop");
            literal.name("literal");
            qi::debug(expr);
            qi::debug(binop);
            qi::debug(literal);
        }
    };
} // ns

int main()
{
    try
    {
        string input = "0.1 + 1.2 ";
        std::string::const_iterator begin = input.begin();
        std::string::const_iterator end = input.end();  

        typedef std::string::const_iterator iterator_type;
        client::grammar_t<iterator_type> g;

        client::ast::expression_t ast;

        bool status;    
        status = qi::phrase_parse(begin, end, g, ascii::space, ast);
        EXPECT_TRUE(status);
        EXPECT_TRUE(begin == end);
    } catch (std::exception& e)
    {
        cout << e.what() << endl;
    }
}
4

1 に答える 1

3

freenode の ##spirit IRC チャンネルの VeXocide が問題を解決しました ( http://codepad.org/wufmFufE )。答えは、次のように文法を変更することです。

    expr = binop.alias();

    binop = primary_expr >> qi::lit('+') >> (binop | primary_expr);

    primary_expr = (qi::lit('(') >> expr >> qi::lit(')'))
                 | literal;            

    literal = qi::double_;

この文法は、探している構文木を合成できる正しい再帰を作成します。

同じ問題に遭遇した人へのヒント: Spirit デバッグ ステートメントがないと、Boost Spirit に左再帰文法を指定すると、スタック オーバーフローが原因で Seg Fault が発生します。デバッグ ステートメントをオンにすると、パーサーで問題が発生していることを示す "無限" の量のテキストが出力されます。

于 2013-05-22T14:14:07.580 に答える