Анализатор логических выражений (грамматика) в c ++ - PullRequest
Новая
       16

Анализатор логических выражений (грамматика) в c ++

31 голосов
/ 03 января 2012

Я хочу разобрать логическое выражение (в C ++).Форма ввода: 

a and b xor (c and d or a and b);

Я просто хочу проанализировать это выражение в дереве, зная правило приоритета (не, и, или не, или).Поэтому приведенное выше выражение должно выглядеть примерно так: 

(a and b) xor ((c and d) or (a and b));

для синтаксического анализатора.

И дерево будет иметь форму: 

                        a
                   and
                        b
               or
                        c
                   and
                        d
        xor
                   a
              and
                   b

Ввод будет либочерез командную строку или в виде строки.Мне просто нужен парсер.

Есть ли источники, которые могут мне помочь в этом?

Ответы [ 5 ]

89 голосов
/ 03 января 2012

Вот реализация, основанная на Boost Spirit.

Поскольку Boost Spirit генерирует рекурсивные спуски синтаксические анализаторы на основе шаблонов выражений , соблюдение «уникальных» (sic) правил приоритета (как упоминалось другими) довольно утомительно. Поэтому грамматике не хватает определенной элегантности.

Абстрактный тип данных

Я определил древовидную структуру данных, используя поддержку рекурсивного варианта Boost Variant, обратите внимание на определение expr: 

struct op_or  {}; // tag
struct op_and {}; // tag
struct op_xor {}; // tag
struct op_not {}; // tag

typedef std::string var;
template <typename tag> struct binop;
template <typename tag> struct unop;

typedef boost::variant<var, 
        boost::recursive_wrapper<unop <op_not> >, 
        boost::recursive_wrapper<binop<op_and> >,
        boost::recursive_wrapper<binop<op_xor> >,
        boost::recursive_wrapper<binop<op_or> >
        > expr;

(полный источник ниже)

Правила грамматики

Ниже приведено (немного утомительное) определение грамматики, как упоминалось.

Хотя я не считаю эту грамматику оптимальной, она вполне читаема, и у нас есть статически скомпилированный синтаксический анализатор со строго типизированным типом данных AST в примерно 50 строках кода. Все могло быть значительно хуже. 

template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr(), Skipper>
{
    parser() : parser::base_type(expr_)
    {
        using namespace qi;
        expr_  = or_.alias();

        or_  = (xor_ >> "or"  >> xor_) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
        xor_ = (and_ >> "xor" >> and_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
        and_ = (not_ >> "and" >> not_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];

        simple = (('(' > expr_ > ')') | var_);
        var_ = qi::lexeme[ +alpha ];
    }

  private:
    qi::rule<It, var() , Skipper> var_;
    qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};

Работа с синтаксическим деревом

Очевидно, вы захотите оценить выражения. Сейчас я решил остановиться только на печати, поэтому мне не нужно искать таблицу для именованных переменных:)

Обход рекурсивного варианта на первый взгляд может показаться загадочным, но boost::static_visitor<> удивительно прост, как только вы его освоите: 

struct printer : boost::static_visitor<void>
{
    printer(std::ostream& os) : _os(os) {}
    std::ostream& _os;

    //
    void operator()(const var& v) const { _os << v; }

    void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }
    void operator()(const binop<op_xor>& b) const { print(" ^ ", b.oper1, b.oper2); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        _os << "(";
            boost::apply_visitor(*this, l);
            _os << op;
            boost::apply_visitor(*this, r);
        _os << ")";
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << "(";
            _os << "!";
            boost::apply_visitor(*this, u.oper1);
        _os << ")";
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(printer(os), e); return os; }

Тестовый вывод:

Для тестовых случаев в коде выводится следующее, демонстрирующее правильную обработку правил приоритета путем добавления (избыточных) скобок: 

result: ((a & b) ^ ((c & d) | (a & b)))
result: ((a & b) ^ ((c & d) | (a & b)))
result: (a & b)
result: (a | b)
result: (a ^ b)
result: (!a)
result: ((!a) & b)
result: (!(a & b))
result: (a | (b | c))

Полный код: 

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/variant/recursive_wrapper.hpp>

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

struct op_or  {};
struct op_and {};
struct op_xor {};
struct op_not {};

typedef std::string var;
template <typename tag> struct binop;
template <typename tag> struct unop;

typedef boost::variant<var, 
        boost::recursive_wrapper<unop <op_not> >, 
        boost::recursive_wrapper<binop<op_and> >,
        boost::recursive_wrapper<binop<op_xor> >,
        boost::recursive_wrapper<binop<op_or> >
        > expr;

template <typename tag> struct binop 
{ 
    explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { }
    expr oper1, oper2; 
};

template <typename tag> struct unop  
{ 
    explicit unop(const expr& o) : oper1(o) { }
    expr oper1; 
};

struct printer : boost::static_visitor<void>
{
    printer(std::ostream& os) : _os(os) {}
    std::ostream& _os;

