最近，我在sehe的帮助下，成功地为hlsl（高级着色语言）改进了我的boost spirit x3解析器，hlsl是一种类似c的语言，用于为GPU编写着色器内核。下面是我遵循的粗略语法... https://craftinginterpreters.com/appendix-i.html
下面是前面的问题和答案为好奇。
Trying to parse nested expressions with boost spirit x3
我现在正在尝试实现一元和二元运算符，但遇到了它们如何递归的障碍。我能够让它编译并解析单个二元运算符，但是有多个嵌套对象似乎不起作用。我怀疑解决方案将再次涉及语义操作，以手动传播值，但我很难看到如何做到这一点，因为副作用很难理解（仍在研究这一切是如何工作的）。
下面是我的编译示例...
#include <boost/fusion/adapted.hpp>
#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/home/x3/support/ast/variant.hpp>
#include <boost/spirit/home/x3/support/utility/error_reporting.hpp>
#include <iomanip>
#include <iostream>
namespace x3 = boost::spirit::x3;
namespace hlsl
{
namespace ast
{
struct Void
{
};
struct Get;
struct Set;
struct Call;
struct Assign;
struct Binary;
struct Unary;
struct Variable
{
std::string name;
};
using Expr = x3::variant<Void, x3::forward_ast<Get>, x3::forward_ast<Set>, Variable, x3::forward_ast<Call>, x3::forward_ast<Assign>, x3::forward_ast<Binary>, x3::forward_ast<Unary>>;
struct Call
{
Expr name;
std::vector<Expr> arguments_;
};
struct Get
{
Expr object_;
std::string property_;
};
struct Set
{
Expr object_;
Expr value_;
std::string name_;
};
struct Assign
{
std::string name_;
Expr value_;
};
struct Binary
{
Expr left_;
std::string op_;
Expr right_;
};
struct Unary
{
std::string op_;
Expr expr_;
};
} // namespace ast
struct printer
{
std::ostream &_os;
using result_type = void;
void operator()(hlsl::ast::Get const &get) const
{
_os << "get { object_:";
get.object_.apply_visitor(*this);
_os << ", property_:" << quoted(get.property_) << " }";
}
void operator()(hlsl::ast::Set const &set) const
{
_os << "set { object_:";
set.object_.apply_visitor(*this);
_os << ", name_:" << quoted(set.name_);
_os << " equals: ";
set.value_.apply_visitor(*this);
_os << " }";
}
void operator()(hlsl::ast::Assign const &assign) const
{
_os << "assign { ";
_os << "name_:" << quoted(assign.name_);
_os << ", value_:";
assign.value_.apply_visitor(*this);
_os << " }";
}
void operator()(hlsl::ast::Variable const &var) const
{
_os << "var{" << quoted(var.name) << "}";
};
void operator()(hlsl::ast::Binary const &bin) const
{
_os << "binary { ";
bin.left_.apply_visitor(*this);
_os << " " << quoted(bin.op_) << " ";
bin.right_.apply_visitor(*this);
_os << " }";
};
void operator()(hlsl::ast::Unary const &un) const
{
_os << "unary { ";
un.expr_.apply_visitor(*this);
_os << quoted(un.op_);
_os << " }";
};
void operator()(hlsl::ast::Call const &call) const
{
_os << "call{";
call.name.apply_visitor(*this);
_os << ", args: ";
for (auto &arg : call.arguments_)
{
arg.apply_visitor(*this);
_os << ", ";
}
_os << /*quoted(call.name) << */ "}";
};
void operator()(hlsl::ast::Void const &) const { _os << "void{}"; };
};
} // namespace hlsl
BOOST_FUSION_ADAPT_STRUCT(hlsl::ast::Variable, name)
BOOST_FUSION_ADAPT_STRUCT(hlsl::ast::Call, name, arguments_)
BOOST_FUSION_ADAPT_STRUCT(hlsl::ast::Get, object_, property_)
BOOST_FUSION_ADAPT_STRUCT(hlsl::ast::Set, object_, value_)
BOOST_FUSION_ADAPT_STRUCT(hlsl::ast::Assign, name_, value_)
BOOST_FUSION_ADAPT_STRUCT(hlsl::ast::Binary, left_, op_, right_)
BOOST_FUSION_ADAPT_STRUCT(hlsl::ast::Unary, op_, expr_)
namespace hlsl::parser
{
struct eh_tag;
struct error_handler
{
template <typename It, typename Exc, typename Ctx>
auto on_error(It &, It, Exc const &x, Ctx const &context) const
{
x3::get<eh_tag>(context)( //
x.where(), "Error! Expecting: " + x.which() + " here:");
return x3::error_handler_result::fail;
}
};
struct program_ : error_handler
{
};
x3::rule<struct identifier_, std::string> const identifier{"identifier"};
x3::rule<struct variable_, ast::Variable> const variable{"variable"};
x3::rule<struct arguments_, std::vector<ast::Expr>> const arguments{"arguments_"};
x3::rule<struct binary_, hlsl::ast::Binary, true> const binary{"binary"};
x3::rule<struct unary_, hlsl::ast::Unary> const unary{"unary"};
x3::rule<struct unarycallwrapper_, hlsl::ast::Expr> const unarycallwrapper{"unarycallwrapper"};
x3::rule<struct get_, ast::Expr> const get{"get"};
x3::rule<struct call_, ast::Expr> const call{"call"};
x3::rule<struct program_, ast::Expr> const program{"program"};
x3::rule<struct primary_, ast::Expr> const primary{"primary"};
x3::rule<struct expression_, ast::Expr> const expression{"expression"};
x3::rule<struct set_, ast::Set, true> const set{"set"};
x3::rule<struct assign_, ast::Assign> const assign{"assign"};
x3::rule<struct assignment_, ast::Expr> const assignment{"assignment"};
auto get_string_from_variable = [](auto &ctx)
{ _val(ctx).name_ = std::move(_attr(ctx).name); };
auto fix_assignExpr = [](auto &ctx)
{ _val(ctx).value_ = std::move(_attr(ctx)); };
auto as_expr = [](auto &ctx)
{ _val(ctx) = ast::Expr(std::move(_attr(ctx))); };
auto as_unary = [](auto &ctx)
{ _val(ctx) = ast::Unary(std::move(_attr(ctx))); };
auto as_call = [](auto &ctx)
{ _val(ctx) = ast::Call{std::move(_val(ctx)), std::move(_attr(ctx))}; };
auto fold_in_get_to_set = [](auto &ctx)
{
auto &val = x3::_val(ctx);
val.name_ = boost::get<x3::forward_ast<ast::Get>>(val.object_).get().property_;
val.object_ = ast::Expr(boost::get<x3::forward_ast<ast::Get>>(val.object_).get().object_);
};
auto as_string = [](auto &ctx)
{ _val(ctx) = std::move(_attr(ctx).name); };
auto as_assign = [](auto &ctx)
{ _val(ctx) = ast::Assign(std::move(_val(ctx)), std::move(_attr(ctx))); };
auto as_get = [](auto &ctx)
{
_val(ctx) = ast::Get{std::move(_val(ctx)), _attr(ctx)};
};
auto variable_def = identifier;
auto primary_def = variable;
auto identifier_def = x3::lexeme[x3::alpha >> *x3::alnum];
auto expression_def = assignment;
auto assignment_def = (assign | set) | binary; // replace binary with call to see the rest working
auto assign_def = variable[get_string_from_variable] >> '=' >> assignment[fix_assignExpr];
auto set_def = (get >> '=' >> assignment)[fold_in_get_to_set];
auto arguments_def = *(expression % ',');
auto get_def = primary[as_expr] >> *('.' >> identifier)[as_get];
auto call_def = primary[as_expr] >> *((x3::lit('(') >> arguments >> x3::lit(')'))[as_call] | ('.' >> identifier)[as_get]);
auto unary_def = (x3::string("-") >> unary);
auto unarycallwrapper_def = unary | call ;
auto binary_def = unarycallwrapper >> x3::string("*") >> unarycallwrapper;
auto program_def = x3::skip(x3::space)[expression];
BOOST_SPIRIT_DEFINE(primary, assign, binary, unary, unarycallwrapper, assignment, get, set, variable, arguments, expression, call, identifier, program);
} // namespace hlsl::parser
int main()
{
using namespace hlsl;
for (std::string const input :
{
"first",
"first.second",
"first.Second.third",
"first.Second().third",
"first.Second(arg1).third",
"first.Second(arg1, arg2).third",
"first = second",
"first.second = third",
"first.second.third = fourth",
"first.second.third = fourth()",
"first.second.third = fourth(arg1)",
"this * that", //binary { var{"this"} "*" var{"that"} }
"this * -that", // binary { var{"this"} "*" unary{'-', var{"that"}} }
"this * that * there",
}) //
{
std::cout << "===== " << quoted(input) << "\n";
auto f = input.begin(), l = input.end();
// Our error handler
auto const p = x3::with<parser::eh_tag>(
x3::error_handler{f, l, std::cerr})[hlsl::parser::program];
if (hlsl::ast::Expr fs; parse(f, l, p, fs))
{
fs.apply_visitor(hlsl::printer{std::cout << "Parsed: "});
std::cout << "\n";
}
else
{
std::cout << "Parse failed at " << quoted(std::string(f, l)) << "\n";
}
}
}任何帮助都是非常感谢的：）
4条答案
按热度按时间b09cbbtk1#
下面是我解决这个问题的方法。
我没有使用单个二进制ast节点来存储""或"/"字符串，而是将其拆分为单独的ast节点类型，用于除法和乘法。
然后，我使用了@sehe在关联答案中建议的相同机制来合成正确的节点。
我仍然不确定如何使用语义操作来合成跨越多个'〉〉'操作符的属性。我猜语义操作中的
_val(ctx)是指当前定义的规则中的整个ast：：Expr，所以也许您可以设置ast：：Binary的一个成员（例如x3：：string（""）中的op字符串），然后在'〉〉'之后的下一个术语中再次写入_val(ctx)（从上一个中复制构造？），并设置_attr(ctx)中的下一个成员？我会看看我是否可以研究下一个操作是否有效。这将允许一些更复杂的属性合成。尽管我不确定您是否可以在规则中设置不同的类型。yb3bgrhw2#
我还弄清楚了语义操作如何跨多个序列'〉〉'操作符写入_瓦尔（ctx）。您可以用您需要的类型写入它们，然后它将被传递给下一个操作符！
查看binary 2规则以及它的def如何使用两个语义操作来编写Binary 2 ast节点并每次设置不同的成员。
6ie5vjzr3#
还有一个帖子......
我几乎完成了hlsl使用的所有表达式运算符（按位、逻辑、复合赋值等）。
我甚至想出了嵌套的三元运算符，我认为这将是非常困难的，但没有变成太坏。
93ze6v8z4#
You found out how to jump hoops already :)
To lend some perspective I started from scratch. I copied the specs as a markdown comment. I basically copy pasted stuff and mapped an AST 1:1:
Notes:
Blockcontent to be statements instead of declarations. It's unlikely that the script should really allow local class declarations. Allowing it means effectively theDeclarationandStatementvariant have to merge.Adapting as Fusion sequences:
Next up we declare rules for anything that is gonna recurse:
Sadly, due to the operator precedence levels being split up in separate grammar productions, we get a proliferation of these rules:
The lexicals are simple enough:
I see I forgot to introduce
AST(T, p)macro in time. See below.Constructing the decimal number from string is fine:
Keyword Checking
As an advanced feature I added keyword checking. You will find out you need it when you have a function name starting with a keyword, e.g.
for_eachwould misparseforas the keyword, unless we check that it is not immediately followed by "identifier" characters. Let's also make this a configuration point for case sensitivity:Now we can use
kw("for")instead of"for"and it will be properly case sensitive and boundary-checked.Reserved keywords
The specs don't say, but you may want to avoid creating variables with reserved names. E.g.
(return)("key").indexwould be an expression that invokes a function namedreturn, butreturn ("key")would be a statement that returns the expression"key"(wrapped in a redundant subexpression).So, let's add some logic to distinguish non-reserved identifiers:
AST Building
I think I mentioned the
at<T>(p)device before.Making it less verbose with Ast:: types:
Now the utility productions from the grammar can be written as:
Declarations
Not a lot to be said, except note the embedding of the skipper. For fun and exposition, I've customized the skipper to allow C++ style comments:
Statements
It's a bit of tedium, but the Fusion adaptations and previously introduced
kw(...)andAST(T, p)helpers do all the heavy lifting:Note how these are basically carbon copies of the specs.
Expressions
Here is the part that gave trouble.
First let's get the simple things out of way:
Note here that we conditionally apply the
kw()modification on the operator symbol if the input token looks like alphanumeric. That, again, is to preventandaluciaororlandofrom misparsing as the logical operators.The condition
&identifieris a bit sloppy, but it saves us from separating the interpunction operators from the named ones. Your profiler will tell you which is better.Note that I pruned
"this"and"super"from the list as they are just like other variables. If you opt to make them reserved, you will need to special-case them here, e.g.Smooth Operators
You already noticed the way using semantic actions. I separate out a few semantic action helpers:
With these you can do the simples:
Then the bulk would become e.g.:
To avoid the duplication let's make a rule factory:
The
expect_opfactory handles multiple acceptable operators, and applies proper token boundary checking again:Now all the binaries (except the top level
assignment, which has special associativity and lhs productions) become:Tieing it all together:
Testing
Live On Coliru Printing
Locally, interactively:
Full Listing (anti-bitrot)
Sadly [SO] refuses it for length limits. I'll post it on Github. Link coming.
TL;DR
I think the
at_c<N>accessor trick to dissect Fusion sequences in semantic action will help a lot.Also, keep in mind that I don't think this rule structure is good for performant parsers. Just look at how something simple like
x = y + (2);will invoke 43 rules (!!!) nested to 32 levels deep (!!!).That's... not ideal. I've made a fully C++-compatible expression grammar (complete with interpreter) on SO before, and you can witness it here: https://github.com/sehe/qi-extended-parser-evaluator . It's using Spirit Qi, but in spirit it uses an almost X3 approach. I might make an X3 version of it just to compare for myself.
The key difference is that it generically implements operators with some metadata to describe it (token, precedence, associativity). This information is then used to combine expression AST nodes correctly. It even allows to get rid of redundant parentheses, both when building the Ast and when printing.
The interpreter logic (with dynamic type system, some reflection and execution tracing) may be a nice bonus inspiration: https://github.com/sehe/qi-extended-parser-evaluator/blob/master/eval.h#L291