Need an extended example for your typical math expression like grammar #141
Comments
|
I really don't like these kinds of examples; I've never needed to implement a calculator. But, I suppose it would be useful to do part of this, to show how precedence can be encoded into your parsers. I may do this, but no prommises. |
|
Something that shows how to impleent operator precedence would be good enough. I have to parse a DSL that contains arbitrary math on complex numbers, so... |
|
Gotcha, that makes sense. I'll try to put something together pretty soon. |
|
I ported some weeks ago as an exercise the spirit::x3 example calc2.cpp augmented with building the AST and it's evaluation. It's still using integers as input (though returning double) but it's good enough for operator precedence on pocket calculator operations, i.e. Martin |
The grammar can be simplified when one realizes that the only recursion is on the /*=============================================================================
Copyright (c) 2001-2014 Joel de Guzman
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
///////////////////////////////////////////////////////////////////////////////
//
// A Calculator example demonstrating the grammar and semantic actions
// using lambda functions. The parser prints code suitable for a stack
// based virtual machine, the semantic actions create the AST and
// the evaluation is performed by a recursive visitor. The 'recursive' variant
// decoupling is done with the help of std::optional<>
//
// [ JDG May 10, 2002 ] spirit 1
// [ JDG March 4, 2007 ] spirit 2
// [ JDG February 21, 2011 ] spirit 2.5
// [ JDG June 6, 2014 ] spirit x3 (from qi calc2, but using lambda functions)
// [ MPo Oct 27, 2022 ] boost::parser (from spirit x3)
// [ MPo Apr 20, 2024 ] AST, visitor
//
///////////////////////////////////////////////////////////////////////////////
#include <boost/parser/parser.hpp>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <limits>
namespace bp = boost::parser;
template<typename TVisitor, typename TVariant>
decltype(auto) visit_node_recursively(TVisitor && visitor, TVariant && variant)
{
return std::visit(
std::forward<TVisitor>(visitor), std::forward<TVariant>(variant));
}
namespace impl {
enum class ub_operator { uminus, add, subtract, multiply, divide };
struct node;
using onode = std::optional<node>;
using vnode = std::variant<unsigned int, int, float, double, onode>;
using node_array = std::vector<vnode>;
struct node
{
ub_operator op;
node_array nodes;
node(const ub_operator op, vnode const & arg1) : op(op), nodes{arg1} {}
node(const ub_operator op, vnode const & arg1, vnode const & arg2) :
op(op), nodes{arg1, arg2}
{}
};
}
using impl::ub_operator;
using impl::vnode;
using impl::onode;
struct node_visitor
{
double operator()(unsigned int x) const { return (double)x; }
double operator()(int x) const { return (double)x; }
double operator()(float x) const { return (double)x; }
double operator()(double x) const { return x; }
double operator()(onode const & pn)
{
auto & node = *pn;
switch (node.op) {
case ub_operator::uminus:
assert(node.nodes.size() == 1);
return -visit_node_recursively(*this, node.nodes[0]);
case ub_operator::add:
assert(node.nodes.size() == 2);
return visit_node_recursively(*this, node.nodes[0]) +
visit_node_recursively(*this, node.nodes[1]);
case ub_operator::subtract:
assert(node.nodes.size() == 2);
return visit_node_recursively(*this, node.nodes[0]) -
visit_node_recursively(*this, node.nodes[1]);
case ub_operator::multiply:
assert(node.nodes.size() == 2);
return visit_node_recursively(*this, node.nodes[0]) *
visit_node_recursively(*this, node.nodes[1]);
case ub_operator::divide:
assert(node.nodes.size() == 2);
return visit_node_recursively(*this, node.nodes[0]) /
visit_node_recursively(*this, node.nodes[1]);
default:
return std::numeric_limits<double>::quiet_NaN();
}
}
};
namespace client {
///////////////////////////////////////////////////////////////////////////////
// Semantic actions
////////////////////////////////////////////////////////1///////////////////////
namespace {
std::deque<vnode> vn_stack;
auto do_int = [](auto & ctx) {
std::cout << "push " << bp::_attr(ctx) << std::endl;
vnode i = _attr(ctx);
vn_stack.push_front(i); // ast
};
auto const do_add = [](auto & ctx) {
std::cout << "add" << std::endl;
// stack effect notation ( a, b -- c ) where c = a + b
{ // ast
assert(vn_stack.size() > 1);
auto && second = vn_stack[0];
auto && first = vn_stack[1];
auto result = std::optional(impl::node(ub_operator::add, first, second));
vn_stack[1] = result;
vn_stack.pop_front();
}
};
auto const do_subt = [](auto & ctx) {
std::cout << "subtract" << std::endl;
// stack effect notation ( a, b -- c ) where c = a - b
{ // ast
assert(vn_stack.size() > 1);
auto && second = vn_stack[0];
auto && first = vn_stack[1];
auto result = std::optional(impl::node(ub_operator::subtract, first, second));
vn_stack[1] = result;
vn_stack.pop_front();
}
};
auto const do_mult = [](auto & ctx) {
std::cout << "mult" << std::endl;
// stack effect notation ( a, b -- c ) where c = a * b
{ // ast
assert(vn_stack.size() > 1);
auto && second = vn_stack[0];
auto && first = vn_stack[1];
auto result = std::optional(impl::node(ub_operator::multiply, first, second));
vn_stack[1] = result;
vn_stack.pop_front();
}
};
auto const do_div = [](auto & ctx) {
std::cout << "divide" << std::endl;
// stack effect notation ( a, b -- c ) where c = a / b
{ // ast
assert(vn_stack.size() > 1);
auto && second = vn_stack[0];
auto && first = vn_stack[1];
auto result = std::optional(impl::node(ub_operator::divide, first, second));
vn_stack[1] = result;
vn_stack.pop_front();
}
};
auto const do_neg = [](auto & ctx) {
std::cout << "negate" << std::endl;
// stack effect notation ( a -- -a )
{ // ast
assert(vn_stack.size() > 0);
auto && arg = vn_stack[0];
auto result = std::optional(impl::node(ub_operator::uminus, arg));
vn_stack[0] = result;
}
};
}
///////////////////////////////////////////////////////////////////////////////
// The calculator grammar
///////////////////////////////////////////////////////////////////////////////
namespace calculator_grammar {
bp::rule<class expression> const expression("expression");
auto const uint = bp::uint_[do_int];
auto const factor = uint | '(' >> expression >> ')' |
('-' >> uint[do_neg]) | ('+' >> uint);
auto const term = factor >> *(('*' >> factor[do_mult]) |
('/' >> factor[do_div]));
auto const expression_def = term >> *(('+' >> term[do_add]) |
('-' >> term[do_subt]));
BOOST_PARSER_DEFINE_RULES(expression);
auto calculator = expression;
}
using calculator_grammar::calculator;
}
///////////////////////////////////////////////////////////////////////////////
// Main program
///////////////////////////////////////////////////////////////////////////////
int main()
{
//test_recursive_node_visitor();
std::cout << "/////////////////////////////////////////////////////////"
<< std::endl << std::endl;
std::cout << "Expression parser..." << std::endl << std::endl;
std::cout << "/////////////////////////////////////////////////////////"
<< std::endl << std::endl;
std::string inputs[]=
{ "999"
, "-888"
, "1+2"
, "2*3"
, "2+(3*4)"
};
for(std::string str:inputs) {
auto & calc = client::calculator; // Our grammar
auto r = bp::parse(str, calc, bp::ws);
if (r) {
std::cout << "-------------------------" << std::endl;
std::cout << "Parsing succeeded" << std::endl;
assert(client::vn_stack.size() == 1);
std::cout << str << " ==> "
<< std::visit(node_visitor(), client::vn_stack[0])
<< " (AST eval)"
<< std::endl;
client::vn_stack.pop_front();
std::cout << "-------------------------" << std::endl;
} else {
typedef std::string::const_iterator iterator_type;
iterator_type iter = str.begin();
iterator_type end = str.end();
std::cout << "-------------------------" << std::endl;
std::cout << "Parsing failed" << std::endl;
bp::prefix_parse(iter, end, calc, bp::ws);
std::string rest(iter, end);
std::cout << "stopped at: \"" << rest << "\"" << std::endl;
client::vn_stack.clear();
std::cout << "-------------------------" << std::endl;
}
}
std::cout << "Bye... :-)" << std::endl << std::endl;
return 0;
}which produces the expected output: |
|
Thank you @cppljevans and @d5ch4k these examples are very helpful. |
@cppljevans Why did you put parentheses around |
Very simple reason. It was an oversight. Thanks for catching it. Here's corrected code (with slight change in uint parser): /*=============================================================================
Copyright (c) 2001-2014 Joel de Guzman
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
///////////////////////////////////////////////////////////////////////////////
//
// A Calculator example demonstrating the grammar and semantic actions
// using lambda functions. The parser prints code suitable for a stack
// based virtual machine, the semantic actions create the AST and
// the evaluation is performed by a recursive visitor. The 'recursive' variant
// decoupling is done with the help of std::optional<>
//
// [ JDG May 10, 2002 ] spirit 1
// [ JDG March 4, 2007 ] spirit 2
// [ JDG February 21, 2011 ] spirit 2.5
// [ JDG June 6, 2014 ] spirit x3 (from qi calc2, but using lambda functions)
// [ MPo Oct 27, 2022 ] boost::parser (from spirit x3)
// [ MPo Apr 20, 2024 ] AST, visitor
//
///////////////////////////////////////////////////////////////////////////////
#include <boost/parser/parser.hpp>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <limits>
namespace bp = boost::parser;
template<typename TVisitor, typename TVariant>
decltype(auto) visit_node_recursively(TVisitor && visitor, TVariant && variant)
{
return std::visit(
std::forward<TVisitor>(visitor), std::forward<TVariant>(variant));
}
namespace impl {
enum class ub_operator { uminus, add, subtract, multiply, divide };
struct node;
using onode = std::optional<node>;
using vnode = std::variant<unsigned int, int, float, double, onode>;
using node_array = std::vector<vnode>;
struct node
{
ub_operator op;
node_array nodes;
node(const ub_operator op, vnode const & arg1) : op(op), nodes{arg1} {}
node(const ub_operator op, vnode const & arg1, vnode const & arg2) :
op(op), nodes{arg1, arg2}
{}
};
}
using impl::ub_operator;
using impl::vnode;
using impl::onode;
struct node_visitor
{
double operator()(unsigned int x) const { return (double)x; }
double operator()(int x) const { return (double)x; }
double operator()(float x) const { return (double)x; }
double operator()(double x) const { return x; }
double operator()(onode const & pn)
{
auto & node = *pn;
switch (node.op) {
case ub_operator::uminus:
assert(node.nodes.size() == 1);
return -visit_node_recursively(*this, node.nodes[0]);
case ub_operator::add:
assert(node.nodes.size() == 2);
return visit_node_recursively(*this, node.nodes[0]) +
visit_node_recursively(*this, node.nodes[1]);
case ub_operator::subtract:
assert(node.nodes.size() == 2);
return visit_node_recursively(*this, node.nodes[0]) -
visit_node_recursively(*this, node.nodes[1]);
case ub_operator::multiply:
assert(node.nodes.size() == 2);
return visit_node_recursively(*this, node.nodes[0]) *
visit_node_recursively(*this, node.nodes[1]);
case ub_operator::divide:
assert(node.nodes.size() == 2);
return visit_node_recursively(*this, node.nodes[0]) /
visit_node_recursively(*this, node.nodes[1]);
default:
return std::numeric_limits<double>::quiet_NaN();
}
}
};
namespace client {
///////////////////////////////////////////////////////////////////////////////
// Semantic actions
////////////////////////////////////////////////////////1///////////////////////
namespace {
std::deque<vnode> vn_stack;
auto do_int = [](auto & ctx) {
std::cout << "push " << bp::_attr(ctx) << std::endl;
vnode i = _attr(ctx);
vn_stack.push_front(i); // ast
};
auto const do_add = [](auto & ctx) {
std::cout << "add" << std::endl;
// stack effect notation ( a, b -- c ) where c = a + b
{ // ast
assert(vn_stack.size() > 1);
auto && second = vn_stack[0];
auto && first = vn_stack[1];
auto result = std::optional(impl::node(ub_operator::add, first, second));
vn_stack[1] = result;
vn_stack.pop_front();
}
};
auto const do_subt = [](auto & ctx) {
std::cout << "subtract" << std::endl;
// stack effect notation ( a, b -- c ) where c = a - b
{ // ast
assert(vn_stack.size() > 1);
auto && second = vn_stack[0];
auto && first = vn_stack[1];
auto result = std::optional(impl::node(ub_operator::subtract, first, second));
vn_stack[1] = result;
vn_stack.pop_front();
}
};
auto const do_mult = [](auto & ctx) {
std::cout << "mult" << std::endl;
// stack effect notation ( a, b -- c ) where c = a * b
{ // ast
assert(vn_stack.size() > 1);
auto && second = vn_stack[0];
auto && first = vn_stack[1];
auto result = std::optional(impl::node(ub_operator::multiply, first, second));
vn_stack[1] = result;
vn_stack.pop_front();
}
};
auto const do_div = [](auto & ctx) {
std::cout << "divide" << std::endl;
// stack effect notation ( a, b -- c ) where c = a / b
{ // ast
assert(vn_stack.size() > 1);
auto && second = vn_stack[0];
auto && first = vn_stack[1];
auto result = std::optional(impl::node(ub_operator::divide, first, second));
vn_stack[1] = result;
vn_stack.pop_front();
}
};
auto const do_neg = [](auto & ctx) {
std::cout << "negate" << std::endl;
// stack effect notation ( a -- -a )
{ // ast
assert(vn_stack.size() > 0);
auto && arg = vn_stack[0];
auto result = std::optional(impl::node(ub_operator::uminus, arg));
vn_stack[0] = result;
}
};
}
///////////////////////////////////////////////////////////////////////////////
// The calculator grammar
///////////////////////////////////////////////////////////////////////////////
namespace calculator_grammar {
bp::rule<class expression> const expression("expression");
auto const uint = bp::uint_[do_int] | '(' >> expression >> ')';
auto const factor = uint | ('-' >> uint[do_neg]) | ('+' >> uint);
auto const term = factor >> *(('*' >> factor[do_mult]) |
('/' >> factor[do_div]));
auto const expression_def = term >> *(('+' >> term[do_add]) |
('-' >> term[do_subt]));
BOOST_PARSER_DEFINE_RULES(expression);
auto calculator = expression;
}
using calculator_grammar::calculator;
}
///////////////////////////////////////////////////////////////////////////////
// Main program
///////////////////////////////////////////////////////////////////////////////
int main()
{
//test_recursive_node_visitor();
std::cout << "/////////////////////////////////////////////////////////"
<< std::endl << std::endl;
std::cout << "Expression parser..." << std::endl << std::endl;
std::cout << "/////////////////////////////////////////////////////////"
<< std::endl << std::endl;
std::string inputs[]=
{ "999"
, "-888"
, "1+2"
, "2*3"
, "2*(3+4)"
, "2*-(3+4)"
};
for(std::string str:inputs) {
auto & calc = client::calculator; // Our grammar
auto r = bp::parse(str, calc, bp::ws);
if (r) {
std::cout << "-------------------------" << std::endl;
std::cout << "Parsing succeeded" << std::endl;
assert(client::vn_stack.size() == 1);
std::cout << str << " ==> "
<< std::visit(node_visitor(), client::vn_stack[0])
<< " (AST eval)"
<< std::endl;
client::vn_stack.pop_front();
std::cout << "-------------------------" << std::endl;
} else {
typedef std::string::const_iterator iterator_type;
iterator_type iter = str.begin();
iterator_type end = str.end();
std::cout << "-------------------------" << std::endl;
std::cout << "Parsing failed" << std::endl;
bp::prefix_parse(iter, end, calc, bp::ws);
std::string rest(iter, end);
std::cout << "stopped at: \"" << rest << "\"" << std::endl;
client::vn_stack.clear();
std::cout << "-------------------------" << std::endl;
}
}
std::cout << "Bye... :-)" << std::endl << std::endl;
return 0;
}
|
|
@LegalizeAdulthood, there's no need for the added complexity of vn_stack as demonstrated by: /*=============================================================================
Copyright (c) 2001-2014 Joel de Guzman
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
///////////////////////////////////////////////////////////////////////////////
//
// A Calculator example demonstrating the grammar and semantic actions
// using lambda functions. The parser prints code suitable for a stack
// based virtual machine, the semantic actions create the AST and
// the evaluation is performed by a recursive visitor. The 'recursive' variant
// decoupling is done with the help of std::optional<>
//
// [ JDG May 10, 2002 ] spirit 1
// [ JDG March 4, 2007 ] spirit 2
// [ JDG February 21, 2011 ] spirit 2.5
// [ JDG June 6, 2014 ] spirit x3 (from qi calc2, but using lambda functions)
// [ MPo Oct 27, 2022 ] boost::parser (from spirit x3)
// [ MPo Apr 20, 2024 ] AST, visitor
//
///////////////////////////////////////////////////////////////////////////////
#include <boost/parser/parser.hpp>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <limits>
namespace bp = boost::parser;
namespace client
{
using val_t=int;
///////////////////////////////////////////////////////////////////////////////
// Semantic actions
////////////////////////////////////////////////////////1///////////////////////
namespace
{
auto do_int = [](auto & ctx) {
val_t v = _attr(ctx);
std::cout << "do_int(before):_attr=" << bp::_attr(ctx) <<":_val="<<bp::_val(ctx)<< std::endl;
bp::_val(ctx) = v;
std::cout << "do_int(after):_val="<<bp::_val(ctx)<< std::endl;
};
auto const do_add = [](auto & ctx) {
std::cout << "do_add(before):_attr=" << bp::_attr(ctx) <<":_val="<<bp::_val(ctx)<< std::endl;
bp::_val(ctx) += bp::_attr(ctx);
std::cout << "do_add(after):_val="<<bp::_val(ctx)<< std::endl;
};
auto const do_subt = [](auto & ctx) {
std::cout << "do_subt(before):_attr=" << bp::_attr(ctx) <<":_val="<<bp::_val(ctx)<< std::endl;
bp::_val(ctx) -= bp::_attr(ctx);
std::cout << "do_subt(after):_val="<<bp::_val(ctx)<< std::endl;
};
auto const do_mult = [](auto & ctx) {
std::cout << "do_mult(before):_attr=" << bp::_attr(ctx) <<":_val="<<bp::_val(ctx)<< std::endl;
bp::_val(ctx) *= bp::_attr(ctx);
std::cout << "do_mult(after):_val="<<bp::_val(ctx)<< std::endl;
};
auto const do_div = [](auto & ctx) {
std::cout << "do_div(before):_attr=" << bp::_attr(ctx) <<":_val="<<bp::_val(ctx)<< std::endl;
bp::_val(ctx) /= bp::_attr(ctx);
std::cout << "do_div(after):_val="<<bp::_val(ctx)<< std::endl;
};
auto const do_neg = [](auto & ctx) {
std::cout << "do_neg(before):_attr=" << bp::_attr(ctx) <<":_val="<<bp::_val(ctx)<< std::endl;
bp::_val(ctx) = -bp::_attr(ctx);
std::cout << "do_neg(after):_val="<<bp::_val(ctx)<< std::endl;
};
}//anonymous
///////////////////////////////////////////////////////////////////////////////
// The calculator grammar
///////////////////////////////////////////////////////////////////////////////
namespace calculator_grammar
{
using client::val_t
;
template<typename Tag>
using calc_rule=
bp::rule<Tag,val_t>
;
calc_rule<class expression_tag> const expression("expression");
calc_rule<class fac_uns_tag> const fac_uns("fac_uns");
auto const fac_uns_def
= bp::uint_[do_int]
| ('(' >> expression >> ')')[do_int]
;
calc_rule<class factor_tag> const factor("factor");
auto const factor_def
= fac_uns[do_int]
| ('-' >> fac_uns[do_neg])
| ('+' >> fac_uns[do_int ])
;
calc_rule<class term_tag> const term("term");
auto const term_def
= factor[do_int]
>> *( ('*' >> factor[do_mult])
| ('/' >> factor[do_div ])
)
;
auto const expression_def
= term[do_int]
>> *( ('+' >> term[do_add])
| ('-' >> term[do_subt])
)
;
BOOST_PARSER_DEFINE_RULES(expression,fac_uns,factor,term);
auto calculator = expression;
}//calculator_grammar
using calculator_grammar::calculator;
}//client
///////////////////////////////////////////////////////////////////////////////
// Main program
///////////////////////////////////////////////////////////////////////////////
int main()
{
//test_recursive_node_visitor();
std::cout << "/////////////////////////////////////////////////////////"
<< std::endl << std::endl;
std::cout << "Expression parser..." << std::endl << std::endl;
std::cout << "/////////////////////////////////////////////////////////"
<< std::endl << std::endl;
std::string inputs[]=
{ "999"
, "-888"
, "1+2"
, "2*3"
, "2*(3+4)"
, "2*-(3+4)"
};
for(std::string str:inputs) {
auto & calc = client::calculator; // Our grammar
client::val_t val{0};
auto r =
bp::parse
( str
, calc
, bp::ws
, val
//, bp::trace::on
);
if (r) {
std::cout << "-------------------------" << std::endl;
std::cout << "Parsing succeeded" << std::endl;
std::cout << "val = "<<val << std::endl;
std::cout << "-------------------------" << std::endl;
} else {
typedef std::string::const_iterator iterator_type;
iterator_type iter = str.begin();
iterator_type end = str.end();
std::cout << "-------------------------" << std::endl;
std::cout << "Parsing failed" << std::endl;
bp::prefix_parse(iter, end, calc, bp::ws);
std::string rest(iter, end);
std::cout << "stopped at: \"" << rest << "\"" << std::endl;
std::cout << "-------------------------" << std::endl;
}
}
std::cout << "Bye... :-)" << std::endl << std::endl;
return 0;
}which produces expected output: |
|
@cppljevans wrote:
...but now it has Basically, if you have to supply parentheses to enforce precedence, then you're not implementing precedence in the grammar, which is the original request. I haven't had time to take your code and put it down somewhere and use it with the library. |
Slightly revised code with requested test with expected output: To see details, uncomment the |
|
Thanks for the updated version! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Lots of times when people get down into the nitty gritty of using a parsing framework, it's because their ad-hoc attempts at using a regex or whatever for a complicated grammar becomes unwieldy. One of the most common needs for using a parsing framework is when you need to parse arithmetic expressions with operator precedence similar to C/C++.
An elaborated example that demonstrated parsing expression using all the typical operators:
+,-(unary and binary)/,*&,|,^,~,<<,>>==,!=,<,<=,>,>=The text was updated successfully, but these errors were encountered: