c++ dsl

c++ - ¿Cómo analizar texto para un DSL en tiempo de compilación?



(3)

Sí. Está bien. Quiero poder pegar una expresión como:

"a && b || c"

directamente en el código fuente como una cadena:

const std::string expression_text("a && b || c");

Crea una estructura relajada y evaluada con ella:

Expr expr(magical_function(expression_text));

luego, más adelante, evalúe la sustitución en valores conocidos:

evaluate(expr, a, b, c);

Me gustaría expandir este pequeño DSL más tarde, así que hacer algo un poco más complicado usando alguna sintaxis que no sea de C ++, así que no puedo simplemente codificar mi expresión de la manera más simple. El caso de uso es que podré copiar y pegar la misma lógica de otro módulo utilizado en un área de desarrollo diferente para otro idioma en lugar de tener que adaptarla cada vez que siga la sintaxis de C ++.

Si alguien puede comenzar, al menos, cómo hacer el concepto simple anterior de 1 expresión y 2 operadores booleanos que sería realmente apreciado.

Nota: publiqué esta pregunta debido a los comentarios de otra pregunta que publiqué: cómo analizar la entrada DSL a la plantilla de expresión de alto rendimiento . Aquí realmente quería una respuesta a un problema ligeramente diferente, pero los comentarios provocaron esta pregunta específica que pensé que valía la pena publicar ya que realmente vale la pena documentar las posibles respuestas.

Descargo de responsabilidad: no sé nada sobre metaparse, y muy poco sobre proto. El siguiente código es mi intento (principalmente a través de prueba y error) para modificar este ejemplo y hacer algo similar a lo que desea.

El código se puede dividir fácilmente en varias partes:

1. La gramática.

1.1 Definiciones de tokens

typedef token < lit_c < ''a'' > > arg1_token; typedef token < lit_c < ''b'' > > arg2_token; typedef token < lit_c < ''c'' > > arg3_token;

  • token<Parser> :
    token es un combinador de analizador que usa Parser para analizar la entrada y luego consume (y descarta) todos los espacios en blanco después. El resultado del análisis es el resultado de Parser .
  • lit_c<char> :
    lit_c coincide con el char específico y el resultado del análisis es el mismo carácter. En la gramática este resultado se anula por el uso de always .

typedef token < keyword < _S ( "true" ), bool_<true> > > true_token; typedef token < keyword < _S ( "false" ), bool_<false> > > false_token;

  • keyword<metaparse_string,result_type=undefined> :
    la palabra clave coincide con la metaparse_string específica ( _S("true") devuelve metaparse::string<''t'',''r'',''u'',''e''> que es lo que metaparse usa internamente para hacer su magia) y el resultado de el análisis es tipo de result_type .

typedef token < keyword < _S ( "&&" ) > > and_token; typedef token < keyword < _S ( "||" ) > > or_token; typedef token < lit_c < ''!'' > > not_token;

En el caso de and_token y or_token el resultado no está definido y en la gramática a continuación se ignora.

1.2 "Reglas" de la gramática

struct paren_exp;

El primer paren_exp se paren_exp hacia adelante.

typedef one_of< paren_exp, transform<true_token, build_value>, transform<false_token, build_value>, always<arg1_token, arg<0> >, always<arg2_token, arg<1> >, always<arg3_token, arg<2> > > value_exp;

  • one_of<Parsers...> :
    one_of es un combinador de analizador que intenta hacer coincidir la entrada con uno de sus parámetros. El resultado es lo que devuelve el primer analizador que coincide.
  • transform<Parser,SemanticAction> :
    transform es un combinador de analizador que coincide con Parser . El tipo de resultado es el tipo de resultado de Parser transformado por SemanticAction .

  • always<Parser,NewResultType> :
    coincide con Parser , devuelve NewResultType .

    La regla de espíritu equivalente sería:

    value_exp = paren_exp [ _val=_1 ] | true_token [ _val=build_value(_1) ] | false_token [ _val=build_value(_1) ] | argN_token [ _val=phx::construct<arg<N>>() ];

typedef one_of< transform<last_of<not_token, value_exp>, build_not>, value_exp > not_exp;

  • last_of<Parsers...> :
    last_of coincide con cada uno de los Parsers en secuencia y su tipo de resultado es el tipo de resultado del último analizador.

    La regla del espíritu equivalente sería:

    not_exp = (omit[not_token] >> value_exp) [ _val=build_not(_1) ] | value_exp [ _val=_1 ];

