使用Boost Spirit使用指数运算符的表达语法 [英] Expression grammar with exponentiation operator using Boost Spirit
问题描述
我想将幂运算符添加到 Boost精神示例中提供的表达语法.
I would like to add the exponentiation operator to the expression grammar provided in the Boost spirit samples.
BNF语法如下:(例如，请参见以下答案:求幂运算的明确语法" )
The BNF grammar is the following: (see this answer for example: "Unambiguous grammar for exponentiation operation" )
E -> E + T | E - T | T
T -> T * F | T / F | X
X -> X ^ Y | Y
Y -> i | (E)
我这样翻译成Boost精神:
which I translated to Boost spirit like this:
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).
The problem is that the ^ operator in this case is left associative, ie 2 ^ 3 ^ 4 is parsed incorrectly as (2 ^ 3) ^ 4 instead of 2^ (3 ^ 4).
我该如何重写语法，使^正确关联?显然，我在factor的定义中使用的Kleene星是不正确的.将语法转换为Spirit代码的方法是什么?似乎有一种方法可以从左手分解的语法过渡到Spirit的实现，但我无法立即看到它.
How may I rewrite the grammar so that ^ becomes right associative? Obviously the Kleene star I used in the definition of factor is incorrect. What is the method to translate a grammar to Spirit code ? There seems to be a way to go from the left-factored grammar to the Spirit implementation but I can't see it immediately.
以更正式的方式，Spirit代码如下所示(在我尝试添加指数之前):
In a more formal way, the Spirit code looks like this (before I tried to add the exponent):
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
推荐答案
我认为您可以采用正确的递归来获得所需的内容:
I think you can employ right recursion to get what you want:
factor= expo >> -('^' >> factor [&do_power]);
我不确定所需的评估顺序；你可能想要类似的东西
I'm not sure about the desired order of evaluation; you could want something like
factor= expo [&do_power] >> -('^' >> factor);
相反.
这是一个简单的测试程序，显示了它如何处理 2^(6/2)^4+1 :
Here's a simple test program showing it how it handles 2^(6/2)^4+1:
编辑可在 Coliru在线观看
Edit See it LIVE on 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;
}
这篇关于使用Boost Spirit使用指数运算符的表达语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