    //
    void operator()(const var& v) const { _os << v; }

    void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }
    void operator()(const binop<op_xor>& b) const { print(" ^ ", b.oper1, b.oper2); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        _os << "(";
            boost::apply_visitor(*this, l);
            _os << op;
            boost::apply_visitor(*this, r);
        _os << ")";
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << "(";
            _os << "!";
            boost::apply_visitor(*this, u.oper1);
        _os << ")";
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(printer(os), e); return os; }

template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr(), Skipper>
{
    parser() : parser::base_type(expr_)
    {
        using namespace qi;

        expr_  = or_.alias();

        or_  = (xor_ >> "or"  >> or_ ) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
        xor_ = (and_ >> "xor" >> xor_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
        and_ = (not_ >> "and" >> and_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];

        simple = (('(' > expr_ > ')') | var_);
        var_ = qi::lexeme[ +alpha ];

        BOOST_SPIRIT_DEBUG_NODE(expr_);
        BOOST_SPIRIT_DEBUG_NODE(or_);
        BOOST_SPIRIT_DEBUG_NODE(xor_);
        BOOST_SPIRIT_DEBUG_NODE(and_);
        BOOST_SPIRIT_DEBUG_NODE(not_);
        BOOST_SPIRIT_DEBUG_NODE(simple);
        BOOST_SPIRIT_DEBUG_NODE(var_);
    }

  private:
    qi::rule<It, var() , Skipper> var_;
    qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};

int main()
{
    for (auto& input : std::list<std::string> {
            // From the OP:
            "(a and b) xor ((c and d) or (a and b));",
            "a and b xor (c and d or a and b);",

            /// Simpler tests:
            "a and b;",
            "a or b;",
            "a xor b;",
            "not a;",
            "not a and b;",
            "not (a and b);",
            "a or b or c;",
            })
    {
        auto f(std::begin(input)), l(std::end(input));
        parser<decltype(f)> p;

        try
        {
            expr result;
            bool ok = qi::phrase_parse(f,l,p > ';',qi::space,result);

            if (!ok)
                std::cerr << "invalid input\n";
            else
                std::cout << "result: " << result << "\n";

        } catch (const qi::expectation_failure<decltype(f)>& e)
        {
            std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
        }

        if (f!=l) std::cerr << "unparsed: '" << std::string(f,l) << "'\n";
    }

    return 0;
}

Бонус:

Для получения бонусных баллов, чтобы получить дерево в точности как показано в ОП: 

static const char indentstep[] = "    ";

struct tree_print : boost::static_visitor<void>
{
    tree_print(std::ostream& os, const std::string& indent=indentstep) : _os(os), _indent(indent) {}
    std::ostream& _os;
    std::string _indent;

    void operator()(const var& v) const { _os << _indent << v << std::endl; }

    void operator()(const binop<op_and>& b) const { print("and ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print("or  ", b.oper2, b.oper1); }
    void operator()(const binop<op_xor>& b) const { print("xor ", b.oper2, b.oper1); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        boost::apply_visitor(tree_print(_os, _indent+indentstep), l);
        _os << _indent << op << std::endl;
        boost::apply_visitor(tree_print(_os, _indent+indentstep), r);
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << _indent << "!";
        boost::apply_visitor(tree_print(_os, _indent+indentstep), u.oper1);
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ 
    boost::apply_visitor(tree_print(os), e); return os; 
}

результат: 

            a
        and 
            b
    or  
            c
        and 
            d
xor 
        a
    and 
        b
5 голосов
/ 03 января 2012

Либо используйте генератор синтаксического анализатора, как уже упоминал Оли Чарльзуорт (yacc, bison, antlr; последний, по моему опыту, лучше подходит для C ++, чем два других, хотя я какое-то время смотрел на них) или создайте простой синтаксический анализатор с рекурсивным спуском: для такого простого языка, как ваш, это может быть более простой подход.

2 голосов
/ 03 января 2012

См. мой SO-ответ о том, как кодировать простые парсеры рекурсивного спуска .

Этот подход очень удобен для простых языков, таких как булевы выражения. И концепции в значительной степени не зависят от вашего языка программирования.

1 голос
/ 03 января 2012

Если, как и я, вы обнаружите, что издержки и особенности разбора библиотек слишком велики для такой маленькой работы, вы можете очень легко написать собственный анализатор для простого сценария, подобного тому, который вы представляете.Смотрите здесь для парсера, который я написал на C #, чтобы разобрать простые выражения C # в соответствии с вашими требованиями.

0 голосов
/ 11 апреля 2012

Посмотрите на пример кода Mini C https://github.com/boostorg/spirit/tree/master/example/qi/compiler_tutorial/mini_c.

В частности, обратите внимание на выражения.cpp, expression.hpp, expression_def.hpp и ast.hpp. Это хороший пример того, как анализировать выражения в AST.

...