Грамматика выражения с оператором возведения в степень с использованием 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
Решение
Я думаю, что вы можете использовать правильную рекурсию, чтобы получить то, что вы хотите:
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;
}
Другие решения
Других решений пока нет …