typedef foldl_start_with_parser< last_of<and_token, not_exp>, not_exp, build_and > and_exp; // and_exp = not_exp >> *(omit[and_token] >> not_exp); typedef foldl_start_with_parser< last_of<or_token, and_exp>, and_exp, build_or > or_exp; // or_exp = and_exp >> *(omit[or_token] >> and_exp);

  • foldl_start_with_parser<RepeatingParser,InitialParser,SemanticAction> :
    este combinador de analizador coincide con InitialParser y luego con RepeatingParser varias veces hasta que falla. El tipo de resultado es el resultado de mpl::fold<RepeatingParserSequence, InitialParserResult, SemanticAction> , donde RepeatingParserSequence es una secuencia de los tipos de resultados de cada aplicación de RepeatingParser . Si RepeatingParser nunca tiene éxito, el tipo de resultado es simplemente InitialParserResult .

    Creo (xd) que la regla del espíritu equivalente sería:

    or_exp = and_exp[_a=_1] >> *( omit[or_token] >> and_exp [ _val = build_or(_1,_a), _a = _val ]);

struct paren_exp: middle_of < lit_c < ''('' > , or_exp, lit_c < '')'' > > {}; // paren_exp = ''('' >> or_exp >> '')'';

  • middle_of<Parsers...> :
    esto coincide con la secuencia de Parsers y el tipo de resultado es el resultado del analizador que está en el medio.

typedef last_of<repeated<space>, or_exp> expression; //expression = omit[*space] >> or_exp;

  • repeated<Parser>
    este combinador de analizadores intenta hacer coincidir Parser varias veces. El resultado es una secuencia de los tipos de resultados de cada aplicación del analizador, si el analizador falla en su primer intento, el resultado es una secuencia vacía. Esta regla simplemente elimina cualquier espacio en blanco inicial.

typedef build_parser<entire_input<expression> > function_parser;

Esta línea crea una metafunción que acepta una cadena de entrada y devuelve el resultado del análisis sintáctico.

2. Construcción de la expresión.

Veamos un ejemplo de recorrido de la construcción de una expresión. Esto se hace en dos pasos: primero, la gramática construye un árbol que depende de build_or , build_and , build_value , build_not y arg<N> . Una vez que obtenga ese tipo, puede obtener la expresión proto utilizando el typedef proto_type .

"a ||! b"

Comenzamos en or_expr :

  • or_expr : Probamos su InitialParser que es and_expr .
    • and_expr : Probamos su InitialParser que no not_expr .
      • not_expr : not_token falla, así que probamos value_expr .
        • value_expr : arg1_token tiene éxito. El tipo de retorno es arg<0> y volvemos a not_expr .
      • not_expr : el tipo de retorno no se modifica en este paso. Volvemos a and_expr .
    • and_expr : Probamos su RepeatingParser, falla. and_expr tiene éxito y su tipo de devolución es el tipo de retorno de InitialParser: arg<0> . Volvemos a or_expr .
    • or_expr : Probamos su RepeatingParser, o _token matches, probamos con and_expr .
    • and_expr : Probamos su InitialParser not_expr .
      • not_expr : not_token tiene éxito, intentamos value_expr .
        • value_expr : arg2_token tiene éxito. El tipo de retorno es arg<1> y volvemos a not_expr .
      • not_expr : el tipo de retorno se modifica mediante la transformación usando build_not: build_not :: apply <arg <1>> . Volvemos a and_expr .
    • and_expr : Probamos su RepeatingParser, falla. and_expr tiene éxito y devuelve build_not :: apply <arg <1>> . Regresamos a or_expr .
  • or_expr : RepeatingParser ha tenido éxito, foldlp usa build_or en build_not::apply< arg<1> > y arg<0> , obteniendo build_or::apply< build_not::apply< arg<1> >, arg<0> > .

Una vez que tenemos este árbol construido, obtenemos su proto_type :

build_or::apply< build_not::apply< arg<1> >, arg<0> >::proto_type; proto::logical_or< arg<0>::proto_type, build_not::apply< arg<1> >::proto_type >::type; proto::logical_or< proto::terminal< placeholder<0> >::type, build_not::apply< arg<1> >::proto_type >::type; proto::logical_or< proto::terminal< placeholder<0> >::type, proto::logical_not< arg<1>::proto_type >::type >::type; proto::logical_or< proto::terminal< placeholder<0> >::type, proto::logical_not< proto::terminal< placeholder<1> >::type >::type >::type;

Código de muestra completo ( ejecutándose en Wandbox )

#include <iostream> #include <vector> #include <boost/metaparse/repeated.hpp> #include <boost/metaparse/sequence.hpp> #include <boost/metaparse/lit_c.hpp> #include <boost/metaparse/last_of.hpp> #include <boost/metaparse/middle_of.hpp> #include <boost/metaparse/space.hpp> #include <boost/metaparse/foldl_start_with_parser.hpp> #include <boost/metaparse/one_of.hpp> #include <boost/metaparse/token.hpp> #include <boost/metaparse/entire_input.hpp> #include <boost/metaparse/string.hpp> #include <boost/metaparse/transform.hpp> #include <boost/metaparse/always.hpp> #include <boost/metaparse/build_parser.hpp> #include <boost/metaparse/keyword.hpp> #include <boost/mpl/apply_wrap.hpp> #include <boost/mpl/front.hpp> #include <boost/mpl/back.hpp> #include <boost/mpl/bool.hpp> #include <boost/proto/proto.hpp> #include <boost/fusion/include/at.hpp> #include <boost/fusion/include/make_vector.hpp> using boost::metaparse::sequence; using boost::metaparse::lit_c; using boost::metaparse::last_of; using boost::metaparse::middle_of; using boost::metaparse::space; using boost::metaparse::repeated; using boost::metaparse::build_parser; using boost::metaparse::foldl_start_with_parser; using boost::metaparse::one_of; using boost::metaparse::token; using boost::metaparse::entire_input; using boost::metaparse::transform; using boost::metaparse::always; using boost::metaparse::keyword; using boost::mpl::apply_wrap1; using boost::mpl::front; using boost::mpl::back; using boost::mpl::bool_; struct build_or { typedef build_or type; template <class C, class State> struct apply { typedef apply type; typedef typename boost::proto::logical_or<typename State::proto_type, typename C::proto_type >::type proto_type; }; }; struct build_and { typedef build_and type; template <class C, class State> struct apply { typedef apply type; typedef typename boost::proto::logical_and<typename State::proto_type, typename C::proto_type >::type proto_type; }; }; template<bool I> struct value //helper struct that will be used during the evaluation in the proto context {}; struct build_value { typedef build_value type; template <class V> struct apply { typedef apply type; typedef typename boost::proto::terminal<value<V::type::value> >::type proto_type; }; }; struct build_not { typedef build_not type; template <class V> struct apply { typedef apply type; typedef typename boost::proto::logical_not<typename V::proto_type >::type proto_type; }; }; template<int I> struct placeholder //helper struct that will be used during the evaluation in the proto context {}; template<int I> struct arg { typedef arg type; typedef typename boost::proto::terminal<placeholder<I> >::type proto_type; }; #ifdef _S #error _S already defined #endif #define _S BOOST_METAPARSE_STRING typedef token < keyword < _S ( "&&" ) > > and_token; typedef token < keyword < _S ( "||" ) > > or_token; typedef token < lit_c < ''!'' > > not_token; typedef token < keyword < _S ( "true" ), bool_<true> > > true_token; typedef token < keyword < _S ( "false" ), bool_<false> > > false_token; typedef token < lit_c < ''a'' > > arg1_token; typedef token < lit_c < ''b'' > > arg2_token; typedef token < lit_c < ''c'' > > arg3_token; struct paren_exp; typedef one_of< paren_exp, transform<true_token, build_value>, transform<false_token, build_value>, always<arg1_token, arg<0> >, always<arg2_token, arg<1> >, always<arg3_token, arg<2> > > value_exp; //value_exp = paren_exp | true_token | false_token | arg1_token | arg2_token | arg3_token; typedef one_of< transform<last_of<not_token, value_exp>, build_not>, value_exp> not_exp; //not_exp = (omit[not_token] >> value_exp) | value_exp; typedef foldl_start_with_parser < last_of<and_token, not_exp>, not_exp, build_and > and_exp; // and_exp = not_exp >> *(and_token >> not_exp); typedef foldl_start_with_parser < last_of<or_token, and_exp>, and_exp, build_or > or_exp; // or_exp = and_exp >> *(or_token >> and_exp); struct paren_exp: middle_of < lit_c < ''('' > , or_exp, lit_c < '')'' > > {}; //paren_exp = lit(''('') >> or_exp >> lit(''(''); typedef last_of<repeated<space>, or_exp> expression; //expression = omit[*space] >> or_exp; typedef build_parser<entire_input<expression> > function_parser; template <typename Args> struct calculator_context : boost::proto::callable_context< calculator_context<Args> const > { calculator_context ( const Args& args ) : args_ ( args ) {} // Values to replace the placeholders const Args& args_; // Define the result type of the calculator. // (This makes the calculator_context "callable".) typedef bool result_type; // Handle the placeholders: template<int I> bool operator() ( boost::proto::tag::terminal, placeholder<I> ) const { return boost::fusion::at_c<I> ( args_ ); } template<bool I> bool operator() ( boost::proto::tag::terminal, value<I> ) const { return I; } }; template <typename Args> calculator_context<Args> make_context ( const Args& args ) { return calculator_context<Args> ( args ); } template <typename Expr, typename ... Args> int evaluate ( const Expr& expr, const Args& ... args ) { return boost::proto::eval ( expr, make_context ( boost::fusion::make_vector ( args... ) ) ); } #ifdef LAMBDA #error LAMBDA already defined #endif #define LAMBDA(exp) apply_wrap1<function_parser, _S(exp)>::type::proto_type{} int main() { using std::cout; using std::endl; cout << evaluate ( LAMBDA ( "true&&false" ) ) << endl; cout << evaluate ( LAMBDA ( "true&&a" ), false ) << endl; cout << evaluate ( LAMBDA ( "true&&a" ), true ) << endl; cout << evaluate ( LAMBDA ( "a&&b" ), true, false ) << endl; cout << evaluate ( LAMBDA ( "a&&(b||c)" ), true, false, true ) << endl; cout << evaluate ( LAMBDA ( "!a&&(false||(b&&!c||false))" ), false, true, false ) << endl; } /*int main(int argc , char** argv) { using std::cout; using std::endl; bool a=false, b=false, c=false; if(argc==4) { a=(argv[1][0]==''1''); b=(argv[2][0]==''1''); c=(argv[3][0]==''1''); } LAMBDA("a && b || c") expr; cout << evaluate(expr, true, true, false) << endl; cout << evaluate(expr, a, b, c) << endl; return 0; }*/

