c++ - 如何使用具有强制性最小元素数量的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分别是--的标记。

问题是上面的代码只会对 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;

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

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

Answer 1

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

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

注意事项

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

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

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

如何解决

虽然我通常不是语义 Action 的粉丝¹，但语义 Action 似乎是这里要使用的东西。您可以通过使用“事件”响应每个解析的规则来模仿 Graphviz 的解析器的行为，该“事件”可以由有状态的“构建器”处理，从而导致对域模型进行适当的更改。

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

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

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

模型

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

TODO(但请参阅评论中的更新)

AST

让我们创建一组单独的 类来表示源文档。注意:

• 这紧跟http://www.graphviz.org/doc/info/lang.html
• 以后有意与我们的 spirit 规则保持 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"?

² 我将这类复杂性归类为“阻抗失配”，这是我最初从对象关系映射框架中学到的一个术语