小贝子编程

解析字符串以创建几何图形



开发用于创建几何图形的字符串解析器的算法是什么?几何图形的生成分为两个步骤:第一步，我们创建原语;第二步，我们将原语组合成对象。

语法如下所示。

string str="[GEOMETRY]    
PRIMITIVE1=SPHERE(RADIUS=5.5);  
PRIMITIVE2=BOX(A=-5.2, B=7.3);  
//...  
OBJECT1=PRIMITIVE2*(-PRIMITIVE1);  
//..."
class PRIMITIVE{
int number;
public:
Primitive& operator+ (Primitive& primitive) {}; //overloading arithmetic operations
Primitive& operator* (Primitive& primitive) {};
Primitive& operator- (Primitive& primitive) {};
virtual bool check_in_point_inside_primitive = 0;
};
class SPHERE:public PRIMITIVE{
double m_radius;
public:
SPHERE(double radius): m_radius(radius) {};  //In which part of the parser to create objects?
bool check_in_point_inside_sphere(Point& point){};
};
class BOX:public PRIMITIVE{
double m_A;
double m_B;
public:
BOX(double A, double B): m_A(A), m_B(B) {};
bool check_in_point_inside_box(Point& point){};
};
class OBJECT{
int number;
PRIMITIVE& primitive;
public:
OBJECT(){};
bool check_in_point_inside_object(Primitive& PRIMITIVE1, Primitive& PRIMITIVE2, Point& point){
//>How to construct a function from an expression 'PRIMITIVE2*(-PRIMITIVE1)' when parsing?
}
};

  1. 如何分析字符串PRIMITIVE1=SPHERE(RADIUS=5.5)并将参数传递给SPHERE()的构造函数?如何用PRIMITIVE 1这个名字来识别这个对象，以便在OBJECT中调用它?是否可以创建一个pair<PRIMITIVE1,SPHERE(5.5)>并在map中存储所有原语?

  2. 如何解析OBJECT1的字符串，并从表达式PRIMITIVE2*(-PRIMITIVE1)在OBJECT1内构建一个函数?在确定每个点相对于对象的位置时，将多次使用此表达式。

  3. 如何使用boost::spirit完成此任务?使用boost::spirit::lex标记字符串，然后使用boost::spirit::qi开发规则?

作为一个手指练习，尽管我看到所选择的虚拟类型层次结构存在严重的问题，让我们尝试创建一个面向值的基元容器，可以通过它们的id (ById)进行索引:

Live On Coliru 

#include <boost/intrusive/set.hpp>
#include <boost/poly_collection/base_collection.hpp>
#include <iostream>
namespace bi = boost::intrusive;
struct Point {
};
using IndexHook = bi::set_member_hook<bi::link_mode<bi::auto_unlink>>;
class Primitive {
int _id;
public:
struct ById {
bool operator()(auto const&... oper) const { return std::less<>{}(access(oper)...); }
private:
static int access(int id) { return id; }
static int access(Primitive const& p) { return p._id; }
};
IndexHook _index;
Primitive(int id) : _id(id) {}
virtual ~Primitive() = default;
int id() const { return _id; }
Primitive& operator+= (Primitive const& primitive) { return *this; } //overloading arithmetic operations
Primitive& operator*= (Primitive const& primitive) { return *this; }
Primitive& operator-= (Primitive const& primitive) { return *this; }
virtual bool check_in_point_inside(Point const&) const = 0;
};
using Index =
bi::set<Primitive, bi::constant_time_size<false>,
bi::compare<Primitive::ById>,
bi::member_hook<Primitive, IndexHook, &Primitive::_index>>;
class Sphere : public Primitive {
double _radius;
public:
Sphere(int id, double radius)
: Primitive(id)
, _radius(radius) {} // In which part of the parser to create objects?
bool check_in_point_inside(Point const& point) const override { return false; }
};
class Box : public Primitive {
double _A;
double _B;
public:
Box(int id, double A, double B) : Primitive(id), _A(A), _B(B) {}
bool check_in_point_inside(Point const& point) const override { return false; }
};
class Object{
int _id;
Primitive& _primitive;
public:
Object(int id, Primitive& p) : _id(id), _primitive(p) {}
bool check_in_point_inside_object(Primitive const& p1, Primitive const& p2,
Point const& point) const
{
//>How to construct a function from an expression
//'PRIMITIVE2*(-PRIMITIVE1)' when parsing?
return false;
}
};
using Primitives = boost::poly_collection::base_collection<Primitive>;
int main() {
Primitives test;
test.insert(Sphere{2, 4.0});
test.insert(Sphere{4, 4.0});
test.insert(Box{2, 5, 6});
test.insert(Sphere{1, 4.0});
test.insert(Box{3, 5, 6});
Index idx;
for (auto& p : test)
if (not idx.insert(p).second)
std::cout << "Duplicate id " << p.id() << " not indexedn";
for (auto& p : idx)
std::cout << typeid(p).name() << " " << p.id() << "n";
std::cout << "---n";
for (auto& p : test)
std::cout << typeid(p).name() << " " << p.id() << "n";
}

打印

Duplicate id 2 not indexed
6Sphere 1
3Box 2
3Box 3
6Sphere 4
---
3Box 2
3Box 3
6Sphere 2
6Sphere 4
6Sphere 1

到目前为止一切顺利。这是一个重要的构建块，可以在处理Spirit语法中的虚拟类型时防止各种痛苦¹

PS:我已经放弃了intrusive_set的想法。它不起作用，因为base_container会在重新分配时移动项，这会将项与它们的侵入集断开链接。

相反，请参见下面的方法，该方法在解析过程中不尝试解析id。

解析原语

我们从PRIMITIVE1中获得ID。我们可以在自然解析原语本身之前将其存储在某个地方，然后在提交时设置其id。

让我们从为解析器定义State对象开始:

struct State {
Ast::Id         next_id;
Ast::Primitives primitives;
Ast::Objects    objects;
template <typename... T> void commit(boost::variant<T...>& val) {
boost::apply_visitor([this](auto& obj) { commit(obj); }, val);
}
template <typename T> void commit(T& primitiveOrExpr) {
auto id = std::exchange(next_id, 0);
if constexpr (std::is_base_of_v<Ast::Primitive, T>) {
primitiveOrExpr.id = id;
primitives.insert(std::move(primitiveOrExpr));
} else {
objects.push_back(Ast::Object{id, std::move(primitiveOrExpr)});
}
}
};

如您所见，我们只有一个地方来存储原语，对象。然后是next_id的临时存储，当我们还在解析下一个实体时。

commit函数帮助对解析器规则的产品进行排序。碰巧的是，它们可以是变量，这就是为什么我们在一个变量上有apply_visitor对commit的调度。

同样，正如脚注¹解释的那样，Spirit的自然属性合成倾向于静态多态性。

我们现在需要的语义动作是:

static inline auto& state(auto& ctx) { return get<State>(ctx); }
auto draft = [](auto& ctx) { state(ctx).next_id = _attr(ctx); };
auto commit = [](auto& ctx) { state(ctx).commit(_attr(ctx)); };

现在让我们跳到原语:

auto sphere = as<Ast::Sphere>(eps >> "sphere" >>'(' >> param("radius") >> ')');
auto box    = as<Ast::Box>(eps >> "box" >> '(' >> param('a') >> ',' >> param('b') >> ')');
auto primitive =
("primitive" >> uint_[draft] >> '=' >> (sphere | box)[commit]) > ';';

这仍然有点作弊，因为我使用了param帮助器来减少输入:

auto number = as<Ast::Number>(double_, "number");
auto param(auto name, auto p) { return eps >> omit[name] >> '=' >> p; }
auto param(auto name) { return param(name, number); }

正如你所看到的，我已经假设了大多数参数将具有数值性质。

对象到底是什么?

看了一会儿，我得出结论，一个对象实际上被定义为一个id号(OBJECT1, OBJECT2…)，它与一个表达式相关联。该表达式可以引用原语，并具有一些一元和二元操作符。

让我们画一个AST:

using Number = double;
struct RefPrimitive { Id id; };
struct Binary;
struct Unary;
using Expr = boost::variant<         //
Number,                          //
RefPrimitive,                    //
boost::recursive_wrapper<Unary>, //
boost::recursive_wrapper<Binary> //
>;
struct Unary { char op; Expr oper; };
struct Binary { Expr lhs; char op; Expr rhs; };
struct Object { Id   id; Expr expr; };

现在解析为表达式AST

对于每个Ast节点类型都是1:1的规则。例如:

auto ref_prim = as<Ast::RefPrimitive>(lexeme["primitive" >> uint_]);

现在许多表达式规则都可以递归，所以我们需要通过BOOstrongPIRIT_DEFINE:

定义声明规则
// object expression grammar
rule<struct simple_tag, Ast::Expr>  simple{"simple"};
rule<struct unary_tag,  Ast::Unary> unary{"unary"};
rule<struct expr_tag,   Ast::Expr>  expr{"expr"};
rule<struct term_tag,   Ast::Expr>  term{"term"};
rule<struct factor_tag, Ast::Expr>  factor{"factor"};

