c++ - प्रदाता उपयोगकर्ता को दिए गए बढ़ावा के लिए स्वत: पूर्ण सुझावों के साथ कैसे करें:: भावना व्याकरण?




parsing autocomplete (2)

आत्मा में वह विशेषता नहीं है। आप इसे स्वयं उत्पन्न कर सकते हैं, लेकिन इसे उदारतापूर्वक करने के लिए काफी प्रयास होगा (यदि एनपी-पूर्णता के कारण असंभव नहीं है, तो सीधे)। शायद बस पार्स त्रुटि ( on_error ) का पता लगाएं और स्टॉक की एक सीमित संख्या "विकल्प" है - 80% नियम को एक लंबा रास्ता तय करना चाहिए।

इसके अलावा, मुझे लगता है कि 'अमान्य प्लेसहोल्डर टोकन' को पार्स करने के साथ "स्केच" काम नहीं करेगा क्योंकि आपको प्लेसहोल्डर टोकन के प्रकार के बारे में मान्यताओं का निर्माण करना होगा और इसलिए इसका परिणाम मान्य अभिव्यक्ति नहीं हो सकता है।

मुझे लगता है कि आप अभिव्यक्ति को पार्स करने की तुलना में थोड़ा अधिक समझ रहे हैं - जो ज्यादातर मामलों में सटीक नहीं है।

मैं गैर-तकनीकी उपयोगकर्ताओं के लिए अपने C ++ GUI एप्लिकेशन में सरल "डेटा-फ़िल्टर" भाषा बनाने के लिए Boost :: Spirit का उपयोग कर रहा हूं। भाषा सादे अंग्रेजी के लिए बहुत ही अनुकूल है और एएसटी में पार्स-सक्षम है। मेरा अनुरोध है कि इस प्रक्रिया को यथासंभव उपयोगकर्ता के अनुकूल बनाया जाए, इसलिए मैं CLang- जैसे त्रुटि संदेश ("अपरिचित 'टोकन') प्रदान करना चाहता हूं, क्या आपका मतलब 'टोकन'?" और स्वतः पूर्णता है।

जगह में सवाल यह है कि दोनों लक्ष्यों के लिए संभावित टोकन सूची बनाने के लिए बूस्ट :: स्पिरिट ग्रामर का उपयोग कैसे करें (मैं पहली आवश्यकता को पूरा करने के लिए सरल स्ट्रिंग दूरी एल्गोरिथ्म का उपयोग करूंगा)?

मेरे विचार अब तक:

  • पार्सर से प्राप्त टोकन स्रोत में स्रोत स्ट्रीम में स्थिति और लंबाई जोड़ें।
  • व्याकरण में विशेष अमान्य टोकन जोड़ें, जो किसी भी चीज़ से मेल खाएगा ... अच्छी तरह से ... मान्य नहीं :-)
  • यदि उपयोगकर्ता ctrl + space दबाता है, तो AST का निर्माण करें (अवैध टोकन के साथ पेड़ हमेशा बिल्ड करने योग्य होगा), तो वर्तमान कर्सर स्थिति के अंदर टोकन की तलाश करें
  • सभी संभव टोकन पर साधारण मिलानकर्ता का उपयोग करें (मेरे पास टोकन सूची है) और सुझावों की एक सूची तैयार करें

इस समाधान के साथ समस्या यह है कि सुझाव उन टोकन को भी सुझाएगा जो दिए गए स्थान के लिए अमान्य हैं। और अगर मैं (और मैं करूँगा) पहचान योग्य पहचानकर्ता, मेरे हाथ में बहुत बड़ी समस्या है ...

एक और बाधा: मैं केवल एक ही स्थान पर परिभाषित इस भाषा के लिए व्याकरण रखना चाहता हूं; अगर व्याकरण बदलता है, तो मैं चाहता हूं कि पुनर्मूल्यांकन के बाद इस परिवर्तन के बारे में पता होना चाहिए


जिज्ञासा से बाहर, मैंने अवधारणा को आजमाने का फैसला किया।

यहाँ मेरा प्रयास है।

योजना

फ़ंक्शन कॉल के साथ अंकगणितीय अभिव्यक्तियों को पार्स करते हैं।

अब, हम संभावित अज्ञात पहचानकर्ताओं के साथ पार्स (आंशिक) अभिव्यक्ति करना चाहते हैं।

अपूर्ण अभिव्यक्तियों के मामले में, हम इसे पूरा करने के लिए न्यूनतम टोकन "इम्प्लीमेंट" करना चाहते हैं (और संभवतः जारी रखने के लिए)।

अज्ञात पहचानकर्ताओं के मामले में, हम ज्ञात पहचानकर्ताओं को डोमेन (या तो चर या कार्यों) में फ़ज़ी-मैच करना चाहते हैं और संभावना कम होने के क्रम में उन्हें रैंक करते हैं।

आधार परिभाषाएँ

आइए यह तय करके शुरू करें कि हम चाहते हैं कि हमारा इनपुट मेमोरी में हो, इसलिए हम string_view s का उपयोग करके स्थानों / सबस्ट्रिंग का उल्लेख कर सकते हैं:

#include <boost/utility/string_view.hpp>

using Source = boost::string_view;
using Location = Source::const_iterator;

समापन संकेत

एएसटी के अलावा, हम चाहते हैं कि हमारा पार्सर पूरा होने के संकेत उत्पन्न करे (अंतर्निहित पूर्ण टोकन और सुझाव)

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

इसके अलावा, चलो एक त्वरित और गंदे फजी पहचानकर्ता मिलान स्कोरिंग फ़ंक्शन को कोड करते हैं।

मैं एक सरल तुल्यकालन के लिए चुना है कि तुलना

  • उत्तरोत्तर अक्षरों के समान रन स्कोर, और
  • इनपुट से अक्षर लंघन करने वाले उम्मीदवारों के चरित्रों को छोड़ देने के पक्ष में हैं (जिसका अर्थ है कि adj_diff लिए एक अच्छा फ़ज़ी मैच है, भले ही अभ्यर्थी से वर्णों को छोड़ दिया गया हो, लेकिन adj_qqq_diff खराब है क्योंकि इनपुट से qqq मिलान नहीं किया जा सकता)
  • एल्गोरिदम पुनरावर्ती और आवंटन के बिना किया जाता है
  • मिलान होने पर पहले वर्णों को बढ़ावा मिलता है (पहले आह्वान पर rate=1 )
    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

हम देखेंगे कि व्याकरण में इसका उपयोग कैसे किया जाता है।

एएसटी

एक रन-ऑफ-द-मिल एएसटी जो बाइनरी एक्सप्रेशन, स्ट्रिंग / न्यूमेरिक शाब्दिक, चर और (नेस्टेड) ​​फ़ंक्शन कॉल कर सकता है:

#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 interesting हैं

            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) वास्तव में करता है, और हम बाद में देखेंगे।

अभी के लिए, निरीक्षण करें कि हम अर्ध क्रिया में Location बनाने के लिए एक (खाली) स्रोत iterator_range प्राप्त करने के लिए raw[eps] करते हैं।

पहचानकर्ता लुकअप

हम Domain सदस्यों _variables और _functions में "प्रतीक तालिका" _functions :

        using Domain = qi::symbols<char>;
        Domain _variables, _functions;

फिर हम कुछ नियमों की घोषणा करते हैं जो दोनों में से कोई भी लुकअप कर सकें:

        // domain identifier lookups
        qi::_r1_type _domain;
        qi::rule<It, Ast::Identifier(Domain const&)> maybe_known, known, unknown;

इसी घोषणाओं को शीघ्र ही दिखाया जाएगा।

चर बहुत सरल हैं:

        variable   = maybe_known(phx::ref(_variables));

