用Spirit作为AST节点的虚拟类 [英] Virtual classes as AST nodes with Spirit

问题描述

我正在与一位朋友一起为一种语言进行口译，我们从一个决定开始，我猜那不是那么明智：我们首先确定所有要执行的元素（实际上是一棵由不同类组成的树）；但是现在来看助推器示例，我对如何将两者合并感到非常困惑。我知道从（语法）开始，我知道要到达（相互拥有的实例化课程），我不知道如何到达。

我们从没有变量的表达式开始，因此我们看了精神计算器示例；但是我不知道何时实例化元素。

表达式项示例：

  namespace exp 
 {
 class op 
 {
 private：
 public：
 virtual double exec（function_scope& fs）; 
 
}; 
 
类操作数：public op 
 {
 private：
 double value; 
 
 public：
操作数（双值）； 
 double exec（function_scope& fs）; 
}; 
 
 class op_bin：公共操作
 {
私人：
公共：
 op * ll; 
 op * rr; 
 op_bin（op * ll，op * rr）; 
〜op_bin（）; 
}; 
 
名称空间bin 
 {
类总和：public op_bin 
 {
 public：
 sum（op * ll，op * rr）; 
 double exec（function_scope& fs）; 
}; 
} 
} 
  

忽略exec函数，它在运行时使用。 / p>

例如，代码5 +（2 + 1）的最终结果应为：

  new exp :: bin :: sum（new exp :: operand（5），new exp :: bin :: sum（new exp :: operand（2），new exp :: operand（1 ））
  

一旦我了解了我实际上已完成的操作。

解决方案

好吧，我打算写出您的问题出了什么问题，但是我去证明自己，做出想要的事情并不难。

几个关键点：

• 我稍加修改，重命名并扩展了ast使其发挥作用并实际显示某些东西。


• Spirit规则出于某种原因制作了属性的副本（我认为这是一个错误），因此我针对 unique_ptr 具有特征。（在1.70中修复）


• 我不确定 x3是否： ：忽略实际上是必需的（您可以删除除最后一个以外的所有内容，它将进行编译），但这似乎是Spirit中的另一个错误。


• make_node 看起来不可靠，并且可能以令人惊讶的方式破坏，您可以根据需要将其拆分为单独的一元/二进制节点创建者。


• 有时，您将希望为您的ast节点创建使用状态分配器，将分配器注入解析器上下文中应该非常简单。我将它留给您作为练习。

解析器：

  #include< boost / spirit / home / x3.hpp> 
 #include< memory> 
 #include< iostream> 
 
命名空间ast 
 {
 
类表达式
 {受保护的
：
 expression（）=默认值； 
 public：
 virtual〜expression（）=默认值； 
 expression（expression&& other）=删除; 
表达式和运算符=（表达式&其他）=删除; 
 
虚拟无效打印（std :: ostream&）const = 0; 
 
朋友std :: ostream&运算符<（std :: ostream& os，表达式const&节点）
 {
 node.print（os）; 
 return os; 
} 
}; 
 
类操作数：公共表达式
 {
 double value_; 
 
 public：
 constexpr操作数（双值）：value_ {value} {} 
 void print（std :: ostream& os）const替代{os<<值_; } 
}; 
 
 class op_bin：公共表达式
 {受保护的
：
 std :: unique_ptr< expression>左右_; 
 
 public：
 op_bin（std :: unique_ptr< expression>左，std :: unique_ptr< expression>右）
：left_ {std :: move（left）}， right_ {std :: move（right）} 
 {} 
 
 op_bin（expression * left，expression * right）
：left_ {left}，right_ {right} 
 {} 
}; 
 
 class plus：public op_bin 
 {
 public：
使用op_bin :: op_bin; 
 void print（std :: ostream& os）const覆盖
 {os<< ’（’<< * left_<< +<< * right_<<’））; } 
}; 
 
类减去：public op_bin 
 {
 public：
使用op_bin :: op_bin; 
 void print（std :: ostream& os）const覆盖
 {os<< ’（’<< * left_<<--<< * right_<<’））； } 
}; 
 
 class mul：public op_bin 
 {
 public：
 using op_bin :: op_bin; 
 void print（std :: ostream& os）const覆盖
 {os<< ’（’<< * left_<< *<< * right_<<’））; } 
}; 
 
 class div：公共op_bin 
 {
 public：
使用op_bin :: op_bin; 
 void print（std :: ostream& os）const覆盖
 {os<< ’（’<< * left_<< /<< * right_<<’））; } 
}; 
 
} //命名空间ast 
 
命名空间语法
 {
 
命名空间x3 = boost :: spirit :: x3; 
 
模板< typename T> 
 struct make_node_ 
 {
 template< typename Context> 
 void operator（）（上下文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）））; 
} 
} 
}; 
 
模板< typename T> 
 constexpr make_node_< T> make_node {}; 
 
使用x3 :: double_; 
使用x3 :: char_; 
 
 x3 :: rule< class expression_r，std :: unique_ptr< ast :: expression> ;, true> const表达式
 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>]] 
 | ’（’>表达式>’）’
； 
 
 BOOST_SPIRIT_DEFINE（
表达式
，prec1 
，prec0 
）; 
 
} //名称空间语法
 
 #if BOOST_VERSION< 107000 
名称空间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>&类型; 
 typedef std :: unique_ptr< Attribute>&值类型; 
}; 
 
} //命名空间boost :: spirit :: x3 :: traits 
 #endif 
 
 int main（）
 {
命名空间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< < 解析失败； 
} 
 else {
 if（iter！= s.cend（））
 std :: cout<< 部分解析； 
 std :: cout<< * expr<< ‘n’; 
} 
} 
  

输出：

 （1 +（（2 *（3-4））/ 5））
  

i was working on an interpreter for a language with a friend, and we started with a decision I'm guessing wasn't that wise: we made all the elements for execution first (practically a tree made of different classes); but now looking at boost examples i get a lot confused about how to merge the two. I know what to start from (the grammar), i know what to reach (instantiated classes owning each other), i don't know how to reach it.

We started with expressions without variables, hence we looked at spirit calculator examples; but i don't understand when to instantiate elements.

Example of expression items:

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);
        };
    }
}

Ignore the exec function, it's used at runtime.

For example the code 5 + (2 + 1) should result in a final equivalent of:

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

Once i understand how to do that I've practically done.

解决方案

Well, I was going to write what's wrong with your question, but instead I went to prove myself that it is not that hard to make what you want.

Few keypoints:

• I slightly modified, renamed and extended your ast to make it work and to actually show something.
• Spirit rules for some reason make copy of an attribute (I think it is a bug), so I workarounded this issue for unique_ptr with a trait. (fixed in 1.70)
• I am not sure if x3::omit is actually required there (you can remove all except the last and it will compile), but it looks like it is an another bug in Spirit.
• make_node looks unreliable and may broke in surprising ways, you can split it into separate unary/binary node creators if you wish.
• At some point you will want to use stateful allocator for your ast nodes creation, it should be very simple by injecting allocator into the parser context. I am leaving it for you as an exercise.

The 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';
    }
}

Output:

(1 + ((2 * (3 - 4)) / 5))

这篇关于用Spirit作为AST节点的虚拟类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！