可以看出，其中一些与Ast节点不是1:1的，主要是因为递归和操作符优先级的差异(termvsfactorvssimple)。使用规则定义更容易看到:

auto unary_def  = char_("-+") >> simple;
auto simple_def = ref_prim | unary | '(' >> expr >> ")";
auto factor_def = simple;
auto term_def   = factor[assign] >> *(char_("*/") >> term)[make_binary];
auto expr_def   = term[assign] >> *(char_("-+") >> expr)[make_binary];

因为没有任何规则实际上公开Binary，所以自动属性传播在那里不方便²。相反，我们使用assign和make_binary语义动作:

auto assign = [](auto& ctx) { _val(ctx) = _attr(ctx); };
auto make_binary = [](auto& ctx) {
using boost::fusion::at_c;
auto& attr = _attr(ctx);
auto  op   = at_c<0>(attr);
auto& rhs  = at_c<1>(attr);
_val(ctx)  = Ast::Binary { _val(ctx), op, rhs };
};

最后，让我们将定义绑定到声明的规则(使用它们的标记类型):

BOOST_SPIRIT_DEFINE(simple, unary, expr, term, factor)

我们所需要的是一个类似primitive:

的行
auto object =
("object" >> uint_[draft] >> '=' >> (expr)[commit]) > ';';

最后，我们可以将每行定义为一个原语|object:

auto line = primitive | object;
auto file = no_case[skip(ws_comment)[*eol >> "[geometry]" >> (-line % eol) >> eoi]];

在顶层，我们期望[GEOMETRY]头，指定我们想要不区分大小写和…ws_comment将被跳过³:

auto ws_comment = +(blank | lexeme["//" >> *(char_ - eol) >> eol]);

这也允许我们忽略// comments。

实时演示时间

Live On Compiler Explorer

