4

I got a working parser for reading position descriptions for a board game (international draughts, official grammar):

#include <boost/spirit/home/x3.hpp>
#include <iostream>

namespace x3 = boost::spirit::x3;

auto const colon   = x3::lit(':');
auto const comma   = x3::lit(',');
auto const dash    = x3::lit('-');
auto const dot     = x3::lit('.');    
auto const king    = x3::char_('K');
auto const color   = x3::char_("BW");
auto const num_sq  = x3::int_;

auto const num_pc  = -king >> num_sq;               // Kxx means king on square xx, xx a man on that square
auto const num_rng = num_pc >> dash >> num_sq;      // xx-yy means range of squares xx through yy (inclusive)
auto const num_seq = (num_rng | num_pc) % comma;    // <--- attribute should be std::vector<boost::variant>
auto const ccn     = colon >> color >> -num_seq;
auto const num_not = x3::repeat(2)[ccn];            // need to specify both white and black pieces
auto const fen     = color >> num_not >> -dot;

Live On Coliru

Now I want to extract the values from the synthesized attributes, so I did the boilerplate dance around Boost.Fusion etc.,

namespace ast {

struct num_pc  { boost::optional<char> k; int sq; };
struct num_rng { boost::optional<char> k; int first, last; };
using rng_or_pc = boost::variant<num_rng, num_pc>;
struct num_seq { std::vector<rng_or_pc> sqrs; };
struct ccn     { char c; boost::optional<num_seq> seq; };
struct num_not { std::vector<ccn> n; };
struct fen     { char c; num_not n; };

}   // namespace ast

BOOST_FUSION_ADAPT_STRUCT(ast::num_pc,  (boost::optional<char>, k), (int, sq))
BOOST_FUSION_ADAPT_STRUCT(ast::num_rng, (boost::optional<char>, k), (int, first), (int, last))
BOOST_FUSION_ADAPT_STRUCT(ast::num_seq, (std::vector<ast::rng_or_pc>, sqrs))
BOOST_FUSION_ADAPT_STRUCT(ast::ccn,     (char, c), (boost::optional<ast::num_seq>, seq))
BOOST_FUSION_ADAPT_STRUCT(ast::num_not, (std::vector<ast::ccn>, n))
BOOST_FUSION_ADAPT_STRUCT(ast::fen,     (char, c), (ast::num_not, n))

x3::rule<class num_pc_class,  ast::num_pc > num_pc  = "num_pc";
x3::rule<class num_rng_class, ast::num_rng> num_rng = "num_rng";
x3::rule<class num_seq_class, ast::num_seq> num_seq = "num_seq";
x3::rule<class ccn_class,     ast::ccn    > ccn     = "ccn";
x3::rule<class num_not_class, ast::num_not> num_not = "num_not";
x3::rule<class fen_class,     ast::fen    > fen     = "fen";

auto const colon   = x3::lit(':');
auto const comma   = x3::lit(',');
auto const dash    = x3::lit('-');
auto const dot     = x3::lit('.');    
auto const king    = x3::char_('K');
auto const color   = x3::char_("BW");
auto const num_sq  = x3::int_;

auto const num_pc_def  = -king >> num_sq;
auto const num_rng_def = num_pc >> dash >> num_sq;
auto const num_seq_def = (num_rng | num_pc) % comma;
auto const ccn_def     = colon >> color >> -num_seq;
auto const num_not_def = x3::repeat(2)[ccn];
auto const fen_def     = color >> num_not >> -dot;

BOOST_SPIRIT_DEFINE(num_pc, num_rng, num_seq, ccn, num_not, fen)

Live On Coliru

However, I then get an error saying that

error: static_assert failed "Attribute does not have the expected size."

and a couple of pages down:

^ main.cpp:16:8: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'std::vector<boost::variant<ast::num_rng, ast::num_pc>, std::allocator<boost::variant<ast::num_rng, ast::num_pc> > >' to 'ast::num_seq' for 1st argument struct num_seq { std::vector<rng_or_pc> sqrs; };