Durante mucho tiempo, el análisis en tiempo de compilación ha significado el uso de una meta programación de plantillas, que parece ser un ruido de línea para la mayoría de los programadores principiantes e incluso intermedios de C ++.

Sin embargo, con C ++ 11 obtuvimos constexpr y en C ++ 14, se eliminaron muchas restricciones a constexpr. C ++ 17 incluso hace algunas de las cosas de la biblioteca estándar constexpr.

Mientras intentaba aprender C ++ moderno y avanzado, decidí escribir un analizador de HTML en tiempo de compilación. La idea era crear un motor de plantillas HTML rápido.

El código completo se puede encontrar aquí: https://github.com/rep-movsd/see-phit

Explicaré brevemente las cosas que aprendí al hacer que esto funcione.

Manejo de estructuras dinámicas de datos.

Necesitaba analizar un const char * y convertirlo en un árbol de múltiples vías, pero la asignación dinámica es un no-no en constexpr land.

¿La solución? Utilice una matriz de nodos, con índices que apuntan a niños y hermanos. ¡Esencialmente cómo podría hacerlo en FORTRAN!

La advertencia es que su lista de nodos debe ser inicialmente de un tamaño fijo. Manteniéndolo muy grande parecía hacer una compilación lenta de gcc en una gran cantidad. Si termina pasando el final de una matriz, el compilador lanzará un error. Escribí una pequeña std :: array como envoltorio que es completamente conciente.

Parsing

¡Casi todo el código estándar que escriba para el análisis de tiempo de ejecución funcionará en tiempo de compilación! Bucles, recursiones, condicionales, todo funciona perfectamente.

Un problema fue: cómo representar cadenas? El uso del enfoque mencionado anteriormente - una variedad de caracteres - es una forma muy hambrienta y tediosa de hacer las cosas. Afortunadamente en mi caso, todo lo que siempre necesité fueron simplemente subcadenas de la entrada const char * original. Así que escribí un pequeño constexpr string_view como clase que solo contiene punteros al inicio y al final del token analizado relevante. Crear nuevas cadenas literales es solo una cuestión de convertir estas vistas en un const char * literal.

Error al reportar

La forma básica de manejar los errores en el código constexpr es llamar a una función que no sea constexpr: el compilador detiene e imprime la línea ofensiva, que puede contener fácilmente una cadena de error.

Sin embargo, quería más: quería que el analizador mostrara también la fila y la columna. Luché por un tiempo y terminé pensando que era imposible. Pero volví y probé todo lo que pude pensar. Finalmente encontré una manera que hace que gcc imprima 2 números y un mensaje de descripción de error. Básicamente, implica crear una plantilla con dos parámetros enteros (fila y columna) cuyos valores provienen del analizador constexpr.

Actuación

No pude encontrar claramente ningún patrón en cuanto a qué tipo de código restringido tiende a desacelerar al compilador, pero el rendimiento predeterminado no es para nada lamentable. Puedo analizar un archivo HTML de 1000 nodos en aproximadamente 1,5 segundos en gcc.

clang es un poco más rápido.

Tengo la intención de escribir una descripción más detallada de cómo funciona el código en la wiki del repositorio github: estad atentos.

Si bien es técnicamente posible hacer ese tipo de metaprogramación con plantillas o constexpr, no recomendaría ese enfoque. Terminarás con una gran cantidad de código muy complejo. Va a ser difícil de depurar y costoso de mantener y extender.

En su lugar, use cualquier otro lenguaje para generar código C ++ a partir de sus expresiones.

Si está utilizando Visual Studio, una buena forma integrada es plantillas de texto T4. Aquí hay más detalles .

De lo contrario, use cualquier otro idioma disponible en su plataforma, por ejemplo, hice algo similar en Python.