I am a bit of a newbee using Spirit.
I am trying to construct an AST tree from a simple "excel" formula using spirit x3. The grammar supports typical operators (+,-,*,/), functions (myfunc(myparam1, myparam2)) and cell references (eg A1, AA234).
So an example expression to be parsed might be A1 + sin(A2+3).
The problem is that the xlreference rule below never gets matched as the xlfunction rule takes precedence and the rule does not backtrack. I have experimented with expect, but I am lacking a few good examples to get it going.
I guess this leads onto another question relating to what is the best way to debug x3. I have seen the BOOST_SPIRIT_X3_DEBUG define, but I could not find any examples that demonstrated it's usage. I am also wrote an on_error method on the expression_class but this does not provide a good trace. I have tried to use the position tagging and with statement but this also does not provide enough information.
Any help would be appreciated!
x3::rule<class xlreference, ast::xlreference> const xlreference{"xlreference"};
auto const xlreference_def = +alpha > x3::uint_ > !x3::expect[char('(')];
BOOST_SPIRIT_DEFINE(xlreference);
struct identifier_class;
typedef x3::rule<identifier_class, std::string> identifier_type;
identifier_type const identifier = "identifier";
auto const identifier_def = x3::char_("a-zA-Z") > *(x3::char_("a-zA-Z") | x3::char_('_')) > !x3::expect[char('0-9')];
BOOST_SPIRIT_DEFINE(identifier);
auto const expression_def = // constadditive_expr_def
term [print_action()]
>> *( (char_('+') > term)
| (char_('-') > term)
)
;
x3::rule<xlfunction_class, ast::xlfunction> const xlfunction("xlfunction");
auto const xlfunction_def = identifier > '(' > *(expression > *(',' > expression)) > ')';
BOOST_SPIRIT_DEFINE(xlfunction);
auto const term_def = //constmultiplicative_expr_def
factor
>> *( (char_('*') > factor)
| (char_('/') > factor)
)
;
auto const factor_def = // constunary_expr_def
xlfunction [print_action()]
| '(' > expression > ')'
| (char_('-') > factor)
| (char_('+') > factor)
| x3::double_ [print_action()] | xlreference [print_action()]
;
The error handler:
struct expression_class //: x3::annotate_on_success
{
// Our error handler
template <typename Iterator, typename Exception, typename Context>
x3::error_handler_result
on_error(Iterator& q, Iterator const& last, Exception const& x, Context const& context)
{
std::cout
<< "Error! Expecting: "
<< x.which()
<< " here: \""
<< std::string(x.where(), last)
<< "\""
<< std::endl
;
return x3::error_handler_result::fail;
}
};
Position tag:
with<position_cache_tag>(std::ref(positions))
[
client::calculator_grammar::expression
];
client::ast::program ast;
bool r = phrase_parse(iter, (iterator_type const ) str.end(), parser, x3::space, ast);
if (!r) {
std::cout << "failed:" << str << "\n";
}
Okay, taking the review one step at a time. Making up AST types along the way (because you didn't care to show).
This is invalid code: char('0-9'). Is that a wide-character literal? Enable your compiler warnings! You probably meant x3::char_("0-9") (two important differences!).
!x3::expect[] is a contradiction. You can never pass that condition, because ! asserts the lookahead is NOT matched, while expect[] REQUIRES a match. So, best case ! fails because the expect[]-ation is matched. Worst case expect[] throws an exception because you asked it to.
operator > is already an expectation point. For the same reason as before > !p is a contradiction. Make it >> !p
Replace char_("0-9") with x3::digit
Replace char_("a-zA-Z") with x3::alpha
Some (many) rules NEED to be lexemes. That's because you invoke the grammar in a skipper context (phrase_parse with x3::space). You identifier will silently eat whitespace, because you didn't make them lexemes. See Boost spirit skipper issues
Negative lookahead assertions don't expose attributes so ! char_('(') could (should?) be ! lit('(')
presence of semantic actions (by default) suppresses attribute propagation - so print_action() will cause attribute propagation to stop
Expectation points (operator>) by defintion cannot backtrack. That's what makes them expecation points.
use the List operator of composing with kleene-star: p >> *(',' >> p) -> p % ','
That extra kleene-star was bogus. Did you mean to make the argument list optional? That's -(expression % ',')
the chaining operator rules make it slightly cumbersome to get the ast right
Simplify
factor >> *((x3::char_('*') > factor) //
| (x3::char_('/') > factor));
To just factor >> *(x3::char_("*/") >> factor);
factor_def logically matches what expression would be?
A first review pass yields:
auto const xlreference_def =
x3::lexeme[+x3::alpha >> x3::uint_] >> !x3::char_('(');
auto const identifier_def =
x3::raw[x3::lexeme[x3::alpha >> *(x3::alpha | '_') >> !x3::digit]];
auto const xlfunction_def = identifier >> '(' >> -(expression % ',') >> ')';
auto const term_def = factor >> *(x3::char_("*/") >> factor);
auto const factor_def = xlfunction //
| '(' >> expression >> ')' //
| x3::double_ //
| xlreference;
auto const expression_def = term >> *(x3::char_("-+") >> term);
More observations:
(iterator_type const)str.end()?? Never use C-style casts. In fact, just use str.cend() or indeed str.end() if str is suitably const anyways.
phrase_parse - consider NOT making the skipper a caller's decision, since it logically is part of your grammar
many kinds of excel expressions are not parsed: A:A, $A4, B$4, all cell ranges; I think often R1C1 is also supported
So, leaning on a lot of experience, I'm going to Crystall Ball™ some AST®:
namespace client::ast {
using identifier = std::string;
//using identifier = boost::iterator_range<std::string::const_iterator>;
struct string_literal : std::string {
using std::string::string;
using std::string::operator=;
friend std::ostream& operator<<(std::ostream& os, string_literal const& sl) {
return os << std::quoted(sl) ;
}
};
struct xlreference {
std::string colname;
size_t rownum;
};
struct xlfunction; // fwd
struct binary_op; // fwd
using expression = boost::variant< //
double, //
string_literal, //
identifier, //
xlreference, //
boost::recursive_wrapper<xlfunction>, //
boost::recursive_wrapper<binary_op> //
>;
struct xlfunction{
identifier name;
std::vector<expression> args;
friend std::ostream& operator<<(std::ostream& os, xlfunction const& xlf)
{
os << xlf.name << "(";
char const* sep = "";
for (auto& arg : xlf.args)
os << std::exchange(sep, ", ") << arg;
return os;
}
};
struct binary_op {
struct chained_t {
char op;
expression e;
};
expression lhs;
std::vector<chained_t> chained;
friend std::ostream& operator<<(std::ostream& os, binary_op const& bop)
{
os << "(" << bop.lhs;
for (auto& rhs : bop.chained)
os << rhs.op << rhs.e;
return os << ")";
}
};
using program = expression;
using boost::fusion::operator<<;
} // namespace client::ast
Which we promptly adapt:
BOOST_FUSION_ADAPT_STRUCT(client::ast::xlfunction, name, args)
BOOST_FUSION_ADAPT_STRUCT(client::ast::xlreference, colname, rownum)
BOOST_FUSION_ADAPT_STRUCT(client::ast::binary_op, lhs, chained)
BOOST_FUSION_ADAPT_STRUCT(client::ast::binary_op::chained_t, op, e)
Next, let's declare suitable rules:
x3::rule<struct identifier_class, ast::identifier> const identifier{"identifier"};
x3::rule<struct xlreference, ast::xlreference> const xlreference{"xlreference"};
x3::rule<struct xlfunction_class, ast::xlfunction> const xlfunction{"xlfunction"};
x3::rule<struct factor_class, ast::expression> const factor{"factor"};
x3::rule<struct expression_class, ast::binary_op> const expression{"expression"};
x3::rule<struct term_class, ast::binary_op> const term{"term"};
Which need definitions:
auto const xlreference_def =
x3::lexeme[+x3::alpha >> x3::uint_] /*>> !x3::char_('(')*/;
Note how the look-ahead assertion (
!) doesn't actually change the parse result, as any cell reference isn't a valid identifier anyways, so the () would remain unparsed.
auto const identifier_def =
x3::raw[x3::lexeme[x3::alpha >> *(x3::alpha | '_') /*>> !x3::digit*/]];
Same here. Remaining input will be checked against with
x3::eoilater.
I threw in a string literal because any Excel clone would have one:
auto const string_literal =
x3::rule<struct _, ast::string_literal>{"string_literal"} //
= x3::lexeme['"' > *('\\' >> x3::char_ | ~x3::char_('"')) > '"'];
Note that this demonstrates that non-recursive, locally-defined rules don't need separate definitions.
Then come the expression rules
auto const factor_def = //
xlfunction //
| '(' >> expression >> ')' //
| x3::double_ //
| string_literal //
| xlreference //
| identifier //
;
I'd usually call this "simple expression" instead of factor.
auto const term_def = factor >> *(x3::char_("*/") >> factor);
auto const expression_def = term >> *(x3::char_("-+") >> term);
auto const xlfunction_def = identifier >> '(' >> -(expression % ',') >> ')';
Straight-forward mappings to the AST.
BOOST_SPIRIT_DEFINE(xlreference)
BOOST_SPIRIT_DEFINE(identifier)
BOOST_SPIRIT_DEFINE(xlfunction)
BOOST_SPIRIT_DEFINE(term)
BOOST_SPIRIT_DEFINE(factor)
BOOST_SPIRIT_DEFINE(expression)
'Nuff said. Now comes a bit of cargo cult - remnants of code both unshown and unused, which I'll mostly just accept and ignore here:
int main() {
std::vector<int> positions; // TODO
auto parser = x3::with<struct position_cache_tag /*TODO*/> //
(std::ref(positions)) //
[ //
x3::skip(x3::space)[ //
client::calculator_grammar::expression >> x3::eoi //
] //
];
DO NOTE though that
x3::eoimakes it so the rule doesn't match if end of input (modulo skipper) isn't reached.
Now, let's add some test cases!
struct {
std::string category;
std::vector<std::string> cases;
} test_table[] = {
{
"xlreference",
{"A1", "A1111", "AbCdZ9876543", "i9", "i0"},
},
{
"identifier",
{"i", "id", "id_entifier"},
},
{
"number",
{"123", "inf", "-inf", "NaN", ".99e34", "1e-8", "1.e-8", "+9"},
},
{
"binaries",
{ //
"3+4", "3*4", //
"3+4+5", "3*4*5", "3+4*5", "3*4+5", "3*4+5", //
"3+(4+5)", "3*(4*5)", "3+(4*5)", "3*(4+5)", "3*(4+5)", //
"(3+4)+5", "(3*4)*5", "(3+4)*5", "(3*4)+5", "(3*4)+5"},
},
{
"xlfunction",
{
"pi()",
"sin(4)",
R"--(IIF(A1, "Red", "Green"))--",
},
},
{
"invalid",
{
"A9()", // an xlreference may not be followed by ()
"", // you didn't specify
},
},
{
"other",
{
"A-9", // 1-letter identifier and binary operation
"1 + +9", // unary plus accepted in number rule
},
},
{
"question",
{
"myfunc(myparam1, myparam2)",
"A1",
"AA234",
"A1 + sin(A2+3)",
},
},
};
And run them:
for (auto& [cat, cases] : test_table) {
for (std::string const& str : cases) {
auto iter = begin(str), last(end(str));
std::cout << std::setw(12) << cat << ": ";
client::ast::program ast;
if (parse(iter, last, parser, ast)) {
std::cout << "parsed: " << ast;
} else {
std::cout << "failed: " << std::quoted(str);
}
if (iter == last) {
std::cout << "\n";
} else {
std::cout << " unparsed: "
<< std::quoted(std::string_view(iter, last)) << "\n";
}
}
}
//#define BOOST_SPIRIT_X3_DEBUG
#include <boost/fusion/adapted.hpp>
#include <boost/fusion/include/io.hpp>
#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/home/x3/support/ast/position_tagged.hpp>
#include <boost/spirit/home/x3/support/utility/annotate_on_success.hpp>
#include <iostream>
#include <iomanip>
#include <map>
namespace x3 = boost::spirit::x3;
namespace client::ast {
using identifier = std::string;
//using identifier = boost::iterator_range<std::string::const_iterator>;
struct string_literal : std::string {
using std::string::string;
using std::string::operator=;
friend std::ostream& operator<<(std::ostream& os, string_literal const& sl) {
return os << std::quoted(sl) ;
}
};
struct xlreference {
std::string colname;
size_t rownum;
};
struct xlfunction; // fwd
struct binary_op; // fwd
using expression = boost::variant< //
double, //
string_literal, //
identifier, //
xlreference, //
boost::recursive_wrapper<xlfunction>, //
boost::recursive_wrapper<binary_op> //
>;
struct xlfunction{
identifier name;
std::vector<expression> args;
friend std::ostream& operator<<(std::ostream& os, xlfunction const& xlf)
{
os << xlf.name << "(";
char const* sep = "";
for (auto& arg : xlf.args)
os << std::exchange(sep, ", ") << arg;
return os;
}
};
struct binary_op {
struct chained_t {
char op;
expression e;
};
expression lhs;
std::vector<chained_t> chained;
friend std::ostream& operator<<(std::ostream& os, binary_op const& bop)
{
os << "(" << bop.lhs;
for (auto& rhs : bop.chained)
os << rhs.op << rhs.e;
return os << ")";
}
};
using program = expression;
using boost::fusion::operator<<;
} // namespace client::ast
BOOST_FUSION_ADAPT_STRUCT(client::ast::xlfunction, name, args)
BOOST_FUSION_ADAPT_STRUCT(client::ast::xlreference, colname, rownum)
BOOST_FUSION_ADAPT_STRUCT(client::ast::binary_op, lhs, chained)
BOOST_FUSION_ADAPT_STRUCT(client::ast::binary_op::chained_t, op, e)
namespace client::calculator_grammar {
struct expression_class //: x3::annotate_on_success
{
// Our error handler
template <typename Iterator, typename Exception, typename Context>
x3::error_handler_result on_error(Iterator& q, Iterator const& last,
Exception const& x,
Context const& context)
{
std::cout //
<< "Error! Expecting: " << x.which() //
<< " here: \"" << std::string(x.where(), last) //
<< "\"" << std::endl;
return x3::error_handler_result::fail;
}
};
x3::rule<struct identifier_class, ast::identifier> const identifier{"identifier"};
x3::rule<struct xlreference, ast::xlreference> const xlreference{"xlreference"};
x3::rule<struct xlfunction_class, ast::xlfunction> const xlfunction{"xlfunction"};
x3::rule<struct factor_class, ast::expression> const factor{"factor"};
x3::rule<struct expression_class, ast::binary_op> const expression{"expression"};
x3::rule<struct term_class, ast::binary_op> const term{"term"};
auto const xlreference_def =
x3::lexeme[+x3::alpha >> x3::uint_] /*>> !x3::char_('(')*/;
auto const identifier_def =
x3::raw[x3::lexeme[x3::alpha >> *(x3::alpha | '_') /*>> !x3::digit*/]];
auto const string_literal =
x3::rule<struct _, ast::string_literal>{"string_literal"} //
= x3::lexeme['"' > *('\\' >> x3::char_ | ~x3::char_('"')) > '"'];
auto const factor_def = //
xlfunction //
| '(' >> expression >> ')' //
| x3::double_ //
| string_literal //
| xlreference //
| identifier //
;
auto const term_def = factor >> *(x3::char_("*/") >> factor);
auto const expression_def = term >> *(x3::char_("-+") >> term);
auto const xlfunction_def = identifier >> '(' >> -(expression % ',') >> ')';
BOOST_SPIRIT_DEFINE(xlreference)
BOOST_SPIRIT_DEFINE(identifier)
BOOST_SPIRIT_DEFINE(xlfunction)
BOOST_SPIRIT_DEFINE(term)
BOOST_SPIRIT_DEFINE(factor)
BOOST_SPIRIT_DEFINE(expression)
} // namespace client::calculator_grammar
int main() {
std::vector<int> positions; // TODO
auto parser = x3::with<struct position_cache_tag /*TODO*/> //
(std::ref(positions)) //
[ //
x3::skip(x3::space)[ //
client::calculator_grammar::expression >> x3::eoi //
] //
];
struct {
std::string category;
std::vector<std::string> cases;
} test_table[] = {
{
"xlreference",
{"A1", "A1111", "AbCdZ9876543", "i9", "i0"},
},
{
"identifier",
{"i", "id", "id_entifier"},
},
{
"number",
{"123", "inf", "-inf", "NaN", ".99e34", "1e-8", "1.e-8", "+9"},
},
{
"binaries",
{ //
"3+4", "3*4", //
"3+4+5", "3*4*5", "3+4*5", "3*4+5", "3*4+5", //
"3+(4+5)", "3*(4*5)", "3+(4*5)", "3*(4+5)", "3*(4+5)", //
"(3+4)+5", "(3*4)*5", "(3+4)*5", "(3*4)+5", "(3*4)+5"},
},
{
"xlfunction",
{
"pi()",
"sin(4)",
R"--(IIF(A1, "Red", "Green"))--",
},
},
{
"invalid",
{
"A9()", // an xlreference may not be followed by ()
"", // you didn't specify
},
},
{
"other",
{
"A-9", // 1-letter identifier and binary operation
"1 + +9", // unary plus accepted in number rule
},
},
{
"question",
{
"myfunc(myparam1, myparam2)",
"A1",
"AA234",
"A1 + sin(A2+3)",
},
},
};
for (auto& [cat, cases] : test_table) {
for (std::string const& str : cases) {
auto iter = begin(str), last(end(str));
std::cout << std::setw(12) << cat << ": ";
client::ast::program ast;
if (parse(iter, last, parser, ast)) {
std::cout << "parsed: " << ast;
} else {
std::cout << "failed: " << std::quoted(str);
}
if (iter == last) {
std::cout << "\n";
} else {
std::cout << " unparsed: "
<< std::quoted(std::string_view(iter, last)) << "\n";
}
}
}
}
Prints
xlreference: parsed: (((A 1)))
xlreference: parsed: (((A 1111)))
xlreference: parsed: (((AbCdZ 9876543)))
xlreference: parsed: (((i 9)))
xlreference: parsed: (((i 0)))
identifier: parsed: ((i))
identifier: parsed: ((id))
identifier: parsed: ((id_entifier))
number: parsed: ((123))
number: parsed: ((inf))
number: parsed: ((-inf))
number: parsed: ((nan))
number: parsed: ((9.9e+33))
number: parsed: ((1e-08))
number: parsed: ((1e-08))
number: parsed: ((9))
binaries: parsed: ((3)+(4))
binaries: parsed: ((3*4))
binaries: parsed: ((3)+(4)+(5))
binaries: parsed: ((3*4*5))
binaries: parsed: ((3)+(4*5))
binaries: parsed: ((3*4)+(5))
binaries: parsed: ((3*4)+(5))
binaries: parsed: ((3)+(((4)+(5))))
binaries: parsed: ((3*((4*5))))
binaries: parsed: ((3)+(((4*5))))
binaries: parsed: ((3*((4)+(5))))
binaries: parsed: ((3*((4)+(5))))
binaries: parsed: ((((3)+(4)))+(5))
binaries: parsed: ((((3*4))*5))
binaries: parsed: ((((3)+(4))*5))
binaries: parsed: ((((3*4)))+(5))
binaries: parsed: ((((3*4)))+(5))
xlfunction: parsed: ((pi())
xlfunction: parsed: ((sin(((4))))
xlfunction: parsed: ((IIF((((A 1))), (("Red")), (("Green"))))
invalid: failed: "A9()" unparsed: "A9()"
invalid: failed: ""
other: parsed: ((A)-(9))
other: parsed: ((1)+(9))
question: parsed: ((myfunc((((myparam 1))), (((myparam 2)))))
question: parsed: (((A 1)))
question: parsed: (((AA 234)))
question: parsed: (((A 1))+(sin((((A 2))+(3))))
The only two failed lines are as expected
Simply uncomment
#define BOOST_SPIRIT_X3_DEBUG
And be slammed with additional noise:
question: <expression>
<try>A1 + sin(A2+3)</try>
<term>
<try>A1 + sin(A2+3)</try>
<factor>
<try>A1 + sin(A2+3)</try>
<xlfunction>
<try>A1 + sin(A2+3)</try>
<identifier>
<try>A1 + sin(A2+3)</try>
<success>1 + sin(A2+3)</success>
<attributes>[A]</attributes>
</identifier>
<fail/>
</xlfunction>
<string_literal>
<try>A1 + sin(A2+3)</try>
<fail/>
</string_literal>
<xlreference>
<try>A1 + sin(A2+3)</try>
<success> + sin(A2+3)</success>
<attributes>[[A], 1]</attributes>
</xlreference>
<success> + sin(A2+3)</success>
<attributes>[[A], 1]</attributes>
</factor>
<success> + sin(A2+3)</success>
<attributes>[[[A], 1], []]</attributes>
</term>
<term>
<try> sin(A2+3)</try>
<factor>
<try> sin(A2+3)</try>
<xlfunction>
<try> sin(A2+3)</try>
<identifier>
<try> sin(A2+3)</try>
<success>(A2+3)</success>
<attributes>[s, i, n]</attributes>
</identifier>
<expression>
<try>A2+3)</try>
<term>
<try>A2+3)</try>
<factor>
<try>A2+3)</try>
<xlfunction>
<try>A2+3)</try>
<identifier>
<try>A2+3)</try>
<success>2+3)</success>
<attributes>[A]</attributes>
</identifier>
<fail/>
</xlfunction>
<string_literal>
<try>A2+3)</try>
<fail/>
</string_literal>
<xlreference>
<try>A2+3)</try>
<success>+3)</success>
<attributes>[[A], 2]</attributes>
</xlreference>
<success>+3)</success>
<attributes>[[A], 2]</attributes>
</factor>
<success>+3)</success>
<attributes>[[[A], 2], []]</attributes>
</term>
<term>
<try>3)</try>
<factor>
<try>3)</try>
<xlfunction>
<try>3)</try>
<identifier>
<try>3)</try>
<fail/>
</identifier>
<fail/>
</xlfunction>
<success>)</success>
<attributes>3</attributes>
</factor>
<success>)</success>
<attributes>[3, []]</attributes>
</term>
<success>)</success>
<attributes>[[[[A], 2], []], [[+, [3, []]]]]</attributes>
</expression>
<success></success>
<attributes>[[s, i, n], [[[[[A], 2], []], [[+, [3, []]]]]]]</attributes>
</xlfunction>
<success></success>
<attributes>[[s, i, n], [[[[[A], 2], []], [[+, [3, []]]]]]]</attributes>
</factor>
<success></success>
<attributes>[[[s, i, n], [[[[[A], 2], []], [[+, [3, []]]]]]], []]</attributes>
</term>
<success></success>
<attributes>[[[[A], 1], []], [[+, [[[s, i, n], [[[[[A], 2], []], [[+, [3, []]]]]]], []]]]]</attributes>
</expression>
parsed: (((A 1))+(sin((((A 2))+(3))))