Pio*_*trK 2 c++ parsing autocomplete boost-spirit
我正在使用Boost :: Spirit在我的C++ GUI应用程序中为非技术用户构建简单的"数据过滤"语言.语言与普通英语非常相似,可以解析为AST.我被要求尽可能方便用户进程,所以我希望提供类似CLang的错误消息("无法识别'tokken',你的意思是'令牌'？")和自动完成.
现在的问题是如何使用Boost :: Spirit语法为两个目标生成可能的令牌列表(我将使用简单的字符串距离算法来满足第一个要求)？
我的想法到目前为止:
这个解决方案的问题是建议还会建议对给定地点无效的令牌.如果我添加(我会)可定义的标识符,我手头有更大的问题...
还有一个约束:我希望只在一个地方定义这种语言的语法; 如果语法改变了,我想在重新编译后自动完成注意这个改变
出于好奇,我决定尝试这个概念.
这是我的尝试.
让我们用函数调用解析算术表达式.
现在,我们想要用可能的未知标识符解析(部分)表达式.
如果表达式不完整,我们希望"暗示"最小标记来完成它(并可能继续解析).
在标识符未知的情况下,我们希望模糊匹配域中的已知标识符(变量或函数),并按概率递减的顺序对它们进行排序.
让我们首先决定我们希望输入在内存中,所以我们可以使用string_views 来引用位置/子串:
#include <boost/utility/string_view.hpp>
using Source = boost::string_view;
using Location = Source::const_iterator;
除了AST之外,我们希望我们的解析器生成完成提示(隐式完成标记和建议)
namespace Completion {
using Candidates = std::vector<std::string>;
class Hints {
struct ByLocation {
template <typename T, typename U>
bool operator()(T const& a, U const& b) const { return loc(a) < loc(b); }
private:
static Location loc(Source const& s) { return s.begin(); }
static Location loc(Location const& l) { return l; }
};
public:
std::map<Location, std::string, ByLocation> incomplete;
std::map<Source, Candidates, ByLocation> suggestions;
/*explicit*/ operator bool() const { return incomplete.size() || suggestions.size(); }
};
In addition, let's code up a quick & dirty fuzzy identifier match scoring function.
I opted for a simple synchronizing compare that
adj_diff is a good fuzzy match for adjacent_difference even though characters have been skipped from the candidate, but adj_qqq_diff is worse because the qqq from the input could not be matched)rate=1 at first invocation) static int fuzzy_match(Source input, boost::string_view candidate, int rate = 1) { // start with first-letter boost
int score = 0;
while (!(input.empty() || candidate.empty())) {
if (input.front() != candidate.front()) {
return score + std::max(
fuzzy_match(input.substr(1), candidate, std::max(rate-2,0)), //penalty for ignoring an input char
fuzzy_match(input, candidate.substr(1), std::max(rate-1,0)));
}
input.remove_prefix(1);
candidate.remove_prefix(1);
score += ++rate;
}
return score;
}
} // namespace Completion
We'll see how this is used in the grammar.
A run-of-the-mill AST that can do binary expressions, string/numeric literals, variables and (nested) function calls:
#include <boost/variant.hpp>
namespace Ast {
using NumLiteral = double;
using StringLiteral = std::string; // de-escaped, not source view
struct Identifier : std::string {
using std::string::string;
using std::string::operator=;
};
struct BinaryExpression;
struct CallExpression;
using Expression = boost::variant<
NumLiteral,
StringLiteral,
Identifier,
boost::recursive_wrapper<BinaryExpression>,
boost::recursive_wrapper<CallExpression>
>;
struct BinaryExpression {
Expression lhs;
char op;
Expression rhs;
};
using ArgList = std::vector<Expression>;
struct CallExpression {
Identifier function;
ArgList args;
};
}
语法也从"基本"开始:
namespace Parsing {
namespace qi = boost::spirit::qi;
namespace phx = boost::phoenix;
template <typename It>
struct Expression : qi::grammar<It, Ast::Expression()> {
Expression(Completion::Hints& hints) : Expression::base_type(start), _hints(hints) {
using namespace qi;
start = skip(space) [expression];
expression = term [_val = _1] >> *(char_("-+") >> expression) [_val = make_binary(_val, _1, _2)];
term = factor [_val = _1] >> *(char_("*/") >> term) [_val = make_binary(_val, _1, _2)];
factor = simple [_val = _1] >> *(char_("^") >> factor) [_val = make_binary(_val, _1, _2)];
simple = call | variable | compound | number | string;
到目前为止一切顺利:构造函数存储Completion::Hints&对要记录的引用.所有这些规则都被定义为qi::rule<It, Expression(), qi::space_type>.
现在它变得更有趣了,这里的一些规则是lexemes¹
number = double_;
identifier = raw[(alpha|'_') >> *(alnum|'_')];
有些作品可以容忍错过结束令牌:
// imply the closing quotes
string %= '"' >> *('\\' >> char_ | ~char_('"')) >> implied('"');
compound %= '(' >> expression >> implied(')');
该implied魔法使得它如此,如果有结束的令牌丢失,它会被记录为一个提示,并继续解析:
auto implied = [=](char ch) {
return copy(omit[lit(ch) | raw[eps][imply(_1, ch)]]);
};
当然,这引出了imply(_1, ch)真正的问题,我们稍后会看到.
现在,请注意我们在语义操作中
raw[eps]获取(空)源iterator_range来构造Locationfrom.
我们在Domain会员中存储"符号表" _variables并且_functions:
using Domain = qi::symbols<char>;
Domain _variables, _functions;
Then we declare some rules that can do lookups on either of them:
// domain identifier lookups
qi::_r1_type _domain;
qi::rule<It, Ast::Identifier(Domain const&)> maybe_known, known, unknown;
The corresponding declarations will be shown shortly.
Variables are pretty simple:
variable = maybe_known(phx::ref(_variables));
Calls are trickier. If a name is unknown we don't want to assume it implies a function unless it's followed by a '(' character. However, if an identifier is a known function name, we want even to imply the ( (this gives the UX the appearance of autocompletion where when the user types sqrt, it suggests the next character to be ( magically).
// The heuristics:
// - an unknown identifier followed by (
// - an unclosed argument list implies )
call %= ( known(phx::ref(_functions)) // known -> imply the parens
| &(identifier >> '(') >> unknown(phx::ref(_functions))
) >> implied('(') >> -(expression % ',') >> implied(')');
It all builds on known, unknown and maybe_known:
///////////////////////////////
// identifier loopkup, suggesting
{
maybe_known = known(_domain) | unknown(_domain);
// distinct to avoid partially-matching identifiers
using boost::spirit::repository::qi::distinct;
auto kw = distinct(copy(alnum | '_'));
known = raw[kw[lazy(_domain)]];
unknown = raw[identifier[_val=_1]] [suggest_for(_1, _domain)];
}
Remaining is a bit of red tape:
BOOST_SPIRIT_DEBUG_NODES(
(start)
(expression)(term)(factor)(simple)(compound)
(call)(variable)
(identifier)(number)(string)
//(maybe_known)(known)(unknown) // qi::symbols<> non-streamable
)
_variables += "foo", "bar", "qux";
_functions += "print", "sin", "tan", "sqrt", "frobnicate";
}
private:
Completion::Hints& _hints;
using Domain = qi::symbols<char>;
Domain _variables, _functions;
qi::rule<It, Ast::Expression()> start;
qi::rule<It, Ast::Expression(), qi::space_type> expression, term, factor, simple;
// completables
qi::rule<It, Ast::Expression(), qi::space_type> compound;
qi::rule<It, Ast::CallExpression(), qi::space_type> call;
// implicit lexemes
qi::rule<It, Ast::Identifier()> variable, identifier;
qi::rule<It, Ast::NumLiteral()> number;
qi::rule<It, Ast::StringLiteral()> string;
// domain identifier lookups
qi::_r1_type _domain;
qi::rule<It, Ast::Identifier(Domain const&)> maybe_known, known, unknown;
Let's start with the usual helper to construct binary AST nodes:
///////////////////////////////
// binary expression factory
struct make_binary_f {
Ast::BinaryExpression operator()(Ast::Expression const& lhs, char op, Ast::Expression const& rhs) const {
return {lhs, op, rhs};
}
};
boost::phoenix::function<make_binary_f> make_binary;
Similarly, we can have a Phoenix function object to register implied chars:
///////////////////////////////
// auto-completing incomplete expressions
struct imply_f {
Completion::Hints& _hints;
void operator()(boost::iterator_range<It> where, char implied_char) const {
auto inserted =
_hints.incomplete.emplace(&*where.begin(), std::string(1, implied_char));
// add the implied char to existing completion
if (!inserted.second)
inserted.first->second += implied_char;
}
};
boost::phoenix::function<imply_f> imply { imply_f { _hints } };
Note that it orders by location (which makes UX easier) and detects when a previous implied token lived at the same location, in which case we simply append to it.
By now it won't be much of a surprise that generating relevant suggestions for unknown identifiers is also a phoenix actor:
///////////////////////////////
// suggest_for
struct suggester {
Completion::Hints& _hints;
void operator()(boost::iterator_range<It> where, Domain const& symbols) const {
using namespace Completion;
Source id(&*where.begin(), where.size());
Candidates c;
symbols.for_each([&](std::string const& k, ...) { c.push_back(k); });
auto score = [id](Source v) { return fuzzy_match(id, v); };
auto byscore = [=](Source a, Source b) { return score(a) > score(b); };
sort(c.begin(), c.end(), byscore);
c.erase( remove_if(c.begin(), c.end(), [=](Source s) { return score(s) < 3; }), c.end());
_hints.suggestions.emplace(id, c);
}
};
boost::phoenix::function<suggester> suggest_for {suggester{_hints}};
That's all. If it looks more complicated, that's because it does a lot more: it scores all candidates fuzzily, orders them by descending score and removes any candidates with score < 3.
};
}
Let's alter things a little more and allow ',' to be implied inside argument lists:
call %= ( known(phx::ref(_functions)) // known -> imply the parens
| &(identifier >> '(') >> unknown(phx::ref(_functions))
)
>> implied('(')
>> -(expression % ',')
>> implied(')')
;
Let's replace ',' there:
>> -(expression % (',' | !(')'|eoi) >> implied(',')))
NOTE: It might seem to make more sense to detect
&expressionto assert that an expression follows, instead asserting that the end of the input/argument list has not been reached.Doing that goes bad, though, because any contained expressions could trigger more implied tokens as a side effect, leading to duplicated implied tokens.
This (side-effectful semantic actions) is one of the chief reasons why I usually avoid semantic actions, or use them to store effect only in the rule's (exposed) attribute(s). See Boost Spirit: "Semantic actions are evil"?
This post would be nothing without some nice test cases. So here goes:
int main() {
for (Source const input : {
"", // invalid
"(3", // incomplete, imply ')'
"3*(6+sqrt(9))^7 - 1e8", // completely valid
"(3*(((6+sqrt(9))^7 - 1e8", // incomplete, imply ")))"
"print(\"hello \\\"world!", // completes the string literal and the parameter list
"foo", // okay, known variable
"baz", // (suggest bar)
"baz(", // incomplete, imply ')', unknown function
"taz(", // incomplete, imply ')', unknown function
"san(", // 2 suggestions (sin/tan)
"print(1, 2, \"three\", complicated(san(78",
"(print sqrt sin 9) -0) \"bye",
})
{
std::cout << "-------------- '" << input << "'\n";
Location f = input.begin(), l = input.end();
Ast::Expression expr;
Completion::Hints hints;
bool ok = parse(f, l, Parsing::Expression<Location>{hints}, expr);
if (hints) {
std::cout << "Input: '" << input << "'\n";
}
for (auto& c : hints.incomplete) {
std::cout << "Missing " << std::setw(c.first - input.begin()) << "" << "^ implied: '" << c.second << "'\n";
}
for (auto& id : hints.suggestions) {
std::cout << "Unknown " << std::setw(id.first.begin() - input.begin()) << "" << std::string(id.first.size(), '^');
if (id.second.empty())
std::cout << " (no suggestions)\n";
else {
std::cout << " (did you mean ";
once_t first;
for (auto& s : id.second)
std::cout << (first?"":" or ") << "'" << s << "'";
std::cout << "?)\n";
}
}
if (ok) {
std::cout << "AST: " << expr << "\n";
} else {
std::cout << "Parse failed\n";
}
if (f!=l)
std::cout << "Remaining input: '" << std::string(f,l) << "'\n";
}
}
Note that, besides the first input ("") everything is heuristically parsed as some kind of expression! The last one is designed to show off how all the parameter lists are implied because print, sqrt and sin are known functions. Then some ',' are implied, before finally the unclosed string literal and remaining parentheses are closed. Here's the (non-debug) output:
-------------- ''
Parse failed
-------------- '(3'
Input: '(3'
Missing ^ implied: ')'
AST: 3
-------------- '3*(6+sqrt(9))^7 - 1e8'
AST: ((3 * ((6 + (sqrt (9))) ^ 7)) - 1e+08)
-------------- '(3*(((6+sqrt(9))^7 - 1e8'
Input: '(3*(((6+sqrt(9))^7 - 1e8'
Missing ^ implied: ')))'
AST: (3 * (((6 + (sqrt (9))) ^ 7) - 1e+08))
-------------- 'print("hello \"world!'
Input: 'print("hello \"world!'
Missing ^ implied: '")'
AST: (print (hello "world!))
-------------- 'foo'
AST: foo
-------------- 'baz'
Input: 'baz'
Unknown ^^^ (did you mean 'bar'?)
AST: baz
-------------- 'baz('
Input: 'baz('
Missing ^ implied: ')'
Unknown ^^^ (no suggestions)
AST: (baz ())
-------------- 'taz('
Input: 'taz('
Missing ^ implied: ')'
Unknown ^^^ (did you mean 'tan'?)
AST: (taz ())
-------------- 'san('
Input: 'san('
Missing ^ implied: ')'
Unknown ^^^ (did you mean 'sin' or 'tan'?)
AST: (san ())
-------------- 'print(1, 2, "three", complicated(san(78'
Input: 'print(1, 2, "three", complicated(san(78'
Missing ^ implied: ')))'
Unknown ^^^^^^^^^^^ (did you mean 'frobnicate' or 'print'?)
Unknown ^^^ (did you mean 'sin' or 'tan'?)
AST: (print (1, 2, three, (complicated ((san (78))))))
-------------- '(print sqrt sin 9) -0) "bye'
Input: '(print sqrt sin 9) -0) "bye'
Missing ^ implied: '('
Missing ^ implied: '('
Missing ^ implied: '('
Missing ^ implied: ','
Missing ^ implied: '"))'
AST: (print ((sqrt (((sin (9)) - 0))), bye))
//#define BOOST_SPIRIT_DEBUG
#include <boost/utility/string_view.hpp>
using Source = boost::string_view;
using Location = Source::const_iterator;
#include <map>
#include <vector>
namespace Completion {
static int fuzzy_match(Source input, boost::string_view candidate, int rate = 1) { // start with first-letter boost
int score = 0;
while (!(input.empty() || candidate.empty())) {
if (input.front() != candidate.front()) {
return score + std::max(
fuzzy_match(input.substr(1), candidate, std::max(rate-2,0)), //penalty for ignoring an input char
fuzzy_match(input, candidate.substr(1), std::max(rate-1,0)));
}
input.remove_prefix(1);
candidate.remove_prefix(1);
score += ++rate;
}
return score;
}
using Candidates = std::vector<std::string>;
class Hints {
struct ByLocation {
template <typename T, typename U>
bool operator()(T const& a, U const& b) const { return loc(a) < loc(b); }
private:
static Location loc(Source const& s) { return s.begin(); }
static Location loc(Location const& l) { return l; }
};
public:
std::map<Location, std::string, ByLocation> incomplete;
std::map<Source, Candidates, ByLocation> suggestions;
/*explicit*/ operator bool() const { return incomplete.size() || suggestions.size(); }
};
}
#include <boost/variant.hpp>
namespace Ast {
using NumLiteral = double;
using StringLiteral = std::string; // de-escaped, not source view
struct Identifier : std::string {
using std::string::string;
using std::string::operator=;
};
struct BinaryExpression;
struct CallExpression;
using Expression = boost::variant<
NumLiteral,
StringLiteral,
Identifier,
boost::recursive_wrapper<BinaryExpression>,
boost::recursive_wrapper<CallExpression>
>;
struct BinaryExpression {
Expression lhs;
char op;
Expression rhs;
};
using ArgList = std::vector<Expression>;
struct CallExpression {
Identifier function;
ArgList args;
};
}
#include <boost/fusion/adapted/struct.hpp>
BOOST_FUSION_ADAPT_STRUCT(Ast::BinaryExpression, lhs, op, rhs)
BOOST_FUSION_ADAPT_STRUCT(Ast::CallExpression, function, args)
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/repository/include/qi_distinct.hpp>
// for debug printing:
namespace {
struct once_t { // an auto-reset flag
operator bool() { bool v = flag; flag = false; return v; }
bool flag = true;
};
}
// for debug printing:
namespace Ast {
static inline std::ostream& operator<<(std::ostream& os, std::vector<Expression> const& args) {
os << "(";
once_t first;
for (auto& a : args) os << (first?"":", ") << a;
return os << ")";
}
static inline std::ostream& operator<<(std::ostream& os, BinaryExpression const& e) {
return os << boost::fusion::as_vector(e);
}
static inline std::ostream& operator<<(std::ostream& os, CallExpression const& e) {
return os << boost::fusion::as_vector(e);
}
}
namespace Parsing {
namespace qi = boost::spirit::qi;
namespace phx = boost::phoenix;
template <typename It>
struct Expression : qi::grammar<It, Ast::Expression()> {
Expression(Completion::Hints& hints) : Expression::base_type(start), _hints(hints) {
using namespace qi;
start = skip(space) [expression];
expression = term [_val = _1] >> *(char_("-+") >> expression) [_val = make_binary(_val, _1, _2)];
term = factor [_val = _1] >> *(char_("*/") >> term) [_val = make_binary(_val, _1, _2)];
factor = simple [_val = _1] >> *(char_("^") >> factor) [_val = make_binary(_val, _1, _2)];
simple = call | variable | compound | number | string;
auto implied = [=](char ch) {
return copy(omit[lit(ch) | raw[eps][imply(_1, ch)]]);
};
variable = maybe_known(phx::ref(_variables));
compound %= '(' >> expression >> implied(')');
// The heuristics:
// - an unknown identifier followed by (
// - an unclosed argument list implies )
call %= ( known(phx::ref(_functions)) // known -> imply the parens
| &(identifier >> '(') >> unknown(phx::ref(_functions))
)
>> implied('(')
>> -(expression % (',' | !(')'|eoi) >> implied(',')))
>> implied(')')
;
// lexemes, primitive rules
identifier = raw[(alpha|'_') >> *(alnum|'_')];
// imply the closing quotes
string %= '"' >> *('\\' >> char_ | ~char_('"')) >> implied('"'); // TODO more escapes
number = double_; // TODO integral arguments
///////////////////////////////
// identifier loopkup, suggesting
{
maybe_known = known(_domain) | unknown(_domain);
// distinct to avoid partially-matching identifiers
using boost::spirit::repository::qi::distinct;
auto kw = distinct(copy(alnum | '_'));
known = raw[kw[lazy(_domain)]];
unknown = raw[identifier[_val=_1]] [suggest_for(_1, _domain)];
}
BOOST_SPIRIT_DEBUG_NODES(
(start)
(expression)(term)(factor)(simple)(compound)
(call)(variable)
(identifier)(number)(string)
//(maybe_known)(known)(unknown) // qi::symbols<> non-streamable
)
_variables += "foo", "bar", "qux";
_functions += "print", "sin", "tan", "sqrt", "frobnicate";
}
private:
Completion::Hints& _hints;
using Domain = qi::symbols<char>;
Domain _variables, _functions;
qi::rule<It, Ast::Expression()> start;
qi::rule<It, Ast::Expression(), qi::space_type> expression, term, factor, simple;
// completables
qi::rule<It, Ast::Expression(), qi::space_type> compound;
qi::rule<It, Ast::CallExpression(), qi::space_type> call;
// implicit lexemes
qi::rule<It, Ast::Identifier()> variable, identifier;
qi::rule<It, Ast::NumLiteral()> number;
qi::rule<It, Ast::StringLiteral()> string;
// domain identifier lookups
qi::_r1_type _domain;
qi::rule<It, Ast::Identifier(Domain const&)> maybe_known, known, unknown;
///////////////////////////////
// binary expression factory
struct make_binary_f {
Ast::BinaryExpression operator()(Ast::Expression const& lhs, char op, Ast::Expression const& rhs) const {
return {lhs, op, rhs};
}
};
boost::phoenix::function<make_binary_f> make_binary;
///////////////////////////////
// auto-completing incomplete expressions
struct imply_f {
Completion::Hints& _hints;
void operator()(boost::iterator_range<It> where, char implied_char) const {
auto inserted =
_hints.incomplete.emplace(&*where.begin(), std::string(1, implied_char));
// add the implied char to existing completion
if (!inserted.second)
inserted.first->second += implied_char;
}
};
boost::phoenix::function<imply_f> imply { imply_f { _hints } };
///////////////////////////////
// suggest_for
struct suggester {
Completion::Hints& _hints;
void operator()(boost::iterator_range<It> where, Domain const& symbols) const {
using namespace Completion;
Source id(&*where.begin(), where.size());
Candidates c;
symbols.for_each([&](std::string const& k, ...) { c.push_back(k); });
auto score = [id](Source v) { return fuzzy_match(id, v); };
auto byscore = [=](Source a, Source b) { return score(a) > score(b); };
sort(c.begin(), c.end(), byscore);
c.erase( remove_if(c.begin(), c.end(), [=](Source s) { return score(s) < 3; }), c.end());
_hints.suggestions.emplace(id, c);
}
};
boost::phoenix::function<suggester> suggest_for {suggester{_hints}};
};
}
#include <iostream>
#include <iomanip>
int main() {
for (Source const input : {
"", // invalid
"(3", // incomplete, imply ')'
"3*(6+sqrt(9))^7 - 1e8", // completely valid
"(3*(((6+sqrt(9))^7 - 1e8", // incomplete, imply ")))"
"print(\"hello \\\"world!", // completes the string literal and the parameter list
"foo", // okay, known variable
"baz", // (suggest bar)
"baz(", // incomplete, imply ')', unknown function
"taz(", // incomplete, imply ')', unknown function
"san(", // 2 suggestions (sin/tan)
"print(1, 2, \"three\", complicated(san(78",
"(print sqrt sin 9) -0) \"bye",
})
{
std::cout << "-------------- '" << input << "'\n";
Location f = input.begin(), l = input.end();
Ast::Expression expr;
Completion::Hints hints;
bool ok = parse(f, l, Parsing::Expression<Location>{hints}, expr);
if (hints) {
std::cout << "Input: '" << input << "'\n";
}
for (auto& c : hints.incomplete) {
std::cout << "Missing " << std::setw(c.first - input.begin()) << "" << "^ implied: '" << c.second << "'\n";
}
for (auto& id : hints.suggestions) {
std::cout << "Unknown " << std::setw(id.first.begin() - input.begin()) << "" << std::string(id.first.size(), '^');
if (id.second.empty())
std::cout << " (no suggestions)\n";
else {
std::cout << " (did you mean ";
once_t first;
for (auto& s : id.second)
std::cout << (first?"":" or ") << "'" << s << "'";
std::cout << "?)\n";
}
}
if (ok) {
std::cout << "AST: " << expr << "\n";
} else {
std::cout << "Parse failed\n";
}
if (f!=l)
std::cout << "Remaining input: '" << std::string(f,l) << "'\n";
}
}
| 归档时间： |
|
| 查看次数： |
377 次 |
| 最近记录： |