c++ - 如何用Boosting Spirit编写 'c like if'解析器

Question

我想编写一个规则来解析类似的内容:
如果(1 == 1){做某事}
我的问题是如何基于另一条规则的输出结果来“禁用”语义 Action 。
为了在我的示例中进行演示，我使用了一个int_解析器，并将该值用作结果。如果ifrule返回false，我想绕过该操作。

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <iomanip>

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

int main() {
    qi::symbols<char, std::function<bool(int, int)>> sym;
    sym.add
    ("==", std::equal_to<>())
    ("!=", std::not_equal_to<>());

    using namespace qi::labels;
    int result;
    auto bin_eval = [](auto const& lhs, auto const& op, auto const& rhs) {
        return op(lhs, rhs);
    };

    qi::rule<std::string::const_iterator, bool(), qi::space_type> ifrule;
    ifrule = (qi::lit("if") >> '(' >> qi::int_ >> sym >> qi::int_ >> ')')
            [qi::_val = px::bind(bin_eval, _1, _2, _3)];
    qi::rule<std::string::const_iterator, int(), qi::space_type> rule;
    rule = ifrule >> '{' >> qi::int_[_val = _1] >> '}';

    for (std::string const s : {"if (1==2) {1}", "if (1==1) {1}"}) {
        std::cout << std::quoted(s) << " -> ";

        if (qi::phrase_parse(s.begin(), s.end(), rule, qi::space, result)) {
            std::cout << "result: " << std::boolalpha << result << "\n";
        } else {
            std::cout << "parse failed\n";
        }
    }
}

Answer 1

您是否正在寻找捷径评估？

如果是这样，除了修改输入之外，您几乎不需要执行任何操作即可获得该效果，也无需执行任何操作。

只要您将解析和评估结合起来，就一定会访问整个表达式树(因为您必须对其进行解析)。

仅当使用AST树时，您才能进行优化:

简化树的

静态优化(消除双重否定，消除重言式，解决x xor not x -> not (x and not x) -> not (false) -> true之类的矛盾

这是一个丰富的主题，并不像看起来那样简单(请参见Boost Spirit: parse boolean expression and reduce to canonical normal form)

运行时优化，这是进入快捷方式评估的地方。 a && (b | (c ^ d) | (!a & (b ^ c))) would be
[![enter image description here][1]][1]. If为false的is false, the entire evaluation can be skipped because the result will be。

Is your grammar an expression grammar or a statement parser? What should be the value of result if the condition is false? – sehe just now

假设答案是“表达式”而不是“语句”，那么可以说这只是一个带有一些二进制运算符和一个三元(带有隐式else分支)的表达式解析器。

在这种情况下，您可以作弊并仅返回一个可选值。

我将向您展示一个更完整的基于AST的示例，因为您可能试图解析比平时显示的内容更为琐碎的内容。

AST

与往常一样，想一想您的抽象语法树是什么样子:

namespace Ast {

    struct BinOp;
    struct Conditioinal;

    using Expr = boost::variant<
        int,
        bool,
        BinOp,
        Conditional
    >;

    struct BinOp {
        BinOpF op;
        Expr lhs, rhs;
    };

    struct Conditional {
        Expr condition, true_part;
    };
}

我已经从您的代码中为运算符定义了函数:

using BinOpF = std::function<bool(int, int)>;

该变体实际上不会使用递归使用不完整类型进行编译，因此让我们使用包装器:

using Expr = boost::variant<
    int,
    bool,
    boost::recursive_wrapper<BinOp>,
    boost::recursive_wrapper<Conditional>
>;

解析中

解析器构造通常是规则的1:1映射:

    expr
        = '(' >> expr >> ')'
        | conditional_
        | int_ 
        | bool_ 
        | binop_
        ;

让我们将其放在一个语法中(这也隐藏了船长)。

Note I also shuffled the binop parser around splitting expr_ into simple_ and using semantic actions to create the BinOp Ast nodes for efficiency. This stems from experience that grammars get horrifically inefficient with backtracking otherwise.

template <typename It>
struct Expr : qi::grammar<It, Ast::Expr()> {
    Expr() : Expr::base_type(start) {
        using namespace qi;
        start = qi::skip(space) [ expr_ ];

        simple_
            = '(' >> expr_ >> ')'
            | conditional_
            | int_ 
            | bool_ 
            ;

        auto make_bin = [](auto lhs, auto op, auto rhs) {
            return Ast::BinOp { op, lhs, rhs };
        };

        expr_ %= simple_
            >> *(binop_ >> expr_) [ _val = px::bind(make_bin, _val, _1, _2) ];
            ;

        conditional_
            = lexeme["if"] 
            >> '(' >> expr_ >> ')' 
            >> '{' >> expr_ >> '}'
            ;

        binop_.add
            ("==", std::equal_to<>())
            ("!=", std::not_equal_to<>());

        BOOST_SPIRIT_DEBUG_NODES((start)(expr_)(conditional_))
    }

  private:
    qi::rule<It, Ast::Expr()> start;
    qi::rule<It, Ast::Expr(), qi::space_type> simple_, expr_;
    qi::rule<It, Ast::Conditional(), qi::space_type> conditional_;

    qi::symbols<char, Ast::BinOpF> binop_;
};

而已。请注意，它将解析以前解析器无法解析的大量表达式。例如。:

Live On Coliru

int main() {
    Expr<std::string::const_iterator> const parser;

    for (std::string const s : {
        "false",
        "1==2",
        "-3!=3",
        "if (true) {42}",
        "if (false) {43}",
        "if (1==2) {44}",
        "if (false == (1 == 2)) {  ((((45)))) }",
        "if (false == (1 == 2)) { if (true) {46} }",
        "if (true == (1 == 2)) {47} else { 48 };",
    }) {
        std::cout << std::quoted(s) << " -> ";

        auto f = begin(s);
        auto l = end(s);
        Ast::Expr expr;
        if (qi::parse(f, l, parser, expr)) {
            std::cout << "result: " << expr << "\n";
        } else {
            std::cout << "parse failed\n";
        }

        if (f!=l) {
            std::cout << "Remaining unparsed input: " << std::quoted(std::string(f,l)) << "\n";
        }
    }
}

版画

"false" -> result: 0
"1==2" -> result: (1 (opfun) 2)
"-3!=3" -> result: (-3 (opfun) 3)
"if (true) {42}" -> result: if(1) {42}
"if (false) {43}" -> result: if(0) {43}
"if (1==2) {44}" -> result: if((1 (opfun) 2)) {44}
"if (false == (1 == 2)) {  ((((45)))) }" -> result: if((0 (opfun) (1 (opfun) 2))) {45}
"if (false == (1 == 2)) { if (true) {46} }" -> result: if((0 (opfun) (1 (opfun) 2))) {if(1) {46}}
"if (true == (1 == 2)) {47} else { 48 };" -> result: if((1 (opfun) (1 (opfun) 2))) {47}
Remaining unparsed input: " else { 48 };"

评价

剩下的就是实际评估。结果将是一个可选值，对于您的示例，该值可以为 optional<int>，但我将其设置为 variant<Nil, int, bool>，以便我们也可以表示条件:

namespace Evaluation {
    struct Nil {};
    using Value = boost::variant<Nil, int, bool>;

现在，引擎是一个将访问我们的AST节点的函数对象:

    struct Engine {
        template <typename... T> auto operator()(T const&... v) const {
            return eval(v...);
        }

      private:

将对 operator()的任何调用委派给私有(private) eval方法可以使事情更容易阅读，并且实现起来非常简单:

Value eval(Ast::Expr const& e) const  { return boost::apply_visitor(*this, e); } 
Value eval(int e) const               { return e;                              } 
Value eval(bool e) const              { return e;                              } 
Value eval(Ast::BinOp const& e) const { return e.op(as_int(e.lhs), as_int(e.rhs)); } 

在这里，我们看到了逻辑的第一部分。由于 BinUpF是 bool(int,int)，我们必须将参数强制为int。

Value eval(Ast::Conditional const& e) const { 
    Value True = true;
    if (eval(e.condition) == True) {
        return eval(e.true_part);
    }

    return Nil{};
} 

这是我们 最终回答您的问题的地方:如果 true_part评估为false¹，则永远不会评估 condition¹

测试＃1

测试当前状态:

Evaluation::Engine const eval;

// ...

    if (qi::parse(f, l, parser, expr)) {
        std::cout << "expr: " << expr << "\n";

        try {
            auto result = eval(expr);
            std::cout << "result: " << result << "\n";
        } catch(boost::bad_get const&) {
            std::cout << "result: Type mismatch\n";
        }
    } else {
        std::cout << "parse failed\n";
    }

打印 Live On Coliru

result: 0
result: 0
result: 1
result: 42
result: Nil
result: Nil
"false" -> expr: 0
"1==2" -> expr: (1 (opfun) 2)
"-3!=3" -> expr: (-3 (opfun) 3)
"if (true) {42}" -> expr: if(1) {42}
"if (false) {43}" -> expr: if(0) {43}
"if (1==2) {44}" -> expr: if((1 (opfun) 2)) {44}

以下表达式失败，因为操作数不是整数:

"if (false == (1 == 2)) {  ((((45)))) }" -> expr: if((0 (opfun) (1 (opfun) 2))) {45}
result: Type mismatch
"if (false == (1 == 2)) { if (true) {46} }" -> expr: if((0 (opfun) (1 (opfun) 2))) {if(1) {46}}
result: Type mismatch
"if (true == (1 == 2)) {47} else { 48 };" -> expr: if((1 (opfun) (1 (opfun) 2))) {47}
result: Type mismatch
Remaining unparsed input: " else { 48 };"

三种改进

让我们允许混合类型求值(true != false也应该起作用，对吗？以及true == (1!=9)。

将功能类型从bool(int,int)更改为Value(Value,Value)可以实现完整色域。

namespace Evaluation {
    struct Nil { bool operator==(Nil) const { return true; } };
    using Value = boost::variant<Nil, int, bool>;

    using BinOpF = std::function<Value(Value, Value)>;

对于混合类型评估，我们需要一些帮助，因为std::equal_to和 friend 不知道如何进行(二进制)变体访问。因此，我们为此做一个包装:

template <typename Op> struct MixedOp {
    Value operator()(Value const& lhs, Value const& rhs) const {
        return boost::apply_visitor(Dispatch{}, lhs, rhs);
    }

  private:
    struct Dispatch {
        template <typename T, typename U>
        Value operator()(T const& lhs, U const& rhs, decltype(Op{}(T{}, U{}))* = nullptr) const 
            { return Op{}(lhs, rhs); }

        template <typename... T>
        Value operator()(T const&...) const 
             { throw std::logic_error("Type mismatch " + std::string(__PRETTY_FUNCTION__)); }
    };
};

是的这很丑陋，但请注意它如何自然适用于大多数运算符功能(例如std::plus<>，std::multiplies<>等)。

// wrap std functionals
using equal_to     = detail::MixedOp<std::equal_to<> >;
using not_equal_to = detail::MixedOp<std::not_equal_to<> >;
using plus         = detail::MixedOp<std::plus<> >;
using minus        = detail::MixedOp<std::minus<> >;
using multiplies   = detail::MixedOp<std::multiplies<> >;
using divides      = detail::MixedOp<std::divides<> >;

让我们也这样，使值的真实性更好(0应该像C语言一样，应该只表示false，就像Nil一样)。

让我们得到真实性:

namespace detail {
    struct truthy {
        Value operator()(Value const& v) const { return boost::apply_visitor(*this, v); }
        Value operator()(int  v) const { return static_cast<bool>(v); }
        Value operator()(bool v) const { return static_cast<bool>(v); }
        Value operator()(Nil)    const { return Nil{}; }
    };

然后定义一个免费函数，以方便从我们的引擎调用:

static inline bool truthy(Value const& v) { return Value{true} == detail::truthy{}(v); }

现在，我们可以从Evaluation::Engine中删除复杂性:

Value eval(Ast::BinOp const& e) const { return e.op(eval(e.lhs), eval(e.rhs)); } 
Value eval(Ast::Conditional const& e) const { 
    if (truthy(eval(e.condition))) {
        return eval(e.true_part);
    }

    return Nil{};
} 

没有更多的as_inst或True比较。

让我们支持else
从上面的内容开始，这是非常简单的。但这会很好地证明实际上只评估了一个分支，例如当一个分支包含零除。

Value eval(Ast::Conditional const& e) const { 
    if (truthy(eval(e.condition))) {
        return eval(e.true_part);
    }
    if (e.false_part) {
        return eval(*e.false_part);
    }

    return Nil{};
} 

完整演示

Live On Coliru

//#define BOOST_SPIRIT_DEBUG
#include <boost/fusion/adapted.hpp>
#include <boost/fusion/include/io.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <iomanip>

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

namespace Evaluation {
    struct Nil { bool operator==(Nil) const { return true; } };
    using Value = boost::variant<Nil, int, bool>;

    using BinOpF = std::function<Value(Value, Value)>;

    namespace detail {
        struct truthy {
            Value operator()(Value const& v) const { return boost::apply_visitor(*this, v); }
            Value operator()(int  v) const { return static_cast<bool>(v); }
            Value operator()(bool v) const { return static_cast<bool>(v); }
            Value operator()(Nil)    const { return Nil{}; }
        };

        template <typename Op> struct MixedOp {
            Value operator()(Value const& lhs, Value const& rhs) const {
                return boost::apply_visitor(Dispatch{}, lhs, rhs);
            }

          private:
            struct Dispatch {
                template <typename T, typename U>
                Value operator()(T const& lhs, U const& rhs, decltype(Op{}(T{}, U{}))* = nullptr) const 
                    { return Op{}(lhs, rhs); }

                template <typename... T>
                Value operator()(T const&...) const 
                     { throw std::logic_error("Type mismatch " + std::string(__PRETTY_FUNCTION__)); }
            };
        };
    }

    static inline bool truthy(Value const& v) { return Value{true} == detail::truthy{}(v); }

    // wrap std functionals
    using equal_to     = detail::MixedOp<std::equal_to<> >;
    using not_equal_to = detail::MixedOp<std::not_equal_to<> >;
    using plus         = detail::MixedOp<std::plus<> >;
    using minus        = detail::MixedOp<std::minus<> >;
    using multiplies   = detail::MixedOp<std::multiplies<> >;
    using divides      = detail::MixedOp<std::divides<> >;
}

namespace Ast {

    struct BinOp;
    struct Conditional;

    using Expr = boost::variant<
        int,
        bool,
        boost::recursive_wrapper<BinOp>,
        boost::recursive_wrapper<Conditional>
    >;

    struct BinOp {
        Evaluation::BinOpF op;
        Expr lhs, rhs;
    };

    struct Conditional {
        Expr condition, true_part;
        boost::optional<Expr> false_part;
    };
}

BOOST_FUSION_ADAPT_STRUCT(Ast::Conditional, condition, true_part, false_part)

namespace Parsing {
    template <typename It>
    struct Expr : qi::grammar<It, Ast::Expr()> {
        Expr() : Expr::base_type(start) {
            using namespace qi;
            start = qi::skip(space) [ expr_ ];

            simple_
                = '(' >> expr_ >> ')'
                | conditional_
                | int_ 
                | bool_ 
                ;

            auto make_bin = [](auto lhs, auto op, auto rhs) {
                return Ast::BinOp { op, lhs, rhs };
            };

            expr_ %= simple_
                >> *(binop_ >> expr_) [ _val = px::bind(make_bin, _val, _1, _2) ];
            ;

            conditional_
                = lexeme["if"] 
                >> '(' >> expr_ >> ')' 
                >> '{' >> expr_ >> '}'
                >> -(lit("else") >> '{' >> expr_ >> '}')
                ;

            binop_.add
                ("==", Evaluation::equal_to())
                ("!=", Evaluation::not_equal_to())
                ("+",  Evaluation::plus())
                ("-",  Evaluation::minus())
                ("*",  Evaluation::multiplies())
                ("/",  Evaluation::divides())
                ;

            BOOST_SPIRIT_DEBUG_NODES((start)(expr_)(conditional_))
        }

        private:
        qi::rule<It, Ast::Expr()> start;
        qi::rule<It, Ast::Expr(), qi::space_type> simple_, expr_;
        qi::rule<It, Ast::Conditional(), qi::space_type> conditional_;

        qi::symbols<char, Evaluation::BinOpF> binop_;
    };
}

namespace Evaluation {
    struct Engine {
        template <typename... T> auto operator()(T const&... v) const {
            return eval(v...);
        }

      private:
        Value eval(Ast::Expr const& e) const  { return boost::apply_visitor(*this, e); } 
        Value eval(int e) const               { return e;                              } 
        Value eval(bool e) const              { return e;                              } 
        Value eval(Ast::BinOp const& e) const { return e.op(eval(e.lhs), eval(e.rhs)); } 
        Value eval(Ast::Conditional const& e) const { 
            if (truthy(eval(e.condition))) {
                return eval(e.true_part);
            }
            if (e.false_part) {
                return eval(*e.false_part);
            }

            return Nil{};
        } 
    };
}

namespace Ast { // for debug output only
    static inline std::ostream& operator<<(std::ostream& os, BinOp const& b) {
        return os << "(" << b.lhs << " (opfun) " << b.rhs << ")";
    }

    static inline std::ostream& operator<<(std::ostream& os, Conditional const& c) {
        os << "if(" << c.condition << ") {" << c.true_part << "}";
        if (c.false_part)
            os << "else{" << *c.false_part << "}";
        return os;
    }
}
namespace Evaluation { // for debug output only
    static inline std::ostream& operator<<(std::ostream& os, Nil) {
        return os << "Nil";
    }
}

int main() {
    Parsing::Expr<std::string::const_iterator> const parser;
    Evaluation::Engine const eval;

    for (std::string const s : {
        "false",
        "1==2",
        "-3!=3",
        "if (true) {42}",
        "if (false) {43}",
        "if (1==2) {44}",
        "if (false == (1 == 2)) {  ((((45)))) }",
        "if (false == (1 == 2)) { if (true) {46} }",
        "if (true == (1 == 2)) {47} else { 48 }",
        // cherry on top:
        "if (false) { 3*3 / 0 } else { 7*7 }", // note division by zero
    }) {
        std::cout << std::quoted(s) << " -> ";

        auto f = begin(s);
        auto l = end(s);
        Ast::Expr expr;
        if (qi::parse(f, l, parser, expr)) {
            std::cout << "expr: " << expr << "\n";

            try {
                std::cout << "result: " << eval(expr) << "\n";
            } catch(std::exception const& e) {
                std::cout << "result: " << e.what() << "\n";
            }
        } else {
            std::cout << "parse failed\n";
        }

        if (f!=l) {
            std::cout << "Remaining unparsed input: " << std::quoted(std::string(f,l)) << "\n";
        }
    }
}

版画

"false" -> expr: 0
result: 0
"1==2" -> expr: (1 (opfun) 2)
result: 0
"-3!=3" -> expr: (-3 (opfun) 3)
result: 1
"if (true) {42}" -> expr: if(1) {42}
result: 42
"if (false) {43}" -> expr: if(0) {43}
result: Nil
"if (1==2) {44}" -> expr: if((1 (opfun) 2)) {44}
result: Nil
"if (false == (1 == 2)) {  ((((45)))) }" -> expr: if((0 (opfun) (1 (opfun) 2))) {45}
result: 45
"if (false == (1 == 2)) { if (true) {46} }" -> expr: if((0 (opfun) (1 (opfun) 2))) {if(1) {46}}
result: 46
"if (true == (1 == 2)) {47} else { 48 }" -> expr: if((1 (opfun) (1 (opfun) 2))) {47}else{48}
result: 48
"if (false) { 3*3 / 0 } else { 7*7 }" -> expr: if(0) {(3 (opfun) (3 (opfun) 0))}else{(7 (opfun) 7)}
result: 49

¹实际上是 true以外的其他东西