如何使用具有强制性最小元素数量的boost spirit list运算符？

Question

我想解析点语言 (http://www.graphviz.org/content/dot-language)。它是一种图形定义语言，用于定义节点和它们之间的连接。一个典型的语句看起来像 node1->node2->node3;。最好使用 boost::spirit 列表运算符 % 来制作节点列表。一个天真的方法是：

edge_stmt %=
    (
        node_or_subgraph(_r1) % (qi::eps(_r1) >> tok.diredgeop | tok.undiredgeop)
    ) >> -attr_list;

_r1表示这是有向图还是无向图，diredgeop是->的token，undiredgeop分别是--的token。

问题是上面的代码只对 node1; 会成功，这是不正确的。为了获得正确的解析器，我必须以某种方式声明 % 构建的列表中必须至少有两个元素。怎么样？

文档说 a % b 等同于 a >> *(omit[b] >> a)，这是不正确的。有人可能想试试这个：

edge_stmt %=
    (
        node_or_subgraph(_r1) >>
            +(
                qi::omit
                [
                    qi::eps(_r1) >> tok.diredgeop | tok.undiredgeop
                ] >>
                node_or_subgraph(_r1)
            )
    ) >> -attr_list;

但是这段代码并没有产生向量，它的合成属性是一个元组。

我当然可以尝试语义操作，但是有没有没有语义操作的优雅替代方案？

Answer 1

要使列表运算符接受最小数量的元素，需要创建一个引入该行为的全新解析器，因为与 repeat 不同，它未配置为这样做。我希望下面的例子可以帮助您了解如何使用 a >> +(omit[b] >> a) 来实现您想要的。

Running on WandBox

#include <iostream>
#include <vector>
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/include/std_pair.hpp>

namespace qi= boost::spirit::qi;

void print(const std::vector<std::string>& data) 
{
    std::cout << "{ ";
    for(const auto& elem : data) {
        std::cout << elem << " ";
    }
    std::cout << "} ";
}

void print(const std::pair<std::string,double>& data) 
{
    std::cout << "[ " << data.first << ", " << data.second << " ]";
}


template <typename Parser,typename... Attrs>
void parse(const std::string& str, const Parser& parser, Attrs&... attrs)
{
    std::string::const_iterator iter=std::begin(str), end=std::end(str);
    bool result = qi::phrase_parse(iter,end,parser,qi::space,attrs...);
    if(result && iter==end) {
        std::cout << "Success.";
        int ignore[] = {(print(attrs),0)...};
        std::cout << "\n";
    } else {
        std::cout << "Something failed. Unparsed: \"" << std::string(iter,end) << "\"\n";
    }
}

template <typename Parser>
void parse_with_nodes(const std::string& str, const Parser& parser) 
{
    std::vector<std::string> nodes;
    parse(str,parser,nodes);
}

template <typename Parser>
void parse_with_nodes_and_attr(const std::string& str, const Parser& parser) 
{
    std::vector<std::string> nodes;
    std::pair<std::string,double> attr_pair;
    parse(str,parser,nodes,attr_pair);
}

int main()
{
    qi::rule<std::string::const_iterator,std::string()> node=+qi::alnum;
    qi::rule<std::string::const_iterator,std::pair<std::string,double>(),qi::space_type> attr = +qi::alpha >> '=' >> qi::double_;


    parse_with_nodes("node1->node2", node % "->");

    parse_with_nodes_and_attr("node1->node2 arrowsize=1.0", node % "->" >> attr);

    parse_with_nodes("node1->node2", node >> +("->" >> node));

    //parse_with_nodes_and_attr("node1->node2 arrowsize=1.0", node >> +("->" >> node) >> attr); 

    qi::rule<std::string::const_iterator,std::vector<std::string>(),qi::space_type> at_least_two_nodes = node >> +("->" >> node);
    parse_with_nodes_and_attr("node1->node2 arrowsize=1.0", at_least_two_nodes >> attr);
}

Answer 2

The problem is the above code will succeed for just node1;, which is incorrect.

你在逆流而上。在 DOT 中 node1; 就可以了。因此，安排语法来反映它可能更容易。

注意事项

Graphviz 的语法有很多特质，很难将语法树直接转换为有用的图形表示。

我认为这反映了这样一个事实，即他们自己的解析函数动态地构建了一个图，根本没有试图表示源语法树。

这是显而易见的，因为语义是有状态的，在全局状态、词法范围和子图命名空间之间有微妙的混合。图中出现的顺序很重要。节点总是共享一个 "global" 命名空间并且可以隐式声明这一事实是一个并不能真正简化事情的因素。

如何解决

虽然我通常不是语义动作的粉丝¹，但语义动作似乎是这里要使用的东西。您可以通过使用 "event" 响应每个已解析的规则来模仿 Graphviz 解析器的行为，该 "event" 可以由有状态 "builder" 处理，这会导致对域模型进行适当的更改。

但是，我尝试这样做，它变得非常复杂，主要是因为规则的合成类型不便于构建。

关注点分离 是消除此类瓶颈²的关键。

如果您首先解析为纯 AST，然后从中构建模型，那么解析器和语义逻辑都会得到极大的简化。

模型

我发明了以下 Model 表示，我认为它很好地捕捉了 GraphViz 领域模型的语义：

TODO（但请参阅评论中的更新）

AST

让我们创建一个 单独的 集类来表示源文档。注：

这紧跟http://www.graphviz.org/doc/info/lang.html
这是有意1:1以后我们的精神规则
它与模型共享基本类型（Id、NodeRef、CompassPoint），因为它们在输入中按字面意思表示

namespace Model {
    using Id = std::string;

    using Attributes = std::map<Id, std::string>;
    enum class GraphKind { directed, undirected };

    enum class CompassPoint { n, ne, e, se, s, sw, w, nw, c, _ };

    struct NodeRef {
        Id id;
        Id port;
        CompassPoint compass_pt = CompassPoint::_;
    };
}

namespace Ast {
    using Model::CompassPoint;
    using Model::Id;
    using Model::NodeRef;
    using Model::GraphKind;
    using OptionalId = boost::optional<Id>;

    using AList    = Model::Attributes;
    using AttrList = std::vector<AList>;

    struct AttrStmt {
        enum Group { graph, node, edge } group;
        AttrList attributes;
    };

    struct Attr {
        Id key, value;

        operator std::pair<Id, Id>() const { return {key, value}; }
    };

    struct NodeStmt {
        NodeRef node_id;
        AttrList attributes;
    };

    struct EdgeStmt;
    using Stmt = boost::variant<
            AttrStmt,
            Attr,
            NodeStmt,
            boost::recursive_wrapper<EdgeStmt> // includes sub graphs
        >;

    using StmtList = std::vector<Stmt>;

    struct Graph {
        OptionalId id;
        StmtList stmt_list;
    };

    struct EdgeStmt {
        std::vector<boost::variant<NodeRef, Graph> > hops;
        AttrList attributes;
    };

    struct GraphViz {
        bool strict;
        GraphKind kind;
        Graph graph;
    };
}

语法

语法完全遵循规范，并将 1:1 映射到 Ast，因此我们不必再做任何魔术（¹）。

namespace Parser {

    namespace qi = boost::spirit::qi;
    namespace px = boost::phoenix;

    template <typename It>
    struct GraphViz : qi::grammar<It, Ast::GraphViz()> {
        GraphViz() : GraphViz::base_type(start) {
            using namespace qi;
            using boost::spirit::repository::qi::distinct;
            auto kw = distinct(char_("a-zA-Z0-9_"));

            start   = skip(space) [matches[kw["strict"]] >> kind_ >> graph_];

            kind_  %= kw["digraph"] >> attr(GraphKind::directed)   [ set_arrow_(px::val("->")) ]
                    | kw["graph"]   >> attr(GraphKind::undirected) [ set_arrow_(px::val("--")) ]
                    ;

            graph_    = -ID_ >> stmt_list;
            subgraph_ = -(kw["subgraph"] >> -ID_) >> stmt_list;

            string_   = '"' >> *('\' >> char_ | ~char_('"')) >> '"';
            ID_       = string_ | +char_("a-zA-Z0-9_");

            stmt_list = '{' >> *(stmt >> -lit(';')) >> '}';

            stmt      = attr_stmt
                      | attribute
                      | node_stmt
                      | edge_stmt
                      ;

            attr_stmt = kw[attr_group] >> attr_list;

            attribute = ID_ >> '=' >> ID_;

            node_stmt = node_id >> -attr_list >> !arrow_;

            edge_stmt
                = (node_id | subgraph_) % arrow_ >> -attr_list
                ;

            a_list    = '[' >> *(attribute >> -omit[char_(",;")]) >> ']';
            attr_list = +a_list;

            node_id 
                = ID_ >> (
                        (attr(Ast::Id{}))              >> (':' >> kw[compass_pt]) >> !lit(':')
                      | (':' >> ID_ | attr(Ast::Id{})) >> (':' >> kw[compass_pt] | attr(Ast::CompassPoint::_))
                )
                ;

            BOOST_SPIRIT_DEBUG_NODES(
                 (graph_) (subgraph_)
                 (a_list) (attr_list)
                 (stmt) (attr_stmt) (attribute) (node_stmt) (edge_stmt) (stmt_list)
                 (node_id)
                 (start)(kind_)(ID_)(string_)
            )
        }

      private:
        ////////////////////////
        using Skipper = qi::space_type;

        //////////////////////////////
        // Arrows depend on GraphKind
        qi::symbols<const char> arrow_;

        struct set_arrow_t { // allow dynamic setting
            qi::symbols<const char>& _ref;
            void operator()(const char* op) const { _ref.clear(); _ref.add(op); }
        };
        px::function<set_arrow_t> set_arrow_ { {arrow_} };

        ////////////////////////
        // enums using symbols<>
        struct AttrGroup : qi::symbols<const char, Ast::AttrStmt::Group> {
            AttrGroup() { add
                ("graph", Ast::AttrStmt::Group::graph)
                ("node", Ast::AttrStmt::Group::node)
                ("edge", Ast::AttrStmt::Group::edge);
            }
        } attr_group;

        struct CompassPoint : qi::symbols<const char, Ast::CompassPoint> {
            CompassPoint() { add
                ("n",  Ast::CompassPoint::n)
                ("ne", Ast::CompassPoint::ne)
                ("e",  Ast::CompassPoint::e)
                ("se", Ast::CompassPoint::se)
                ("s",  Ast::CompassPoint::s)
                ("sw", Ast::CompassPoint::sw)
                ("w",  Ast::CompassPoint::w)
                ("nw", Ast::CompassPoint::nw)
                ("c",  Ast::CompassPoint::c)
                ("_",  Ast::CompassPoint::_);
            }
        } compass_pt;

        ////////////////////////
        // productions
        qi::rule<It, Ast::Graph(),     Skipper> graph_, subgraph_;
        qi::rule<It, Ast::AList(),     Skipper> a_list;
        qi::rule<It, Ast::AttrList(),  Skipper> attr_list;
        qi::rule<It, Ast::NodeRef(),   Skipper> node_id; // misnomer

        qi::rule<It, Ast::Stmt(),      Skipper> stmt;
        qi::rule<It, Ast::AttrStmt(),  Skipper> attr_stmt;
        qi::rule<It, Ast::Attr(),      Skipper> attribute;
        qi::rule<It, Ast::NodeStmt(),  Skipper> node_stmt;
        qi::rule<It, Ast::EdgeStmt(),  Skipper> edge_stmt;

        qi::rule<It, Ast::StmtList(),  Skipper> stmt_list;

        // implicit lexemes
        using GraphKind = Ast::GraphKind;
        qi::rule<It, Ast::GraphViz()> start;
        qi::rule<It, GraphKind()> kind_;
        qi::rule<It, Ast::Id()> ID_;
        qi::rule<It, std::string()> string_;
    };
}

DEMO TIME

In fact, this part already parses GraphViz documents. No online compiler was willing to accept this (exceeding the resource limits). Here's the fully sample from this stage: https://wandbox.org/permlink/AYmxpD6lzOdhOeiS

Given the following sample input, exercising as many of the edge cases I could think of at the time:

digraph G {
    graph [rankdir = LR];

    node[shape=record];
    Bar[label="{ \"Bar\"|{<p1>pin 1|<p2>     2|<p3>     3|<p4>     4|<p5>     5} }"];
    Foo[label="{ {<data0>data0|<data1>data1|<data2>data2|<data3>data3|<data4>data4}|\"Foo\" |{<out0>out0|<out1>out1|<out2>out2|<GND>gnd|<ex0>ex0|<hi>hi|<lo>lo} }"];

    Bew[label="{ {<clk>clk|<syn>syn|<mux0>mux0|<mux1>mux1|<signal>signal}|\"Bew\" |{<out0>out0|<out1>out1|<out2>out2} }"];
    Bar:p1 -> Foo:data0;
    Bar:p2 -> Foo:data1;
    Bar:p3 -> Foo:data2;
    Bar:p4 -> Foo:data3;
    Bar:p5 -> Foo:data4;
    hijacked;

    Foo:out0 -> Bew:mux0;
    Foo:out1 -> Bew:mux1;
    Bew:clk -> Foo:ex0;

    Gate[label="{ {<a>a|<b>b}|OR|{<ab>a\|b} }"];

    Foo:hi -> Gate:a;
    Foo:lo -> Gate:b;
    Gate:ab -> Bew:signal;
    subgraph cluster1 {
        graph [
        label=G1];
        2;
        3;
        2 -> 4;
        3 -> 9;
        3 -> 12;
        9 -> 11;
        9 -> 10;
        10 -> 3;
    }

    subgraph cluster2 {
        graph [label=G2];
        10 -> 3;
        more;
        subgraph clusterNested {
            graph [label=nested];
            innermost;
            hijacked[shape=diamond];
        }
    }

    subgraph cluster1 {
        graph [label=G1_override];
        11 -> 4;
        last;
        hijacked;
        subgraph clusterNested {
            graph [label="can override nested?"];
            {
                unnested;
                first_override;
            } [color=red]
        };

    }

    10[shape=circle][color=red];
    10[shape=circle color=red];
    10[shape=circle; color=red,];

    subgraph clusterNested {
        graph [label="can't override nested"];
        unnested;
        second_override;
    }

    more -> last;
}

The output, from my machine (with full debug info in pastebin)

Parse success
(0 directed ( G {(graph {["rankdir"="LR"; ];
                  });
              (node {["shape"="record"; ];
               });
              ((Bar    _) {["label"="{ \"Bar\"|{<p1>pin 1|<p2>     2|<p3>     3|<p4>     4|<p5>     5} }"; ];
               });
              ((Foo    _) {["label"="{ {<data0>data0|<data1>data1|<data2>data2|<data3>data3|<data4>data4}|\"Foo\" |{<out0>out0|<out1>out1|<out2>out2|<GND>gnd|<ex0>ex0|<hi>hi|<lo>lo} }"; ];
               });
              ((Bew    _) {["label"="{ {<clk>clk|<syn>syn|<mux0>mux0|<mux1>mux1|<signal>signal}|\"Bew\" |{<out0>out0|<out1>out1|<out2>out2} }"; ];
               });
              ({(Bar p1    _);
               (Foo data0  _);
               } {});
              ({(Bar p2    _);
               (Foo data1  _);
               } {});
              ({(Bar p3    _);
               (Foo data2  _);
               } {});
              ({(Bar p4    _);
               (Foo data3  _);
               } {});
              ({(Bar p5    _);
               (Foo data4  _);
               } {});
              ((hijacked   _) {});
              ({(Foo out0  _);
               (Bew mux0   _);
               } {});
              ({(Foo out1  _);
               (Bew mux1   _);
               } {});
              ({(Bew clk   _);
               (Foo ex0    _);
               } {});
              ((Gate   _) {["label"="{ {<a>a|<b>b}|OR|{<ab>a|b} }"; ];
               });
              ({(Foo hi    _);
               (Gate a     _);
               } {});
              ({(Foo lo    _);
               (Gate b     _);
               } {});
              ({(Gate ab   _);
               (Bew signal     _);
               } {});
              ((subgraph   _) {});
              ((cluster1   _) {});
              ({(-- {(graph {["label"="G1"; ];
                      });
                 ((2   _) {});
                 ((3   _) {});
                 ({(2      _);
                  (4   _);
                  } {});
                 ({(3      _);
                  (9   _);
                  } {});
                 ({(3      _);
                  (12      _);
                  } {});
                 ({(9      _);
                  (11      _);
                  } {});
                 ({(9      _);
                  (10      _);
                  } {});
                 ({(10     _);
                  (3   _);
                  } {});
              });
              } {});
              ((subgraph   _) {});
              ((cluster2   _) {});
              ({(-- {(graph {["label"="G2"; ];
                      });
                 ({(10     _);
                  (3   _);
                  } {});
                 ((more    _) {});
                 ((subgraph    _) {});
                 ((clusterNested   _) {});
                 ({(-- {(graph {["label"="nested"; ];
                         });
                    ((innermost    _) {});
                    ((hijacked     _) {["shape"="diamond"; ];
                     });
                    });
                  } {});
                 });
               } {});
              ((subgraph   _) {});
              ((cluster1   _) {});
              ({(-- {(graph {["label"="G1_override"; ];
                      });
                 ({(11     _);
                  (4   _);
                  } {});
                 ((last    _) {});
                 ((hijacked    _) {});
                 ((subgraph    _) {});
                 ((clusterNested   _) {});
                 ({(-- {(graph {["label"="can override nested?"; ];
                         });
                    ({(-- {((unnested      _) {});
                       ((first_override    _) {});
                       });
                     } {["color"="red"; ];
                     });
                    });
                  } {});
                 });
               } {});
              ((10     _) {["shape"="circle"; ];
               ["color"="red"; ];
               });
              ((10     _) {["color"="red"; "shape"="circle"; ];
               });
              ((10     _) {["color"="red"; "shape"="circle"; ];
               });
              ((subgraph   _) {});
              ((clusterNested      _) {});
              ({(-- {(graph {["label"="can't override nested"; ];
                      });
                 ((unnested    _) {});
                 ((second_override     _) {});
                 });
               } {});
              ({(more      _);
               (last   _);
               } {});
}))
Remaining unparsed input: '
'

¹ Boost Spirit: "Semantic actions are evil"?

² 我将这种复杂性分类 "Impedance Mismatch"，这是我最初从对象关系映射框架中学到的术语

如何使用具有强制性最小元素数量的boost spirit list运算符？

How to use boost spirit list operator with mandatory minimum amount of elements?

c++

boost

boost-spirit

boost-spirit-qi

注意事项

如何解决

模型

AST

语法

DEMO TIME