Pracowałem z kolegą nad tłumaczem języka i zaczęliśmy od decyzji, która chyba nie była taka mądra: najpierw zrobiliśmy wszystkie elementy do wykonania (praktycznie drzewo z różnych klas); ale teraz patrząc na przykłady doładowań, jestem bardzo zdezorientowany, jak połączyć te dwa. Wiem od czego zacząć (gramatyka), wiem, do czego dotrzeć (klasy instancjonowane będące współwłaścicielami), nie wiem jak to osiągnąć.

Zaczęliśmy od wyrażeń bez zmiennych, dlatego przyjrzeliśmy się przykładom kalkulatora duchowego; ale nie rozumiem, kiedy tworzyć wystąpienia elementów.

Przykładowe elementy wyrażenia:

namespace exp
{
class op
    {
    private:
    public:
        virtual double exec(function_scope &fs);

    };

class operand : public op
    {
    private:
        double value;

    public:
        operand(double value);
        double exec(function_scope &fs);
    };

class op_bin : public op
    {
    private:
    public:
        op * ll;
        op* rr;
        op_bin(op* ll, op* rr);
        ~op_bin();
    };

namespace bin
    {
    class sum : public op_bin
        {
        public:
            sum(op* ll, op* rr);
            double exec(function_scope &fs);
        };
    }
}

Zignoruj ​​funkcję exec, jest ona używana w czasie wykonywania.

Na przykład kod 5 + (2 + 1) powinien skutkować końcowym odpowiednikiem:

new exp::bin::sum(new exp::operand(5), new exp::bin::sum(new exp::operand(2), new exp::operand(1))

Kiedy już zrozumiem, jak to zrobić, praktycznie to zrobiłem.

1
Barnack 15 listopad 2018, 15:58

1 odpowiedź

Najlepsza odpowiedź

Cóż, chciałem napisać, co jest nie tak z twoim pytaniem, ale zamiast tego poszedłem udowodnić sobie, że nie jest tak trudno zrobić to, czego chcesz.

Kilka kluczowych punktów:

  • Lekko zmodyfikowałem, zmieniłem nazwę i rozszerzyłem twój ast, aby działał i faktycznie coś pokazywał.
  • Reguły duchowe z jakiegoś powodu tworzą kopię atrybutu (myślę, że to błąd), więc obejście ten problem dla unique_ptr z cechą. (naprawiono w 1.70)
  • Nie jestem pewien, czy x3::omit jest tam rzeczywiście wymagany (możesz usunąć wszystkie oprócz ostatniego, a się skompiluje), ale wygląda na to, że jest to kolejny błąd w Spirit.
  • make_node wygląda niewiarygodnie i może się zepsuć w zaskakujący sposób, jeśli chcesz, możesz podzielić go na oddzielnych twórców węzłów jednoargumentowych/binarnych.
  • W pewnym momencie będziesz chciał użyć alokatora stanowego do tworzenia węzłów ast, powinno to być bardzo proste poprzez wstrzyknięcie alokatora do kontekstu parsera. Zostawiam to dla ciebie jako ćwiczenie.

Parser:

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

namespace ast
{

class expression
{
protected:
    expression() = default;
public:
    virtual ~expression() = default;
    expression(expression&& other) = delete;
    expression& operator=(expression&& other) = delete;

    virtual void print(std::ostream&) const = 0;

    friend std::ostream& operator<<(std::ostream& os, expression const& node)
    {
        node.print(os);
        return os;
    }
};

class operand : public expression
{
    double value_;

public:
    constexpr operand(double value) : value_{value} {}
    void print(std::ostream& os) const override { os << value_; }
};

class op_bin : public expression
{
protected:
    std::unique_ptr<expression> left_, right_;

public:
    op_bin(std::unique_ptr<expression> left, std::unique_ptr<expression> right)
      : left_{ std::move(left) }, right_{ std::move(right) }
    {}

    op_bin(expression * left, expression * right)
        : left_{ left }, right_{ right }
    {}
};

class plus : public op_bin
{
public:
    using op_bin::op_bin;
    void print(std::ostream& os) const override
    { os << '(' << *left_ << " + " << *right_ << ')'; }
};

class minus : public op_bin
{
public:
    using op_bin::op_bin;
    void print(std::ostream& os) const override
    { os << '(' << *left_ << " - " << *right_ << ')'; }
};

class mul : public op_bin
{
public:
    using op_bin::op_bin;
    void print(std::ostream& os) const override
    { os << '(' << *left_ << " * " << *right_ << ')'; }
};

class div : public op_bin
{
public:
    using op_bin::op_bin;
    void print(std::ostream& os) const override
    { os << '(' << *left_ << " / " << *right_ << ')'; }
};

} // namespace ast

namespace grammar
{

namespace x3 = boost::spirit::x3;

template <typename T>
struct make_node_
{
    template <typename Context>
    void operator()(Context const& ctx) const
    {
        if constexpr (std::is_convertible_v<decltype(x3::_attr(ctx)), T>) {
            x3::_val(ctx) = std::make_unique<T>(std::move(x3::_attr(ctx)));
        }
        else {
            x3::_val(ctx) = std::make_unique<T>(std::move(x3::_val(ctx)), std::move(x3::_attr(ctx)));
        }
    }
};

template <typename T>
constexpr make_node_<T> make_node{};

using x3::double_;
using x3::char_;

x3::rule<class expression_r, std::unique_ptr<ast::expression>, true> const expression;
x3::rule<class prec1_r, std::unique_ptr<ast::expression>, true> const prec1;
x3::rule<class prec0_r, std::unique_ptr<ast::expression>, true> const prec0;

auto const expression_def =
    prec1
    >> *(   x3::omit[('+' > prec1)[make_node<ast::plus>]]
        |   x3::omit[('-' > prec1)[make_node<ast::minus>]]
        )
    ;

auto const prec1_def =
    prec0
    >> *(   x3::omit[('*' > prec0)[make_node<ast::mul>]]
        |   x3::omit[('/' > prec0)[make_node<ast::div>]]
        )
    ;

auto const prec0_def =
        x3::omit[double_[make_node<ast::operand>]]
    |   '(' > expression > ')'
    ;

BOOST_SPIRIT_DEFINE(
    expression
  , prec1
  , prec0
);

} // namespace grammar

#if BOOST_VERSION < 107000
namespace boost::spirit::x3::traits {

template <typename Attribute>
struct make_attribute<std::unique_ptr<Attribute>, std::unique_ptr<Attribute>>
  : make_attribute_base<std::unique_ptr<Attribute>>
{
    typedef std::unique_ptr<Attribute>& type;
    typedef std::unique_ptr<Attribute>& value_type;
};

} // namespace boost::spirit::x3::traits
#endif

int main()
{
    namespace x3 = boost::spirit::x3;

    std::string s = "1 + 2 * (3 - 4) / 5";
    std::unique_ptr<ast::expression> expr;
    if (auto iter = s.cbegin(); !phrase_parse(iter, s.cend(), grammar::expression, x3::space, expr)) {
        std::cout << "parsing failed";
    }
    else {
        if (iter != s.cend())
            std::cout << "partially parsed\n";
        std::cout << *expr << '\n';
    }
}

Wynik:

(1 + ((2 * (3 - 4)) / 5))
5
Nikita Kniazev 9 listopad 2019, 21:39