正如聊天中建议的那样,您可以从以下内容开始:
expression = addition | simple;
addition = simple >>
( ('+' > expression)
| ('-' > expression)
);
simple = '(' > expression > ')' | call | unary | number;
call = id >> *expression;
unary = qi::char_("-+") > expression;
// terminals
id = qi::lexeme[+qi::char_("a-z")];
number = qi::double_;
从那时起,我在 C++ 中通过 AST 演示实现了这一点,因此您可以通过漂亮的打印来了解该语法实际上是如何构建表达式树的。
所有源代码都在github上:https ://gist.github.com/2152518
有两个版本(向下滚动到“替代”以了解更多信息
语法:
template <typename Iterator>
struct mini_grammar : qi::grammar<Iterator, expression_t(), qi::space_type>
{
qi::rule<Iterator, std::string(), qi::space_type> id;
qi::rule<Iterator, expression_t(), qi::space_type> addition, expression, simple;
qi::rule<Iterator, number_t(), qi::space_type> number;
qi::rule<Iterator, call_t(), qi::space_type> call;
qi::rule<Iterator, unary_t(), qi::space_type> unary;
mini_grammar() : mini_grammar::base_type(expression)
{
expression = addition | simple;
addition = simple [ qi::_val = qi::_1 ] >>
+(
(qi::char_("+-") > simple) [ phx::bind(&append_term, qi::_val, qi::_1, qi::_2) ]
);
simple = '(' > expression > ')' | call | unary | number;
call = id >> *expression;
unary = qi::char_("-+") > expression;
// terminals
id = qi::lexeme[+qi::char_("a-z")];
number = qi::double_;
}
};
相应的 AST 结构是使用非常强大的 Boost Variant 快速定义的:
struct addition_t;
struct call_t;
struct unary_t;
typedef double number_t;
typedef boost::variant<
number_t,
boost::recursive_wrapper<call_t>,
boost::recursive_wrapper<unary_t>,
boost::recursive_wrapper<addition_t>
> expression_t;
struct addition_t
{
expression_t lhs;
char binop;
expression_t rhs;
};
struct call_t
{
std::string id;
std::vector<expression_t> args;
};
struct unary_t
{
char unop;
expression_t operand;
};
BOOST_FUSION_ADAPT_STRUCT(addition_t, (expression_t, lhs)(char,binop)(expression_t, rhs));
BOOST_FUSION_ADAPT_STRUCT(call_t, (std::string, id)(std::vector<expression_t>, args));
BOOST_FUSION_ADAPT_STRUCT(unary_t, (char, unop)(expression_t, operand));
在完整的代码中,我还为这些结构重载了 operator<<。
完整演示
//#define BOOST_SPIRIT_DEBUG
#include <iostream>
#include <iterator>
#include <string>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted.hpp>
#include <boost/optional.hpp>
namespace qi = boost::spirit::qi;
namespace phx= boost::phoenix;
struct addition_t;
struct call_t;
struct unary_t;
typedef double number_t;
typedef boost::variant<
number_t,
boost::recursive_wrapper<call_t>,
boost::recursive_wrapper<unary_t>,
boost::recursive_wrapper<addition_t>
> expression_t;
struct addition_t
{
expression_t lhs;
char binop;
expression_t rhs;
friend std::ostream& operator<<(std::ostream& os, const addition_t& a)
{ return os << "(" << a.lhs << ' ' << a.binop << ' ' << a.rhs << ")"; }
};
struct call_t
{
std::string id;
std::vector<expression_t> args;
friend std::ostream& operator<<(std::ostream& os, const call_t& a)
{ os << a.id << "("; for (auto& e : a.args) os << e << ", "; return os << ")"; }
};
struct unary_t
{
char unop;
expression_t operand;
friend std::ostream& operator<<(std::ostream& os, const unary_t& a)
{ return os << "(" << a.unop << ' ' << a.operand << ")"; }
};
BOOST_FUSION_ADAPT_STRUCT(addition_t, (expression_t, lhs)(char,binop)(expression_t, rhs));
BOOST_FUSION_ADAPT_STRUCT(call_t, (std::string, id)(std::vector<expression_t>, args));
BOOST_FUSION_ADAPT_STRUCT(unary_t, (char, unop)(expression_t, operand));
void append_term(expression_t& lhs, char op, expression_t operand)
{
lhs = addition_t { lhs, op, operand };
}
template <typename Iterator>
struct mini_grammar : qi::grammar<Iterator, expression_t(), qi::space_type>
{
qi::rule<Iterator, std::string(), qi::space_type> id;
qi::rule<Iterator, expression_t(), qi::space_type> addition, expression, simple;
qi::rule<Iterator, number_t(), qi::space_type> number;
qi::rule<Iterator, call_t(), qi::space_type> call;
qi::rule<Iterator, unary_t(), qi::space_type> unary;
mini_grammar() : mini_grammar::base_type(expression)
{
expression = addition | simple;
addition = simple [ qi::_val = qi::_1 ] >>
+(
(qi::char_("+-") > simple) [ phx::bind(&append_term, qi::_val, qi::_1, qi::_2) ]
);
simple = '(' > expression > ')' | call | unary | number;
call = id >> *expression;
unary = qi::char_("-+") > expression;
// terminals
id = qi::lexeme[+qi::char_("a-z")];
number = qi::double_;
BOOST_SPIRIT_DEBUG_NODE(expression);
BOOST_SPIRIT_DEBUG_NODE(call);
BOOST_SPIRIT_DEBUG_NODE(addition);
BOOST_SPIRIT_DEBUG_NODE(simple);
BOOST_SPIRIT_DEBUG_NODE(unary);
BOOST_SPIRIT_DEBUG_NODE(id);
BOOST_SPIRIT_DEBUG_NODE(number);
}
};
std::string read_input(std::istream& stream) {
return std::string(
std::istreambuf_iterator<char>(stream),
std::istreambuf_iterator<char>());
}
int main() {
std::cin.unsetf(std::ios::skipws);
std::string const code = read_input(std::cin);
auto begin = code.begin();
auto end = code.end();
try {
mini_grammar<decltype(end)> grammar;
qi::space_type space;
std::vector<expression_t> script;
bool ok = qi::phrase_parse(begin, end, *(grammar > ';'), space, script);
if (begin!=end)
std::cerr << "Unparsed: '" << std::string(begin,end) << "'\n";
std::cout << std::boolalpha << "Success: " << ok << "\n";
if (ok)
{
for (auto& expr : script)
std::cout << "AST: " << expr << '\n';
}
}
catch (qi::expectation_failure<decltype(end)> const& ex) {
std::cout << "Failure; parsing stopped after \""
<< std::string(ex.first, ex.last) << "\"\n";
}
}
选择:
我有一个替代版本,它以addition_t
迭代方式而不是递归方式构建,可以这么说:
struct term_t
{
char binop;
expression_t rhs;
};
struct addition_t
{
expression_t lhs;
std::vector<term_t> terms;
};
这消除了使用 Phoenix 来构建表达式的需要:
addition = simple >> +term;
term = qi::char_("+-") > simple;