Грамматика выражения с оператором возведения в степень с использованием Boost Spirit

Я хотел бы добавить оператор возведения в степень к грамматика выражения, представленная в примерах Boost Spirit.

Грамматика БНФ следующая: (см. Этот ответ, например: «Однозначная грамматика для возведения в степень» )

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) ^ 4 вместо 2^ (3 ^ 4),

Как я могу переписать грамматику так, чтобы ^ становится правильным ассоциативным? Очевидно, звезда Клини, которую я использовал в определении factor это неверно. Каков метод для перевода грамматики в код Spirit? Кажется, есть способ перейти от левосторонней грамматики к реализации Духа, но я не могу увидеть это сразу.

В более формальной форме код 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

Решение

Я думаю, что вы можете использовать правильную рекурсию, чтобы получить то, что вы хотите:

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

Я не уверен в желаемом порядке оценки; Вы могли бы хотеть что-то вроде

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

вместо.

Вот простая тестовая программа, показывающая, как она справляется 2^(6/2)^4+1:

редактировать Смотрите это в прямом эфире Coliru

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;
}
3

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector