4

Boost精神のサンプルで提供されている表現文法に累乗演算子を追加したいと思います。

BNF文法は次のとおりです。

E -> E + T | E - T | T
T -> T * F | T / F | X
X -> X ^ Y | Y
Y -> i | (E)

これを次のように Boost Spirit に翻訳しました。

    template <typename Iterator>
struct calculator : qi::grammar<Iterator, ascii::space_type>
{
    calculator() : calculator::base_type(expression)
    {
        qi::uint_type uint_;

        expression =
        term
        >> *(   ('+' >> term            [&do_add])
             |   ('-' >> term            [&do_subt])
             )
        ;

        term =
        factor
        >> *(   ( '*' >> factor          [&do_mult])
             |  ('x' >> factor          [&do_mult])
             |   ('/' >> factor          [&do_div])
             );

        factor= expo >> *( '^' >> expo [&do_power]);

        expo =
           uint_                           [&do_int]
        |  '(' >> expression >> ')'
        |  ('-' >> expo[&do_neg])
        |  ('+' >> expo)

        ;
    }

    qi::rule<Iterator, ascii::space_type> expression, term, factor, expo;
};

問題は、この場合の ^ 演算子が連想のままであることです。つまり、の代わりに2 ^ 3 ^ 4として誤って解析されます。(2 ^ 3) ^ 42^ (3 ^ 4)

^右結合になるように文法を書き直すにはどうすればよいですか? 明らかに、定義で使用したクリーネ星factorは正しくありません。文法を精神コードに変換する方法は何ですか? 左因数分解された文法からスピリットの実装に移行する方法があるようですが、すぐにはわかりません。

より正式には、Spirit コードは次のようになります (指数を追加する前)。

E = T ( +T | -T ) *
T = F ( xF | /F ) *
F = int | ( E ) | +F | -F

左因数分解文法は

E  =  T E'
E' = +T E' | -T E' | epsilon
T  =  F T'
T' = *F T' | /F T' | epsilon
F  = ( E ) | int | +F | -F
4

1 に答える 1

3

正しい再帰を使用して、必要なものを取得できると思います。

factor= expo >> -('^' >> factor [&do_power]);

評価の望ましい順序についてはわかりません。あなたは次のようなものが欲しいかもしれません

factor= expo [&do_power] >> -('^' >> factor);

代わりは。

以下は、それがどのように処理されるかを示す簡単なテスト プログラム2^(6/2)^4+1です。

編集Coliruで LIVE を見る

Type an expression...or [q or Q] to quit
2^(6/2)^4+1

push 2
push 6
push 2
divide
push 4
exp
exp
push 1
add
-------------------------
Parsing succeeded

完全なコード

#define BOOST_SPIRIT_NO_PREDEFINED_TERMINALS
#define BOOST_SPIRIT_DEBUG

#include <boost/spirit/include/qi.hpp>

namespace client
{
    namespace qi = boost::spirit::qi;
    namespace ascii = boost::spirit::ascii;

    ///////////////////////////////////////////////////////////////////////////////
    //  Semantic actions
    ////////////////////////////////////////////////////////1///////////////////////
    namespace
    {
        void do_int(int n)  { std::cout << "push " << n << std::endl; }
        void do_add()       { std::cout << "add\n"; }
        void do_subt()      { std::cout << "subtract\n"; }
        void do_mult()      { std::cout << "mult\n"; }
        void do_div()       { std::cout << "divide\n"; }
        void do_power()     { std::cout << "exp\n"; }
        void do_neg()       { std::cout << "negate\n"; }
    }

    ///////////////////////////////////////////////////////////////////////////////
    //  Our calculator grammar
    ///////////////////////////////////////////////////////////////////////////////
    template <typename Iterator>
        struct calculator : qi::grammar<Iterator, ascii::space_type>
    {
        calculator() : calculator::base_type(expression)
        {
            qi::uint_type uint_;

            expression = term
                >> *(   ('+' >> term            [&do_add])
                     |  ('-' >> term            [&do_subt])
                     )
                ;

            term = factor
                >> *(   ( '*' >> factor         [&do_mult])
                     |  ('x' >> factor          [&do_mult])
                     |  ('/' >> factor          [&do_div])
                     );

            factor= expo >> -('^' >> factor [&do_power]);

            expo = uint_                        [&do_int]
                |  '(' >> expression >> ')'
                |  ('-' >> expo[&do_neg])
                |  ('+' >> expo)
            ;

            BOOST_SPIRIT_DEBUG_NODES((expression)(term)(factor)(expo));
        }
      private:
        qi::rule<Iterator, ascii::space_type> expression, term, factor, expo;
    };
}

///////////////////////////////////////////////////////////////////////////////
//  Main program
///////////////////////////////////////////////////////////////////////////////
int
main()
{
    std::cout << "/////////////////////////////////////////////////////////\n\n";
    std::cout << "Expression parser...\n\n";
    std::cout << "/////////////////////////////////////////////////////////\n\n";
    std::cout << "Type an expression...or [q or Q] to quit\n\n";

    typedef std::string::const_iterator iterator_type;
    typedef client::calculator<iterator_type> calculator;

    boost::spirit::ascii::space_type space; // Our skipper
    calculator calc; // Our grammar

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

        std::string::const_iterator iter = str.begin();
        std::string::const_iterator end = str.end();
        bool r = phrase_parse(iter, end, calc, space);

        if (r && iter == end)
        {
            std::cout << "-------------------------\n";
            std::cout << "Parsing succeeded\n";
            std::cout << "-------------------------\n";
        }
        else
        {
            std::string rest(iter, end);
            std::cout << "-------------------------\n";
            std::cout << "Parsing failed\n";
            std::cout << "stopped at: \" " << rest << "\"\n";
            std::cout << "-------------------------\n";
        }
    }

    std::cout << "Bye... :-) \n\n";
    return 0;
}
于 2013-07-12T21:46:40.607 に答える