//#define BOOST_SPIRIT_X3_DEBUG
#include <boost/fusion/adapted.hpp>
#include <boost/poly_collection/base_collection.hpp>
#include <boost/spirit/home/x3.hpp>
#include <iostream>
#include <list>
#include <map>
namespace x3 = boost::spirit::x3;
namespace Ast {
using Id     = uint32_t;
struct Point { }; // ?? where does this belong?
struct Primitive {
Id id;
virtual ~Primitive() = default;
};
struct Sphere : Primitive { double radius; };
struct Box : Primitive { double a, b; };
using Number = double;
struct RefPrimitive { Id id; };
struct Binary;
struct Unary;
using Expr = boost::variant<         //
Number,                          //
RefPrimitive,                    //
boost::recursive_wrapper<Unary>, //
boost::recursive_wrapper<Binary> //
>;
struct Unary { char op; Expr oper; };
struct Binary { Expr lhs; char op; Expr rhs; };
struct Object { Id   id; Expr expr; };
using Primitives = boost::poly_collection::base_collection<Primitive>;
using Objects    = std::list<Object>;
using Index      = std::map<Id, std::reference_wrapper<Primitive const>>;
std::ostream& operator<<(std::ostream& os, Primitive const& p) {
return os << boost::core::demangle(typeid(p).name()) << " "
<< "(id: " << p.id << ")";
}
std::ostream& operator<<(std::ostream& os, Object const& o) {
return os << "object(id:" << o.id << ", expr:" << o.expr << ")";
}
std::ostream& operator<<(std::ostream& os, RefPrimitive ref) {
return os << "reference(prim:" << ref.id << ")";
}
std::ostream& operator<<(std::ostream& os, Binary const& b) {
return os << '(' << b.lhs << b.op << b.rhs << ')';
}
std::ostream& operator<<(std::ostream& os, Unary const& u) {
return os << '(' << u.op << u.oper << ')';
}
} // namespace Ast
BOOST_FUSION_ADAPT_STRUCT(Ast::Primitive, id)
BOOST_FUSION_ADAPT_STRUCT(Ast::Sphere, radius)
BOOST_FUSION_ADAPT_STRUCT(Ast::Box, a, b)
BOOST_FUSION_ADAPT_STRUCT(Ast::Object, id)
BOOST_FUSION_ADAPT_STRUCT(Ast::RefPrimitive, id)
BOOST_FUSION_ADAPT_STRUCT(Ast::Unary, op, oper)
namespace Parser {
using namespace x3;
struct State {
Ast::Id         next_id;
Ast::Primitives primitives;
Ast::Objects    objects;
template <typename... T> void commit(boost::variant<T...>& val) {
boost::apply_visitor([this](auto& obj) { commit(obj); }, val);
}
template <typename T> void commit(T& val) {
auto id = std::exchange(next_id, 0);
if constexpr (std::is_base_of_v<Ast::Primitive, T>) {
val.id = id;
primitives.insert(std::move(val));
} else {
objects.push_back(Ast::Object{id, std::move(val)});
}
}
};
static inline auto& state(auto& ctx) { return get<State>(ctx); }
auto draft = [](auto& ctx) { state(ctx).next_id = _attr(ctx); };
auto commit = [](auto& ctx) { state(ctx).commit(_attr(ctx)); };
template <typename T>
auto as = [](auto p, char const* name = "as") {
return rule<struct _, T>{name} = p;
};
auto ws_comment = +(blank | lexeme["//" >> *(char_ - eol) >> (eol | eoi)]);
auto number = as<Ast::Number>(double_, "number");
auto param(auto name, auto p) { return eps >> omit[name] >> '=' >> p; }
auto param(auto name) { return param(name, number); }
auto sphere = as<Ast::Sphere>(eps >> "sphere" >>'(' >> param("radius") >> ')');
auto box    = as<Ast::Box>(eps >> "box" >> '(' >> param('a') >> ',' >> param('b') >> ')');
auto primitive =
("primitive" >> uint_[draft] >> '=' >> (sphere | box)[commit]) > ';';

auto ref_prim = as<Ast::RefPrimitive>(lexeme["primitive" >> uint_], "ref_prim");
// object expression grammar
rule<struct simple_tag, Ast::Expr>  simple{"simple"};
rule<struct unary_tag,  Ast::Unary> unary{"unary"};
rule<struct expr_tag,   Ast::Expr>  expr{"expr"};
rule<struct term_tag,   Ast::Expr>  term{"term"};
rule<struct factor_tag, Ast::Expr>  factor{"factor"};
auto assign = [](auto& ctx) { _val(ctx) = _attr(ctx); };
auto make_binary = [](auto& ctx) {
using boost::fusion::at_c;
auto& attr = _attr(ctx);
auto  op   = at_c<0>(attr);
auto& rhs  = at_c<1>(attr);
_val(ctx)  = Ast::Binary { _val(ctx), op, rhs };
};
auto unary_def  = char_("-+") >> simple;
auto simple_def = ref_prim | unary | '(' >> expr >> ")";
auto factor_def = simple;
auto term_def   = factor[assign] >> *(char_("*/") >> term)[make_binary];
auto expr_def   = term[assign] >> *(char_("-+") >> expr)[make_binary];
BOOST_SPIRIT_DEFINE(simple, unary, expr, term, factor)
auto object =
("object" >> uint_[draft] >> '=' >> (expr)[commit]) > ';';
auto line = primitive | object;
auto file = no_case[skip(ws_comment)[*eol >> "[geometry]" >> (-line % eol) >> eoi]];
} // namespace Parser
int main() {
for (std::string const input :
{
R"(
[geometry]    
primitive1=sphere(radius=5.5);  
primitive2=box(a=-5.2, b=7.3);  
//...  
object1=primitive2*(-primitive1);  
//...)",
R"(
[GEOMETRY]    
PRIMITIVE1=SPHERE(RADIUS=5.5);  
PRIMITIVE2=BOX(A=-5.2, B=7.3);  
//...  
OBJECT1=PRIMITIVE2*(-PRIMITIVE1);  
//...)",
}) //
{
Parser::State state;
bool ok = parse(begin(input), end(input),
x3::with<Parser::State>(state)[Parser::file]);
std::cout << "Parse success? " << std::boolalpha << ok << "n";
Ast::Index index;
for (auto& p : state.primitives)
if (auto[it,ok] = index.emplace(p.id, p); not ok) {
std::cout << "Duplicate id " << p
<< " (conflicts with existing " << it->second.get()
<< ")n";
}
std::cout << "Primitives by ID:n";
for (auto& [id, prim] : index)
std::cout << " - " << prim << "n";
std::cout << "Objects in definition order:n";
for (auto& obj: state.objects)
std::cout << " - " << obj << "n";
}
}

打印

Parse success? true
Primitives by ID:
- Ast::Sphere (id: 1)
- Ast::Box (id: 2)
Objects in definition order:
- object(id:1, expr:(reference(prim:2)*(-reference(prim:1))))
Parse success? true
Primitives by ID:
- Ast::Sphere (id: 1)
- Ast::Box (id: 2)
Objects in definition order:
- object(id:1, expr:(reference(prim:2)*(-reference(prim:1))))

我如何使用多态属性与boost::spirit::qi解析器?

²并坚持它会导致经典的低效规则，导致大量的回溯

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium