c++ - ¿Cómo proporcionar al usuario un proveedor con sugerencias de autocompletar para impulsar:: gramática de espíritu?

parsing autocomplete

Question

Estoy usando Boost :: Spirit para construir un lenguaje simple de "filtro de datos" en mi aplicación C ++ GUI para usuarios no técnicos. El idioma es muy similar al inglés simple y se puede analizar en AST. Se me solicita que haga el proceso lo más fácil posible para el usuario, por lo que deseo proporcionar mensajes de error similares a CLang ("tokken" no reconocido, ¿quiso decir ''token''? ") Y autocompletar.

La pregunta que se plantea es cómo usar la gramática Boost :: Spirit para generar una posible lista de tokens para ambos objetivos (utilizaré un algoritmo de distancia de cadena simple para satisfacer el primer requisito).

Mis ideas hasta ahora:

• Agregue posición y longitud en la secuencia de origen a la definición de token obtenida del analizador.
• Agregue token inválido especial a la gramática, que coincidirá con cualquier cosa ... bueno ... no válido :-)
• Si el usuario presiona ctrl + espacio, construya AST (con un token inválido, el árbol siempre se podrá construir), luego busque el token dentro de la posición actual del cursor
• Use un comparador simple en todos los tokens posibles (después de todo, tengo una lista de tokens) y prepare una lista de sugerencias

El problema con esta solución es que la sugerencia también sugerirá tokens que no son válidos para un lugar determinado. Y si agrego (y lo haré) identificadores definibles, tengo un problema mucho mayor en la mano ...

Una restricción más: quiero tener la gramática de este lenguaje definida en un solo lugar; Si la gramática cambia, quiero que el autocompletador tenga en cuenta estos cambios después de la compilación

Answer 1

El espíritu no tiene esa característica. Podría generarlo usted mismo, pero sería un esfuerzo considerable hacerlo de forma genérica (si no es imposible, debido a la integridad de NP). Quizás solo detecte un error de análisis ( on_error ) y tenga un número limitado de "opciones" de acciones: la regla del 80% debería ser muy útil.

Además, creo que el "boceto" con el análisis de ''tokens de marcador de posición no válidos'' no funcionará porque tendrá que construir suposiciones sobre el tipo de token de marcador de posición y, por lo tanto, puede no dar como resultado una expresión válida.

Tengo la sensación de que usted trata el análisis de expresiones como poco más que tokenizar, lo que no es exacto en la mayoría de los casos.

Answer 2

Por curiosidad, decidí probar el concepto.

Aquí está mi intento.

Plan

Analicemos expresiones aritméticas con llamadas a funciones.

Ahora, queremos analizar la expresión (parcial) con posibles identificadores desconocidos.

En caso de expresiones incompletas, queremos "implicar" el token mínimo para completarlo (y posiblemente continuar analizando).

En el caso de identificadores desconocidos, queremos hacer coincidir difusamente los identificadores conocidos en el dominio (ya sea variables o funciones) y clasificarlos en orden de probabilidad decreciente.

Definiciones base

Comencemos por decidir que queremos que nuestra entrada esté en la memoria, para que podamos referirnos a ubicaciones / subcadenas usando string_view s:

#include <boost/utility/string_view.hpp>

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

Sugerencias de finalización

Además del AST, queremos que nuestro analizador genere sugerencias de finalización (los tokens y sugerencias implícitas de finalización)

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

Además, codifiquemos una función de puntuación de coincidencia de identificador difuso rápido y sucio.

Opté por una sincronización simple que compara

• puntúa progresivamente las corridas de caracteres correspondientes, y
• favorece la omisión de caracteres de los candidatos sobre la omisión de los caracteres de la entrada (lo que significa que adj_diff es una buena coincidencia adj_diff la adj_diff adjacent_difference aunque los caracteres se hayan omitido del candidato, pero adj_qqq_diff es peor porque el qqq de la entrada no pudo coincidir)
• el algoritmo se realiza de forma recursiva y sin asignaciones
• los primeros caracteres reciben un impulso si coinciden ( rate=1 en la primera invocación)

    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

Veremos cómo se usa esto en la gramática.

AST

Un AST corriente que puede hacer expresiones binarias, cadenas / literales numéricos, variables y llamadas a funciones (anidadas):

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

Gramática

Lo esencial

La gramática también comienza bastante "básica":

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;

Hasta ahora todo bien: el constructor almacena una referencia a Completion::Hints& que se grabará. Todas estas reglas se han definido como qi::rule<It, Expression(), qi::space_type> .

Fichas implícitas

Ahora se pone un poco más interesante, algunas reglas aquí son lexemas¹

            number     = double_;
            identifier = raw[(alpha|''_'') >> *(alnum|''_'')];

Y algunas producciones son tolerantes a la falta de tokens de cierre:

            // imply the closing quotes
            string   %= ''"'' >> *(''//' >> char_ | ~char_(''"'')) >> implied(''"'');
            compound %= ''('' >> expression >> implied('')'');

La magia implied hace que, si falta el token de cierre esperado, se registre como una pista, y el análisis continúa:

            auto implied = [=](char ch) {
                return copy(omit[lit(ch) | raw[eps][imply(_1, ch)]]);
            };

Por supuesto, esto plantea la pregunta de qué imply(_1, ch) realmente imply(_1, ch) , y veremos más adelante.

Por ahora, observe que hacemos raw[eps] para obtener un iterator_range fuente (vacío) para construir una Location desde la acción semántica.

Búsqueda de identificadores

Almacenamos "tablas de símbolos" en los miembros del Domain _variables y _functions :

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

Luego declaramos algunas reglas que pueden hacer búsquedas en cualquiera de ellas:

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

Las declaraciones correspondientes se mostrarán en breve.

Las variables son bastante simples:

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

Las llamadas son más complicadas. Si se desconoce un nombre, no queremos asumir que implica una función a menos que esté seguido de un carácter ''('' . Sin embargo, si un identificador es un nombre de función conocido, queremos incluso implicar el ( (esto le da a UX el Apariencia de autocompletado donde cuando el usuario escribe sqrt , sugiere que el siguiente carácter sea ( mágicamente).

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

Todo se basa en known , unknown y 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)];
            }

Depurar, variables / funciones predefinidas

Queda un poco de burocracia:

            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;

Ayudantes de fénix

Comencemos con el ayudante habitual para construir nodos AST binarios:

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

Del mismo modo, podemos tener un objeto de función Phoenix para registrar caracteres implícitos:

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

Tenga en cuenta que ordena por ubicación (lo que hace que UX sea más fácil) y detecta cuándo un token implícito anterior vivía en la misma ubicación, en cuyo caso simplemente le agregamos.

Por ahora, no será una gran sorpresa que generar sugerencias relevantes para identificadores desconocidos sea también un actor de Phoenix:

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

Eso es todo. Si parece más complicado, es porque hace mucho más: puntúa a todos los candidatos de forma difusa, los ordena por puntaje descendente y elimina a los candidatos con puntaje <3.

    };
}

PRIMA

Modifiquemos las cosas un poco más y permitamos que '','' se implique dentro de las listas de argumentos:

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

Vamos a reemplazar '','' allí:

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

NOTA : Puede parecer que tiene más sentido detectar &expression para afirmar que sigue una expresión, en lugar de afirmar que no se ha alcanzado el final de la lista de entrada / argumento.

Sin embargo, hacer eso va mal, porque cualquier expresión contenida podría desencadenar más tokens implícitos como un efecto secundario, dando lugar a tokens implícitos duplicados.

Esta (acciones semánticas de efecto secundario) es una de las principales razones por las que generalmente evito las acciones semánticas, o las uso para almacenar el efecto solo en los atributos (expuestos) de la regla. Ver Boost Spirit: "¿Las acciones semánticas son malas"?

CONDUCTOR DE PRUEBA

Esta publicación no sería nada sin algunos buenos casos de prueba. Entonces aquí va:

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

Tenga en cuenta que, además de la primera entrada ( "" ), todo se analiza heurísticamente como algún tipo de expresión. El último está diseñado para mostrar cómo están implicadas todas las listas de parámetros porque print , sqrt y sin son funciones conocidas. Luego, algunos '','' están implícitos, antes de que finalmente se cierre el literal de cadena no cerrado y los paréntesis restantes. Aquí está la salida (sin depuración):

-------------- ''''
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))

Listado completo / demostración en vivo

Live On Coliru

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

¹ Aumenta los problemas del capitán espiritual