कॉल पेचीदा हैं। यदि कोई नाम अज्ञात है, तो हम यह नहीं मान सकते हैं कि यह एक फ़ंक्शन का अर्थ है जब तक कि यह '(' वर्ण '(' द्वारा पीछा नहीं किया जाता है। हालांकि, यदि कोई पहचानकर्ता एक ज्ञात फ़ंक्शन नाम है, तो हम चाहते हैं कि यह भी हो (यूएक्स देता है) स्वतः पूर्णता की उपस्थिति जहां उपयोगकर्ता टाइप करता है, यह अगले चरित्र को ( जादुई) होने का सुझाव देता है।

        // 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(')');

यह सभी known , unknown और maybe_known 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)];
            }

डीबग, पूर्वनिर्धारित चर / कार्य

शेष लाल टेप का एक सा है:

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

ध्यान दें कि यह स्थान के अनुसार आदेश देता है (जो UX को आसान बनाता है) और पता लगाता है कि पिछले निहित टोकन उसी स्थान पर रहते थे, जिस स्थिति में हम बस इसके लिए अपील करते हैं।

अब तक यह बहुत आश्चर्य की बात नहीं होगी कि अज्ञात पहचानकर्ताओं के लिए प्रासंगिक सुझाव देना भी एक फीनिक्स अभिनेता है:

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

बस इतना ही। यदि यह अधिक जटिल लगता है, ऐसा इसलिए है क्योंकि यह बहुत अधिक करता है: यह सभी उम्मीदवारों को पूर्ण रूप से स्कोर करता है, उन्हें अवरोही स्कोर द्वारा आदेश देता है और स्कोर 3 के साथ किसी भी उम्मीदवार को निकालता है।

    };
}

बोनस

आइए चीजों को थोड़ा और बदलें और ',' को तर्क सूचियों के अंदर निहित करें:

        call %= ( known(phx::ref(_functions)) // known -> imply the parens
                | &(identifier >> '(') >> unknown(phx::ref(_functions))
                ) 
            >> implied('(') 
            >> -(expression % ',')
            >> implied(')')
            ;

चलो ',' वहाँ:

            >> -(expression % (',' | !(')'|eoi) >> implied(',')))

नोट : यह पता लगाने के लिए &expression लिए अधिक समझ बनाने के लिए लग सकता है कि अभिव्यक्ति का अनुसरण करता है, इसके बजाय यह मानते हुए कि इनपुट / तर्क सूची का अंत नहीं हुआ है।

हालांकि, ऐसा करना बुरा है, क्योंकि किसी भी निहित अभिव्यक्तियां एक साइड इफेक्ट के रूप में अधिक निहित टोकन को ट्रिगर कर सकती हैं, जिससे नकली टोकन के लिए नकल हो सकती है।

यह (साइड-इफ़ेक्टेड सिमेंटिक एक्शन) मुख्य कारणों में से एक है कि मैं आमतौर पर सिमेंटिक एक्शन से बचता हूं, या उन्हें केवल नियम (उजागर) विशेषता (एस) में प्रभाव को स्टोर करने के लिए उपयोग करता हूं। बूस्ट स्पिरिट देखें : "सिमेंटिक क्रियाएं बुराई हैं"?

परीक्षण चालक

यह पोस्ट कुछ अच्छे परीक्षण मामलों के बिना कुछ भी नहीं होगी। तो यहाँ जाता है:

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

ध्यान दें कि, पहले इनपुट ( "" ) के अलावा सब कुछ हेयुरिस्टिक रूप से किसी प्रकार की अभिव्यक्ति के रूप में है! अंतिम को यह दिखाने के लिए डिज़ाइन किया गया है कि सभी पैरामीटर सूचियों को कैसे निहित किया गया है क्योंकि print , sqrt और sin ज्ञात कार्य हैं। फिर कुछ ',' निहित हैं, इससे पहले कि बिना तार के शाब्दिक और शेष कोष्ठक बंद हो जाएं। यहां (गैर-डीबग) आउटपुट है:

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

Ost बूस्ट स्पिरिट स्किपर मुद्दे







boost-spirit