^ main.cpp:16:8: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'std::vector<boost::variant<ast::num_rng, ast::num_pc>, std::allocator<boost::variant<ast::num_rng, ast::num_pc> > >' to 'const ast::num_seq' for 1st argument struct num_seq { std::vector<rng_or_pc> sqrs; };

Question: where is this error coming from, and how to resolve it? Apparently the synthesized attribute of my num_seq rule is not equal to std::vector<boost::variant>>. How can I correct this?

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
  • 2
    [This](http://coliru.stacked-crooked.com/a/0ed4e50273d9f2c3) seems to work. You had at least two problems. The first one (easy to understand) is that your `num_rng` rule's attribute is basically `tuple,int,int>` but its synthesized attribute is `tuple,int>,int>`. In the example I give a possible solution, another could be inlining `num_pc` into `num_rng`. The other I don't fully understand, but seems to be related to the interaction between optional and a single (container) element fusion sequence. Using `using num_seq = vector;` seems to solve it. – llonesmiz Jan 01 '16 at 22:38
  • thanks, I will study it more carefully, I had missed the `tuple,int>>` nesting – TemplateRex Jan 01 '16 at 22:59
  • @cv_and_he please consider posting these as answers instead ? – sehe Jan 01 '16 at 23:14
  • @cv_and_he do you agree that this is still evidence of broken single-element sequences? It appears that even though the non-nested single-element container sequence (`not_num`) is compiling it failed to assign the second item from the `repeat(2)` directive. I'm really out of my depth trying to debug this kind of philosophical design issue in the implementation :( – sehe Jan 01 '16 at 23:51
  • @sehe I really don't know, I feel it's more of a problem with the optional part, but removing the fusion sequence from the equation made it work... – llonesmiz Jan 02 '16 at 00:00
  • The optional doesn't cause it though. I've reported the issue repeatedly without optional being involved. @cv_and_he – sehe Jan 02 '16 at 00:01
  • @sehe In one of my intermediate attempts I removed the optional without changing the adapted struct, and that error also went away(or maybe it was buried under the new errors). – llonesmiz Jan 02 '16 at 00:05
  • @cv_and_he I would very much not be surprised if it compiled but didn't work correctly (as with the outer vector) – sehe Jan 02 '16 at 00:20
  • @sehe I didn't understand that part of your answer, [my program](http://coliru.stacked-crooked.com/a/486f5195f396ac90) gives the exact same results as yours. (Although obviously it's better to just use vector in that situation). – llonesmiz Jan 02 '16 at 00:24
  • @cv_and_he ah. That was a bug on my end: compare [bug](http://coliru.stacked-crooked.com/a/27ec5f72d026222d) with [fixed](http://coliru.stacked-crooked.com/a/f96520493149f71c). I'll remove the warning from my answer. – sehe Jan 02 '16 at 00:44

1 Answers1

4

I've spent some time trying to understand the grammar.

I strongly suggest readable identifiers. It's very hard to understand what's going on, while I have the strong impression it's actually a really simple grammar

I suggest a simplification version shown below.

  • Because your grammar doesn't use recursion there's no real need for the rule and tagged parser types.
  • Also use a namespace for the parser artefacts.
  • Consider encapsulation the use of a skipper instead of letting the caller decide (x3::skip[])
  • Add a few helpers to be able to print the AST for verification:

    template <typename T> std::ostream& operator<<(std::ostream& os, std::vector<T> const& v) {
        os << "{"; for (auto& el : v) os << el << " "; return os << "}";
    }
    std::ostream& operator<<(std::ostream& os, num_pc const& p)  { if (p.k) os << p.k; return os << p.sq; }
    std::ostream& operator<<(std::ostream& os, num_rng const& r) { return os << r.pc << "-" << r.last; }
    std::ostream& operator<<(std::ostream& os, ccn const& o)     { return os << o.c << " " << o.seq;                      } 
    std::ostream& operator<<(std::ostream& os, num_not const& nn) { return os << nn.n; }
    
  • I'd avoid wrapping the other vector unnecessarily too:

    using num_not = std::vector<ccn>;
    
  • Use the modern ADAPT macros (as you're using C++14 by definition):

    BOOST_FUSION_ADAPT_STRUCT(ast::num_pc,  k, sq)
    BOOST_FUSION_ADAPT_STRUCT(ast::num_rng, pc, last)
    BOOST_FUSION_ADAPT_STRUCT(ast::ccn,     c, seq)
    BOOST_FUSION_ADAPT_STRUCT(ast::fen,     c, n)
    
  • -

Live Demo

Live On Coliru

#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/as_vector.hpp>
#include <boost/fusion/include/io.hpp>
#include <boost/optional/optional_io.hpp>
#include <boost/optional.hpp>
#include <boost/spirit/home/x3.hpp>
#include <boost/variant.hpp>
#include <iostream>
#include <vector>

namespace ast {

    struct num_pc {
        boost::optional<char> k;
        int sq;
    };

    struct num_rng {
        num_pc pc;
        int last;
    };

    using rng_or_pc = boost::variant<num_rng, num_pc>;
    using num_seq = std::vector<rng_or_pc>;

    struct ccn {
        char c;
        boost::optional<num_seq> seq;
    };

    using num_not = std::vector<ccn>;

    struct fen {
        char c;
        num_not n;
    };

    template <typename T> std::ostream& operator<<(std::ostream& os, std::vector<T> const& v) {
        os << "{"; for (auto& el : v) os << el << " "; return os << "}";
    }
    std::ostream& operator<<(std::ostream& os, num_pc const& p)  { if (p.k) os << p.k; return os << p.sq; }
    std::ostream& operator<<(std::ostream& os, num_rng const& r) { return os << r.pc << "-" << r.last; }
    std::ostream& operator<<(std::ostream& os, ccn const& o)     { return os << o.c << " " << o.seq;                      } 
}

BOOST_FUSION_ADAPT_STRUCT(ast::num_pc,  k, sq)
BOOST_FUSION_ADAPT_STRUCT(ast::num_rng, pc, last)
BOOST_FUSION_ADAPT_STRUCT(ast::ccn,     c, seq)
BOOST_FUSION_ADAPT_STRUCT(ast::fen,     c, n)

namespace FEN {
    namespace x3 = boost::spirit::x3;

    namespace grammar
    {
        using namespace x3;

        template<typename T>
            auto as = [](auto p) { return rule<struct _, T>{} = as_parser(p); };

        uint_type const number {};
        auto const color   = char_("BW");
        auto const num_pc  = as<ast::num_pc>  ( -char_('K') >> number          ); 
        auto const num_rng = as<ast::num_rng> ( num_pc >> '-' >> number        ); 
        auto const num_seq = as<ast::num_seq> ( (num_rng | num_pc) % ','       ); 
        auto const ccn     = as<ast::ccn>     ( ':' >> color >> -num_seq       ); 
        auto const num_not = as<ast::num_not> ( repeat(2)[ccn]                 ); 
        auto const fen     = as<ast::fen>     ( color >> num_not >> -lit('.')  ); 
    }

    using grammar::fen;
}

int main() {
    for (std::string const t : {
        "B:W18,24,27,28,K10,K15:B12,16,20,K22,K25,K29",
        "B:W18,19,21,23,24,26,29,30,31,32:B1,2,3,4,6,7,9,10,11,12",
        "W:B1-20:W31-50",   // initial position
        "W:B:W",            // empty board
        "W:B1:W",           // only black pieces
        "W:B:W50"           // only white pieces
    }) {
        auto b = t.begin(), e = t.end();
        ast::fen data;
        bool ok = phrase_parse(b, e, FEN::fen, FEN::x3::space, data);

        std::cout << t << "\n";
        if (ok) {
            std::cout << "Parsed: " << boost::fusion::as_vector(data) << "\n";
        } else {
            std::cout << "Parse failed:\n";
            std::cout << "\t on input: " << t << "\n";
        }
        if (b != e)
            std::cout << "\t Remaining unparsed: '" << std::string(b, e) << '\n';
    }
}

Prints:

B:W18,24,27,28,K10,K15:B12,16,20,K22,K25,K29
Parsed: (B {W  {18 24 27 28  K10  K15 } B  {12 16 20  K22  K25  K29 } })
B:W18,19,21,23,24,26,29,30,31,32:B1,2,3,4,6,7,9,10,11,12
Parsed: (B {W  {18 19 21 23 24 26 29 30 31 32 } B  {1 2 3 4 6 7 9 10 11 12 } })
W:B1-20:W31-50
Parsed: (W {B  {1-20 } W  {31-50 } })
W:B:W
Parsed: (W {B -- W -- })
W:B1:W
Parsed: (W {B  {1 } W -- })
W:B:W50
Parsed: (W {B -- W  {50 } })
sehe
  • 374,641
  • 47
  • 450
  • 633
  • thanks a bunch! re: the cryptic notation, yes, I'm guilty, sorry about that. The fen parser essentially enumerate the contents of the board, with B/W modifiers for black / white pieces, and the K modifier for kings (absence = pawn). I used the cryptic "num_" prefix because the full grammar (not shown for brevity) also allows for algebraic notation (as in chess) instead of numbers for squares. – TemplateRex Jan 01 '16 at 23:56
  • Ah. I _was_ wondering about the prefix (how about a namespace, maybe, or just longer names :)) – sehe Jan 01 '16 at 23:57
  • yeah, normally I would do proper naming, but this was a scratch version, fully done online, I had no idea I would actually almost get to the point of doing the attribute extraction on my first try with Boost.Spirit. – TemplateRex Jan 01 '16 at 23:59
  • You got that because you defined the ast. As long as your ast is compatible, you're good (personally, I feel you likely want a slightly higherlevel AST, though, because all the optionals are likely slightly awkward to deal with) – sehe Jan 02 '16 at 00:00
  • so std::vector and boost::variant/optional are automatically adapted by Boost.Fusion? That's nice, so that I only need to adapt the hand-written structs, and the c++14 auto makes it even nicer. – TemplateRex Jan 02 '16 at 00:02
  • 1
    These are intrinsic to Spirit's attribute propagation - fusion is not involved. – sehe Jan 02 '16 at 00:02
  • @TemplateRex [My attempt](http://coliru.stacked-crooked.com/a/b65de362b25fa4f1) at the grammar. I haven't used optionals in the ast structures, and so when they aren't present, they are default initialized. You can easily add the optionals if you like. – llonesmiz Jan 02 '16 at 00:03
  • @sehe: I also see that you (correctly) use unsigned integers for the squares, but what's the difference between `uint_type const number {};` and `auto const number = uint_;`? – TemplateRex Jan 02 '16 at 00:12
  • 2
    @TemplateRex `uint_` is defined as `uint_type const uint_ = {};`. So I'd say that both are the same. – llonesmiz Jan 02 '16 at 00:20
  • btw, I tend to use `lit()` everywhere in order to forget about mixing in other operators than `>>` – TemplateRex Jan 02 '16 at 00:24
  • @TemplateRex better yet, in x3 start into the habit of using `as_parser` for that purpose – sehe Jan 02 '16 at 00:29
  • @sehe [see here](http://coliru.stacked-crooked.com/a/ac09c864d2628a73) for a cleaned up version (separate namespaces for algebraic/notation, better naming etc.). Everything parses nicely, but the overloading of the IO operators is not going well (deep errors from boost/optional_io.hpp), [see here](http://coliru.stacked-crooked.com/a/7257f0b1465a4d98). Any ideas? Or should I post a new Q&A? – TemplateRex Jan 02 '16 at 10:48