使用 boost spirit 的递归 BNF 规则
recursive BNF rule using boost spirit
我正在尝试使用 boost spirit 为以下 BNF 规则编写解析器
(Boost v1.64)
规则是：
<numeric-literal>::= integer
<type-name> ::= "in" | "out" | "in_out"
<array-type-spec> ::= <type-spec> "[" [<numeric-literal>] "]"
<tuple-type-spec> ::= "(" <type-spec> ("," <type-spec>)+ ")"
<type-spec> ::= <type-name> | <array-type-spec> | <tuple-type-spec>
下面是我的尝试，使用 boost::make_recursive_variant
它似乎在字符串 in
上工作正常
但它在 in[2].
上失败了
我的错误在哪里？
什么是优雅的解决方案？
namespace Ast {
enum class TypeName { IN, OUT, INOUT};
using NumericLiteral = int;
using TypeSpec = boost::make_recursive_variant
<
TypeName,
std::pair<boost::recursive_variant_, NumericLiteral>,
std::vector < boost::recursive_variant_ >
>::type;
}
//grammar:
namespace myGrammar {
namespace qi = boost::spirit::qi;
template <typename Iterator = char const*,typename Signature = Ast::TypeSpec()>
struct myRules : qi::grammar < Iterator, Signature> {
myRules() : myRules::base_type(start) {
fillSymbols();
rNumericLiteral = qi::int_;
rTypeName = sTypeName;
rTypeSpec = rTypeName | (rTypeSpec >> '[' >> rNumericLiteral >> ']') | ('(' >> qi::repeat(2, qi::inf)[(rTypeSpec % ',')] >> ')');
start = qi::skip(qi::space)[rTypeSpec];
}
private:
using Skipper = qi::space_type;
qi::rule<Iterator, Ast::TypeSpec()> start;
qi::rule<Iterator, Ast::NumericLiteral(), Skipper> rNumericLiteral;
qi::rule<Iterator, Ast::TypeName(), Skipper> rTypeName;
qi::rule<Iterator, Ast::TypeSpec(), Skipper> rTypeSpec;
//symbols
qi::symbols<char, Ast::TypeName>sTypeName;
void fillSymbols()
{
using namespace Ast;
sTypeName.add
("in", TypeName::IN)
("out", TypeName::OUT)
("in_out", TypeName::INOUT)
}
};
}
将此语法 1:1 转换为 PEG 语法时出现问题，因为左递归会导致无限递归。
您仍然可以轻松地重新排列规则，这样就不会发生左递归，但是在合成您想要的 AST 时会遇到更多麻烦。
这里有一个半途而废的测试结果：
//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
/*
<numeric-literal> ::= integer
<type-name> ::= "in" | "out" | "in_out"
<array-type-spec> ::= <type-spec> "[" [<numeric-literal>] "]"
<tuple-type-spec> ::= "(" <type-spec> ("," <type-spec>)+ ")"
<type-spec> ::= <type-name> | <array-type-spec> | <tuple-type-spec>
*/
namespace Ast {
enum class TypeName { IN, OUT, INOUT };
static inline std::ostream& operator<<(std::ostream& os, TypeName tn) {
switch(tn) {
case TypeName::IN: return os << "IN";
case TypeName::OUT: return os << "OUT";
case TypeName::INOUT: return os << "INOUT";
}
return os << "?";
}
using NumericLiteral = int;
using TypeSpec = boost::make_recursive_variant<
TypeName,
std::pair<boost::recursive_variant_, NumericLiteral>,
std::vector<boost::recursive_variant_>
>::type;
using ArraySpec = std::pair<TypeSpec, NumericLiteral>;
using TupleSpec = std::vector<TypeSpec>;
}
// grammar:
namespace myGrammar {
namespace qi = boost::spirit::qi;
template <typename Iterator = char const *, typename Signature = Ast::TypeSpec()>
struct myRules : qi::grammar<Iterator, Signature> {
myRules() : myRules::base_type(start) {
rNumericLiteral = qi::int_;
rTypeName = sTypeName >> !qi::alpha;
rTupleSpec = '(' >> rTypeSpec >> +(',' >> rTypeSpec) >> ')';
rScalarSpec = rTypeName | rTupleSpec;
rArraySpec = rScalarSpec >> '[' >> rNumericLiteral >> ']';
rTypeSpec = rArraySpec | rScalarSpec;
start = qi::skip(qi::space)[rTypeSpec >> qi::eoi];
BOOST_SPIRIT_DEBUG_NODES((start)(rTypeSpec)(rTypeName)(rArraySpec)(rScalarSpec)(rTypeSpec)(rNumericLiteral))
}
private:
using Skipper = qi::space_type;
qi::rule<Iterator, Ast::TypeSpec()> start;
qi::rule<Iterator, Ast::NumericLiteral(), Skipper> rNumericLiteral;
qi::rule<Iterator, Ast::ArraySpec(), Skipper> rArraySpec;
qi::rule<Iterator, Ast::TypeSpec(), Skipper> rTypeSpec, rScalarSpec;
qi::rule<Iterator, Ast::TupleSpec(), Skipper> rTupleSpec;
// implicit lexeme
qi::rule<Iterator, Ast::TypeName()> rTypeName;
// symbols
struct TypeName_r : qi::symbols<char, Ast::TypeName> {
TypeName_r() {
using Ast::TypeName;
add ("in", TypeName::IN)
("out", TypeName::OUT)
("in_out", TypeName::INOUT);
}
} sTypeName;
};
}
static inline std::ostream& operator<<(std::ostream& os, Ast::TypeSpec tn) {
struct {
std::ostream& _os;
void operator()(Ast::TypeSpec const& ts) const {
apply_visitor(*this, ts);
}
void operator()(Ast::TypeName tn) const { std::cout << tn; }
void operator()(Ast::TupleSpec const& tss) const {
std::cout << "(";
for (auto const& ts: tss) {
(*this)(ts);
std::cout << ", ";
}
std::cout << ")";
}
void operator()(Ast::ArraySpec const& as) const {
(*this)(as.first);
std::cout << '[' << as.second << ']';
}
} const dumper{os};
dumper(tn);
return os;
}
int main() {
using It = std::string::const_iterator;
myGrammar::myRules<It> const parser;
std::string const test_ok[] = {
"in",
"out",
"in_out",
"(in, out)",
"(out, in)",
"(in, in, in, out, in_out)",
"in[13]",
"in[0]",
"in[-2]",
"in[1][2][3]",
"in[3][3][3]",
"(in[3][3][3], out, in_out[0])",
"(in[3][3][3], out, in_out[0])",
"(in, out)[13]",
"(in, out)[13][0]",
};
std::string const test_fail[] = {
"",
"i n",
"inout",
"()",
"(in)",
"(out)",
"(in_out)",
"IN",
};
auto expect = [&](std::string const& sample, bool expected) {
It f = sample.begin(), l = sample.end();
Ast::TypeSpec spec;
bool ok = parse(f, l, parser, spec);
std::cout << "Test passed:" << std::boolalpha << (expected == ok) << "\n";
if (expected || (expected != ok)) {
if (ok) {
std::cout << "Parsed: " << spec << "\n";
} else {
std::cout << "Parse failed\n";
}
}
if (f!=l) {
std::cout << "Remaining unparsed: '" << std::string(f,l) << "'\n";
}
};
for (std::string const sample : test_ok) expect(sample, true);
for (std::string const sample : test_fail) expect(sample, false);
}
打印
Test passed:true
Parsed: IN
Test passed:true
Parsed: OUT
Test passed:true
Parsed: INOUT
Test passed:true
Parsed: (IN, OUT, )
Test passed:true
Parsed: (OUT, IN, )
Test passed:true
Parsed: (IN, IN, IN, OUT, INOUT, )
Test passed:true
Parsed: IN[13]
Test passed:true
Parsed: IN[0]
Test passed:true
Parsed: IN[-2]
Test passed:false
Parse failed
Remaining unparsed: 'in[1][2][3]'
Test passed:false
Parse failed
Remaining unparsed: 'in[3][3][3]'
Test passed:false
Parse failed
Remaining unparsed: '(in[3][3][3], out, in_out[0])'
Test passed:false
Parse failed
Remaining unparsed: '(in[3][3][3], out, in_out[0])'
Test passed:true
Parsed: (IN, OUT, )[13]
Test passed:false
Parse failed
Remaining unparsed: '(in, out)[13][0]'
Test passed:true
Test passed:true
Remaining unparsed: 'i n'
Test passed:true
Remaining unparsed: 'inout'
Test passed:true
Remaining unparsed: '()'
Test passed:true
Remaining unparsed: '(in)'
Test passed:true
Remaining unparsed: '(out)'
Test passed:true
Remaining unparsed: '(in_out)'
Test passed:true
Remaining unparsed: 'IN'
如您所见，除了像 in[1][2] 这样的链式数组维度之外，大多数内容都得到了正确的解析。问题是我们通过在规则中引入 "precedence" 来解决歧义：
rScalarSpec = rTypeName | rTupleSpec;
rArraySpec = rScalarSpec >> '[' >> rNumericLiteral >> ']';
rTypeSpec = rArraySpec | rScalarSpec;
这意味着我们总是首先尝试期望数组维度，只有在找不到数组维度时才回退到标量类型规范。这是因为任何数组规范总是首先作为标量规范进行匹配，从而无法解析数组维度部分。
要修复多维情况，您可以尝试断言 [ 不遵循数组规范：
rArraySpec = rScalarSpec >> '[' >> rNumericLiteral >> ']' >> !qi::lit('[')
| rArraySpec >> '[' >> rNumericLiteral >> ']';
但是——砰——我们又回到了左递归（以防我们进入第二个分支，例如in[1][）。
回到绘图板。
我有两个想法。
我想说在 AST 中删除 scalar/array 规范之间的区别是非常有益的。如果将标量视为零秩数组，这意味着我们始终可以将可选维度解析为相同的结果 AST 类型。
另一个想法或多或少地沿着上面显示的道路继续前进，并且如果假定的标量规范后跟“[”字符，则需要一直回溯。在 (very long spec)[1][1][1][1][1][1][1][1][1][1].
让我实现茶歇后概述的第一个想法:)
重做 AST
这里的 TypeSpec 总是携带一个（可能是空的）维度集合：
namespace Ast {
enum class TypeName { IN, OUT, INOUT };
static inline std::ostream& operator<<(std::ostream& os, TypeName tn) {
switch(tn) {
case TypeName::IN: return os << "IN";
case TypeName::OUT: return os << "OUT";
case TypeName::INOUT: return os << "INOUT";
}
return os << "?";
}
struct TypeSpec;
using ScalarSpec = boost::make_recursive_variant<
TypeName,
std::vector<TypeSpec>
>::type;
struct TypeSpec {
ScalarSpec spec;
std::vector<unsigned> dim;
};
using TupleSpec = std::vector<TypeSpec>;
}
请注意，我们还通过使维度无符号来进行改进。语法将检查它不是 0 的完整性。由于这个原因，许多 "positive" 个测试用例已移至 "expected-to-fail" 个用例。
现在语法是对它的直接模仿：
rRank %= qi::uint_ [qi::_pass = (qi::_1 > 0)];
rTypeName = sTypeName;
rTupleSpec = '(' >> rTypeSpec >> +(',' >> rTypeSpec) >> ')';
rScalarSpec = rTypeName | rTupleSpec;
rTypeSpec = rScalarSpec >> *('[' >> rRank >> ']');
Note the semantic action using Phoenix to assert that the array dimension cannot be 0
这是显示所有测试用例都通过的现场演示：
完整演示
//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted.hpp>
/*
<numeric-literal> ::= integer
<type-name> ::= "in" | "out" | "in_out"
<array-type-spec> ::= <type-spec> "[" [<numeric-literal>] "]"
<tuple-type-spec> ::= "(" <type-spec> ("," <type-spec>)+ ")"
<type-spec> ::= <type-name> | <array-type-spec> | <tuple-type-spec>
*/
namespace Ast {
enum class TypeName { IN, OUT, INOUT };
static inline std::ostream& operator<<(std::ostream& os, TypeName tn) {
switch(tn) {
case TypeName::IN: return os << "IN";
case TypeName::OUT: return os << "OUT";
case TypeName::INOUT: return os << "INOUT";
}
return os << "?";
}
struct TypeSpec;
using ScalarSpec = boost::make_recursive_variant<
TypeName,
std::vector<TypeSpec>
>::type;
struct TypeSpec {
ScalarSpec spec;
std::vector<unsigned> dim;
};
using TupleSpec = std::vector<TypeSpec>;
}
BOOST_FUSION_ADAPT_STRUCT(Ast::TypeSpec, spec, dim)
// grammar:
namespace myGrammar {
namespace qi = boost::spirit::qi;
template <typename Iterator = char const *, typename Signature = Ast::TypeSpec()>
struct myRules : qi::grammar<Iterator, Signature> {
myRules() : myRules::base_type(start) {
rRank %= qi::uint_ [qi::_pass = (qi::_1 > 0)];
rTypeName = sTypeName;
rTupleSpec = '(' >> rTypeSpec >> +(',' >> rTypeSpec) >> ')';
rScalarSpec = rTypeName | rTupleSpec;
rTypeSpec = rScalarSpec >> *('[' >> rRank >> ']');
start = qi::skip(qi::space)[rTypeSpec >> qi::eoi];
BOOST_SPIRIT_DEBUG_NODES((start)(rTypeSpec)(rTypeName)(rScalarSpec)(rTypeSpec)(rRank))
}
private:
using Skipper = qi::space_type;
qi::rule<Iterator, Ast::TypeSpec()> start;
qi::rule<Iterator, Ast::ScalarSpec(), Skipper> rScalarSpec;
qi::rule<Iterator, Ast::TypeSpec(), Skipper> rTypeSpec;
qi::rule<Iterator, Ast::TupleSpec(), Skipper> rTupleSpec;
// implicit lexeme
qi::rule<Iterator, Ast::TypeName()> rTypeName;
qi::rule<Iterator, unsigned()> rRank;
// symbols
struct TypeName_r : qi::symbols<char, Ast::TypeName> {
TypeName_r() {
using Ast::TypeName;
add ("in", TypeName::IN)
("out", TypeName::OUT)
("in_out", TypeName::INOUT);
}
} sTypeName;
};
}
static inline std::ostream& operator<<(std::ostream& os, Ast::TypeSpec tn) {
struct {
std::ostream& _os;
void operator()(Ast::ScalarSpec const& ts) const {
apply_visitor(*this, ts);
}
void operator()(Ast::TypeName tn) const { std::cout << tn; }
void operator()(Ast::TupleSpec const& tss) const {
std::cout << "(";
for (auto const& ts: tss) {
(*this)(ts);
std::cout << ", ";
}
std::cout << ")";
}
void operator()(Ast::TypeSpec const& as) const {
(*this)(as.spec);
for (auto rank : as.dim)
std::cout << '[' << rank << ']';
}
} const dumper{os};
dumper(tn);
return os;
}
int main() {
using It = std::string::const_iterator;
myGrammar::myRules<It> const parser;
std::string const test_ok[] = {
"in",
"out",
"in_out",
"(in, out)",
"(out, in)",
"(in, in, in, out, in_out)",
"in[13]",
"in[1][2][3]",
"in[3][3][3]",
"(in[3][3][3], out, in_out[1])",
"(in[3][3][3], out, in_out[1])",
"(in, out)[13]",
"(in, out)[13][14]",
};
std::string const test_fail[] = {
"",
"i n",
"inout",
"()",
"(in)",
"(out)",
"(in_out)",
"IN",
"in[0]",
"in[-2]",
"(in[3][3][3], out, in_out[0])",
"(in[3][3][3], out, in_out[0])",
};
auto expect = [&](std::string const& sample, bool expected) {
It f = sample.begin(), l = sample.end();
Ast::TypeSpec spec;
bool ok = parse(f, l, parser, spec);
std::cout << "Test passed:" << std::boolalpha << (expected == ok) << "\n";
if (expected || (expected != ok)) {
if (ok) {
std::cout << "Parsed: " << spec << "\n";
} else {
std::cout << "Parse failed\n";
}
}
if (f!=l) {
std::cout << "Remaining unparsed: '" << std::string(f,l) << "'\n";
}
};
for (std::string const sample : test_ok) expect(sample, true);
for (std::string const sample : test_fail) expect(sample, false);
}
打印
Test passed:true
Parsed: IN
Test passed:true
Parsed: OUT
Test passed:true
Parsed: INOUT
Test passed:true
Parsed: (IN, OUT, )
Test passed:true
Parsed: (OUT, IN, )
Test passed:true
Parsed: (IN, IN, IN, OUT, INOUT, )
Test passed:true
Parsed: IN[13]
Test passed:true
Parsed: IN[1][2][3]
Test passed:true
Parsed: IN[3][3][3]
Test passed:true
Parsed: (IN[3][3][3], OUT, INOUT[1], )
Test passed:true
Parsed: (IN[3][3][3], OUT, INOUT[1], )
Test passed:true
Parsed: (IN, OUT, )[13]
Test passed:true
Parsed: (IN, OUT, )[13][14]
Test passed:true
Test passed:true
Remaining unparsed: 'i n'
Test passed:true
Remaining unparsed: 'inout'
Test passed:true
Remaining unparsed: '()'
Test passed:true
Remaining unparsed: '(in)'
Test passed:true
Remaining unparsed: '(out)'
Test passed:true
Remaining unparsed: '(in_out)'
Test passed:true
Remaining unparsed: 'IN'
Test passed:true
Remaining unparsed: 'in[0]'
Test passed:true
Remaining unparsed: 'in[-2]'
Test passed:true
Remaining unparsed: '(in[3][3][3], out, in_out[0])'
Test passed:true
Remaining unparsed: '(in[3][3][3], out, in_out[0])'
我正在尝试使用 boost spirit 为以下 BNF 规则编写解析器
(Boost v1.64)
规则是：
<numeric-literal>::= integer
<type-name> ::= "in" | "out" | "in_out"
<array-type-spec> ::= <type-spec> "[" [<numeric-literal>] "]"
<tuple-type-spec> ::= "(" <type-spec> ("," <type-spec>)+ ")"
<type-spec> ::= <type-name> | <array-type-spec> | <tuple-type-spec>
下面是我的尝试，使用 boost::make_recursive_variant
它似乎在字符串 in
上工作正常
但它在 in[2].
上失败了
我的错误在哪里？
什么是优雅的解决方案？
namespace Ast {
enum class TypeName { IN, OUT, INOUT};
using NumericLiteral = int;
using TypeSpec = boost::make_recursive_variant
<
TypeName,
std::pair<boost::recursive_variant_, NumericLiteral>,
std::vector < boost::recursive_variant_ >
>::type;
}
//grammar:
namespace myGrammar {
namespace qi = boost::spirit::qi;
template <typename Iterator = char const*,typename Signature = Ast::TypeSpec()>
struct myRules : qi::grammar < Iterator, Signature> {
myRules() : myRules::base_type(start) {
fillSymbols();
rNumericLiteral = qi::int_;
rTypeName = sTypeName;
rTypeSpec = rTypeName | (rTypeSpec >> '[' >> rNumericLiteral >> ']') | ('(' >> qi::repeat(2, qi::inf)[(rTypeSpec % ',')] >> ')');
start = qi::skip(qi::space)[rTypeSpec];
}
private:
using Skipper = qi::space_type;
qi::rule<Iterator, Ast::TypeSpec()> start;
qi::rule<Iterator, Ast::NumericLiteral(), Skipper> rNumericLiteral;
qi::rule<Iterator, Ast::TypeName(), Skipper> rTypeName;
qi::rule<Iterator, Ast::TypeSpec(), Skipper> rTypeSpec;
//symbols
qi::symbols<char, Ast::TypeName>sTypeName;
void fillSymbols()
{
using namespace Ast;
sTypeName.add
("in", TypeName::IN)
("out", TypeName::OUT)
("in_out", TypeName::INOUT)
}
};
}
将此语法 1:1 转换为 PEG 语法时出现问题，因为左递归会导致无限递归。
您仍然可以轻松地重新排列规则，这样就不会发生左递归，但是在合成您想要的 AST 时会遇到更多麻烦。
这里有一个半途而废的测试结果：
//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
/*
<numeric-literal> ::= integer
<type-name> ::= "in" | "out" | "in_out"
<array-type-spec> ::= <type-spec> "[" [<numeric-literal>] "]"
<tuple-type-spec> ::= "(" <type-spec> ("," <type-spec>)+ ")"
<type-spec> ::= <type-name> | <array-type-spec> | <tuple-type-spec>
*/
namespace Ast {
enum class TypeName { IN, OUT, INOUT };
static inline std::ostream& operator<<(std::ostream& os, TypeName tn) {
switch(tn) {
case TypeName::IN: return os << "IN";
case TypeName::OUT: return os << "OUT";
case TypeName::INOUT: return os << "INOUT";
}
return os << "?";
}
using NumericLiteral = int;
using TypeSpec = boost::make_recursive_variant<
TypeName,
std::pair<boost::recursive_variant_, NumericLiteral>,
std::vector<boost::recursive_variant_>
>::type;
using ArraySpec = std::pair<TypeSpec, NumericLiteral>;
using TupleSpec = std::vector<TypeSpec>;
}
// grammar:
namespace myGrammar {
namespace qi = boost::spirit::qi;
template <typename Iterator = char const *, typename Signature = Ast::TypeSpec()>
struct myRules : qi::grammar<Iterator, Signature> {
myRules() : myRules::base_type(start) {
rNumericLiteral = qi::int_;
rTypeName = sTypeName >> !qi::alpha;
rTupleSpec = '(' >> rTypeSpec >> +(',' >> rTypeSpec) >> ')';
rScalarSpec = rTypeName | rTupleSpec;
rArraySpec = rScalarSpec >> '[' >> rNumericLiteral >> ']';
rTypeSpec = rArraySpec | rScalarSpec;
start = qi::skip(qi::space)[rTypeSpec >> qi::eoi];
BOOST_SPIRIT_DEBUG_NODES((start)(rTypeSpec)(rTypeName)(rArraySpec)(rScalarSpec)(rTypeSpec)(rNumericLiteral))
}
private:
using Skipper = qi::space_type;
qi::rule<Iterator, Ast::TypeSpec()> start;
qi::rule<Iterator, Ast::NumericLiteral(), Skipper> rNumericLiteral;
qi::rule<Iterator, Ast::ArraySpec(), Skipper> rArraySpec;
qi::rule<Iterator, Ast::TypeSpec(), Skipper> rTypeSpec, rScalarSpec;
qi::rule<Iterator, Ast::TupleSpec(), Skipper> rTupleSpec;
// implicit lexeme
qi::rule<Iterator, Ast::TypeName()> rTypeName;
// symbols
struct TypeName_r : qi::symbols<char, Ast::TypeName> {
TypeName_r() {
using Ast::TypeName;
add ("in", TypeName::IN)
("out", TypeName::OUT)
("in_out", TypeName::INOUT);
}
} sTypeName;
};
}
static inline std::ostream& operator<<(std::ostream& os, Ast::TypeSpec tn) {
struct {
std::ostream& _os;
void operator()(Ast::TypeSpec const& ts) const {
apply_visitor(*this, ts);
}
void operator()(Ast::TypeName tn) const { std::cout << tn; }
void operator()(Ast::TupleSpec const& tss) const {
std::cout << "(";
for (auto const& ts: tss) {
(*this)(ts);
std::cout << ", ";
}
std::cout << ")";
}
void operator()(Ast::ArraySpec const& as) const {
(*this)(as.first);
std::cout << '[' << as.second << ']';
}
} const dumper{os};
dumper(tn);
return os;
}
int main() {
using It = std::string::const_iterator;
myGrammar::myRules<It> const parser;
std::string const test_ok[] = {
"in",
"out",
"in_out",
"(in, out)",
"(out, in)",
"(in, in, in, out, in_out)",
"in[13]",
"in[0]",
"in[-2]",
"in[1][2][3]",
"in[3][3][3]",
"(in[3][3][3], out, in_out[0])",
"(in[3][3][3], out, in_out[0])",
"(in, out)[13]",
"(in, out)[13][0]",
};
std::string const test_fail[] = {
"",
"i n",
"inout",
"()",
"(in)",
"(out)",
"(in_out)",
"IN",
};
auto expect = [&](std::string const& sample, bool expected) {
It f = sample.begin(), l = sample.end();
Ast::TypeSpec spec;
bool ok = parse(f, l, parser, spec);
std::cout << "Test passed:" << std::boolalpha << (expected == ok) << "\n";
if (expected || (expected != ok)) {
if (ok) {
std::cout << "Parsed: " << spec << "\n";
} else {
std::cout << "Parse failed\n";
}
}
if (f!=l) {
std::cout << "Remaining unparsed: '" << std::string(f,l) << "'\n";
}
};
for (std::string const sample : test_ok) expect(sample, true);
for (std::string const sample : test_fail) expect(sample, false);
}
打印
Test passed:true
Parsed: IN
Test passed:true
Parsed: OUT
Test passed:true
Parsed: INOUT
Test passed:true
Parsed: (IN, OUT, )
Test passed:true
Parsed: (OUT, IN, )
Test passed:true
Parsed: (IN, IN, IN, OUT, INOUT, )
Test passed:true
Parsed: IN[13]
Test passed:true
Parsed: IN[0]
Test passed:true
Parsed: IN[-2]
Test passed:false
Parse failed
Remaining unparsed: 'in[1][2][3]'
Test passed:false
Parse failed
Remaining unparsed: 'in[3][3][3]'
Test passed:false
Parse failed
Remaining unparsed: '(in[3][3][3], out, in_out[0])'
Test passed:false
Parse failed
Remaining unparsed: '(in[3][3][3], out, in_out[0])'
Test passed:true
Parsed: (IN, OUT, )[13]
Test passed:false
Parse failed
Remaining unparsed: '(in, out)[13][0]'
Test passed:true
Test passed:true
Remaining unparsed: 'i n'
Test passed:true
Remaining unparsed: 'inout'
Test passed:true
Remaining unparsed: '()'
Test passed:true
Remaining unparsed: '(in)'
Test passed:true
Remaining unparsed: '(out)'
Test passed:true
Remaining unparsed: '(in_out)'
Test passed:true
Remaining unparsed: 'IN'
如您所见，除了像 in[1][2] 这样的链式数组维度之外，大多数内容都得到了正确的解析。问题是我们通过在规则中引入 "precedence" 来解决歧义：
rScalarSpec = rTypeName | rTupleSpec;
rArraySpec = rScalarSpec >> '[' >> rNumericLiteral >> ']';
rTypeSpec = rArraySpec | rScalarSpec;
这意味着我们总是首先尝试期望数组维度，只有在找不到数组维度时才回退到标量类型规范。这是因为任何数组规范总是首先作为标量规范进行匹配，从而无法解析数组维度部分。
要修复多维情况，您可以尝试断言 [ 不遵循数组规范：
rArraySpec = rScalarSpec >> '[' >> rNumericLiteral >> ']' >> !qi::lit('[')
| rArraySpec >> '[' >> rNumericLiteral >> ']';
但是——砰——我们又回到了左递归（以防我们进入第二个分支，例如in[1][）。
回到绘图板。
我有两个想法。
我想说在 AST 中删除 scalar/array 规范之间的区别是非常有益的。如果将标量视为零秩数组，这意味着我们始终可以将可选维度解析为相同的结果 AST 类型。
另一个想法或多或少地沿着上面显示的道路继续前进，并且如果假定的标量规范后跟“[”字符，则需要一直回溯。在
(very long spec)[1][1][1][1][1][1][1][1][1][1]. 这样的情况下，这将导致最糟糕的行为
让我实现茶歇后概述的第一个想法:)
重做 AST
这里的 TypeSpec 总是携带一个（可能是空的）维度集合：
namespace Ast {
enum class TypeName { IN, OUT, INOUT };
static inline std::ostream& operator<<(std::ostream& os, TypeName tn) {
switch(tn) {
case TypeName::IN: return os << "IN";
case TypeName::OUT: return os << "OUT";
case TypeName::INOUT: return os << "INOUT";
}
return os << "?";
}
struct TypeSpec;
using ScalarSpec = boost::make_recursive_variant<
TypeName,
std::vector<TypeSpec>
>::type;
struct TypeSpec {
ScalarSpec spec;
std::vector<unsigned> dim;
};
using TupleSpec = std::vector<TypeSpec>;
}
请注意，我们还通过使维度无符号来进行改进。语法将检查它不是 0 的完整性。由于这个原因，许多 "positive" 个测试用例已移至 "expected-to-fail" 个用例。
现在语法是对它的直接模仿：
rRank %= qi::uint_ [qi::_pass = (qi::_1 > 0)];
rTypeName = sTypeName;
rTupleSpec = '(' >> rTypeSpec >> +(',' >> rTypeSpec) >> ')';
rScalarSpec = rTypeName | rTupleSpec;
rTypeSpec = rScalarSpec >> *('[' >> rRank >> ']');
Note the semantic action using Phoenix to assert that the array dimension cannot be 0
这是显示所有测试用例都通过的现场演示：
完整演示
//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted.hpp>
/*
<numeric-literal> ::= integer
<type-name> ::= "in" | "out" | "in_out"
<array-type-spec> ::= <type-spec> "[" [<numeric-literal>] "]"
<tuple-type-spec> ::= "(" <type-spec> ("," <type-spec>)+ ")"
<type-spec> ::= <type-name> | <array-type-spec> | <tuple-type-spec>
*/
namespace Ast {
enum class TypeName { IN, OUT, INOUT };
static inline std::ostream& operator<<(std::ostream& os, TypeName tn) {
switch(tn) {
case TypeName::IN: return os << "IN";
case TypeName::OUT: return os << "OUT";
case TypeName::INOUT: return os << "INOUT";
}
return os << "?";
}
struct TypeSpec;
using ScalarSpec = boost::make_recursive_variant<
TypeName,
std::vector<TypeSpec>
>::type;
struct TypeSpec {
ScalarSpec spec;
std::vector<unsigned> dim;
};
using TupleSpec = std::vector<TypeSpec>;
}
BOOST_FUSION_ADAPT_STRUCT(Ast::TypeSpec, spec, dim)
// grammar:
namespace myGrammar {
namespace qi = boost::spirit::qi;
template <typename Iterator = char const *, typename Signature = Ast::TypeSpec()>
struct myRules : qi::grammar<Iterator, Signature> {
myRules() : myRules::base_type(start) {
rRank %= qi::uint_ [qi::_pass = (qi::_1 > 0)];
rTypeName = sTypeName;
rTupleSpec = '(' >> rTypeSpec >> +(',' >> rTypeSpec) >> ')';
rScalarSpec = rTypeName | rTupleSpec;
rTypeSpec = rScalarSpec >> *('[' >> rRank >> ']');
start = qi::skip(qi::space)[rTypeSpec >> qi::eoi];
BOOST_SPIRIT_DEBUG_NODES((start)(rTypeSpec)(rTypeName)(rScalarSpec)(rTypeSpec)(rRank))
}
private:
using Skipper = qi::space_type;
qi::rule<Iterator, Ast::TypeSpec()> start;
qi::rule<Iterator, Ast::ScalarSpec(), Skipper> rScalarSpec;
qi::rule<Iterator, Ast::TypeSpec(), Skipper> rTypeSpec;
qi::rule<Iterator, Ast::TupleSpec(), Skipper> rTupleSpec;
// implicit lexeme
qi::rule<Iterator, Ast::TypeName()> rTypeName;
qi::rule<Iterator, unsigned()> rRank;
// symbols
struct TypeName_r : qi::symbols<char, Ast::TypeName> {
TypeName_r() {
using Ast::TypeName;
add ("in", TypeName::IN)
("out", TypeName::OUT)
("in_out", TypeName::INOUT);
}
} sTypeName;
};
}
static inline std::ostream& operator<<(std::ostream& os, Ast::TypeSpec tn) {
struct {
std::ostream& _os;
void operator()(Ast::ScalarSpec const& ts) const {
apply_visitor(*this, ts);
}
void operator()(Ast::TypeName tn) const { std::cout << tn; }
void operator()(Ast::TupleSpec const& tss) const {
std::cout << "(";
for (auto const& ts: tss) {
(*this)(ts);
std::cout << ", ";
}
std::cout << ")";
}
void operator()(Ast::TypeSpec const& as) const {
(*this)(as.spec);
for (auto rank : as.dim)
std::cout << '[' << rank << ']';
}
} const dumper{os};
dumper(tn);
return os;
}
int main() {
using It = std::string::const_iterator;
myGrammar::myRules<It> const parser;
std::string const test_ok[] = {
"in",
"out",
"in_out",
"(in, out)",
"(out, in)",
"(in, in, in, out, in_out)",
"in[13]",
"in[1][2][3]",
"in[3][3][3]",
"(in[3][3][3], out, in_out[1])",
"(in[3][3][3], out, in_out[1])",
"(in, out)[13]",
"(in, out)[13][14]",
};
std::string const test_fail[] = {
"",
"i n",
"inout",
"()",
"(in)",
"(out)",
"(in_out)",
"IN",
"in[0]",
"in[-2]",
"(in[3][3][3], out, in_out[0])",
"(in[3][3][3], out, in_out[0])",
};
auto expect = [&](std::string const& sample, bool expected) {
It f = sample.begin(), l = sample.end();
Ast::TypeSpec spec;
bool ok = parse(f, l, parser, spec);
std::cout << "Test passed:" << std::boolalpha << (expected == ok) << "\n";
if (expected || (expected != ok)) {
if (ok) {
std::cout << "Parsed: " << spec << "\n";
} else {
std::cout << "Parse failed\n";
}
}
if (f!=l) {
std::cout << "Remaining unparsed: '" << std::string(f,l) << "'\n";
}
};
for (std::string const sample : test_ok) expect(sample, true);
for (std::string const sample : test_fail) expect(sample, false);
}
打印
Test passed:true
Parsed: IN
Test passed:true
Parsed: OUT
Test passed:true
Parsed: INOUT
Test passed:true
Parsed: (IN, OUT, )
Test passed:true
Parsed: (OUT, IN, )
Test passed:true
Parsed: (IN, IN, IN, OUT, INOUT, )
Test passed:true
Parsed: IN[13]
Test passed:true
Parsed: IN[1][2][3]
Test passed:true
Parsed: IN[3][3][3]
Test passed:true
Parsed: (IN[3][3][3], OUT, INOUT[1], )
Test passed:true
Parsed: (IN[3][3][3], OUT, INOUT[1], )
Test passed:true
Parsed: (IN, OUT, )[13]
Test passed:true
Parsed: (IN, OUT, )[13][14]
Test passed:true
Test passed:true
Remaining unparsed: 'i n'
Test passed:true
Remaining unparsed: 'inout'
Test passed:true
Remaining unparsed: '()'
Test passed:true
Remaining unparsed: '(in)'
Test passed:true
Remaining unparsed: '(out)'
Test passed:true
Remaining unparsed: '(in_out)'
Test passed:true
Remaining unparsed: 'IN'
Test passed:true
Remaining unparsed: 'in[0]'
Test passed:true
Remaining unparsed: 'in[-2]'
Test passed:true
Remaining unparsed: '(in[3][3][3], out, in_out[0])'
Test passed:true
Remaining unparsed: '(in[3][3][3], out, in_out[0])'