c++ - uso - expresiones regulares tutorial

¿Cómo obtener el AST de una cadena de expresión regular?

Question

¿Cómo puedo obtener el árbol de sintaxis abstracta (AST) de una expresión regular (en C ++)?

Por ejemplo,

 (XYZ)|(123)

Debería ceder un árbol de:

        |
      /   /
    .       .
   / /     / /
  .   Z   .   3    
 / /     / /   
X  Y     1 2

¿Hay un boost::spirit gramática boost::spirit para analizar patrones de expresión regulares? La biblioteca boost::regex debería tenerlo, pero no lo encontré. ¿Hay otras herramientas de código abierto disponibles que me darían la representación abstracta de una expresión regular?

Answer 1

Calculo que Boost Xpressive debe poder "casi" hacer esto fuera de la caja.

xpressive es una biblioteca avanzada de plantillas de expresiones regulares orientada a objetos para C ++. Las expresiones regulares se pueden escribir como cadenas que se analizan en tiempo de ejecución, o como plantillas de expresiones que se analizan en tiempo de compilación. Las expresiones regulares pueden referirse entre sí y recursivamente a sí mismas, lo que te permite construir gramáticas arbitrariamente complicadas a partir de ellas.

Veré si puedo confirmar (con una pequeña muestra).

Otros pensamientos incluyen el uso de Boost Spirit con la facilidad genérica de utree para "almacenar" el AST. Tendría que reproducir una gramática (que es relativamente simple para los subconjuntos comunes de sintaxis Regex), por lo que podría significar más trabajo.

Informe de progreso 1

Mirando a Xpressive, hice algunas incursiones. Conseguí algunas imágenes bonitas utilizando la gran pantalla gráfica de datos de DDD. Pero no es lo suficientemente bonita.

Luego exploré el lado del ''código'' más: Xpressive se basa en Boost Proto. Utiliza Proto para definir un DSEL que modela expresiones regulares directamente en código C ++. Proto genera el árbol de expresiones (AST genérico, si lo desea) completamente a partir del código C ++ (sobrecargando todos los operadores posibles). La biblioteca (Xpressive, en este caso) necesita definir la semántica caminando por el árbol y, por ejemplo,

• la construcción de un árbol de expresión específica de dominio
• Anotándolo / decorándolo con información semántica.
• posiblemente tomando acción semántica directamente (por ejemplo, cómo Boost Spirit realiza acciones semánticas en Qi y Karma ¹ )

Como puede ver, el cielo es realmente el límite allí, y las cosas se ven inquietantemente similares a las macros del compilador como en Boo, Nemerle, Lisp, etc.

Visualizando Expresión Trres

Ahora, los árboles de expresión de Boost Proto se pueden visualizar genéricamente :

Trabajando con el ejemplo de Expressive C ++: jugando con Sintaxis , extendí ligeramente el ejemplo "Hello World" de Xpressive para mostrar el árbol de expresiones:

#include <iostream>
#include <boost/xpressive/xpressive.hpp>
#include <boost/proto/proto.hpp>

using namespace boost::xpressive;

int main()
{
    std::string hello( "hello world!" );

    sregex rex = sregex::compile( "(//w+) (//w+)!" );

    // equivalent proto based expression
    rex = (s1= +_w) >> '' '' >> (s2= +_w) >> ''!'';
    boost::proto::display_expr( (s1= +_w) >> '' '' >> (s2= +_w) >> ''!'');

    smatch what;

    if( regex_match( hello, what, rex ) )
    {
        std::cout << what[0] << ''/n''; // whole match
        std::cout << what[1] << ''/n''; // first capture
        std::cout << what[2] << ''/n''; // second capture
    }

    return 0;
}

La salida de la cual está cerca de (tenga en cuenta los nombres typeid específicos de ABI del compilador ):

shift_right(
    shift_right(
        shift_right(
            assign(
                terminal(N5boost9xpressive6detail16mark_placeholderE)
              , unary_plus(
                    terminal(N5boost9xpressive6detail25posix_charset_placeholderE)
                )
            )
          , terminal( )
        )
      , assign(
            terminal(N5boost9xpressive6detail16mark_placeholderE)
          , unary_plus(
                terminal(N5boost9xpressive6detail25posix_charset_placeholderE)
            )
        )
    )
  , terminal(!)
)
hello world!
hello
world

DESCARGO DE RESPONSABILIDAD Debe darse cuenta de que esto no muestra en realidad el AST Regex, sino el árbol de expresión genérico de Proto, por lo que carece de información específica del dominio (Regex). Lo menciono porque es probable que la diferencia cause más trabajo (a menos que encuentre un gancho en las estructuras de compilación de Xpressive) para que se vuelva realmente útil para la pregunta original.

Eso es todo por ahora

Dejaré esa nota, ya que es la hora del almuerzo y estoy recogiendo a los niños, pero esto ciertamente me llamó la atención, ¡así que tengo la intención de publicar más tarde!

Conclusiones / Informe de progreso 1.0000001

Las malas noticias de inmediato: no funcionarán.

Este es el por qué. Ese descargo de responsabilidad estaba justo en el dinero. Cuando llegó el fin de semana, ya había estado pensando un poco más y "predice" que todo se descompondría justo donde lo había dejado: el AST se basa en el árbol de expresión proto (no en el regex matchable_ex ).

Este hecho se confirmó rápidamente después de una inspección de código: después de la compilación, el árbol de expresiones proto ya no está disponible para ser mostrado. Dejemos de lado cuando el basic_regex se especificó como un patrón dinámico en primer lugar (nunca hubo una proto expresión para él).

Tenía la esperanza de que la coincidencia se hubiera implementado directamente en el árbol de protoexpresión (utilizando los contextos de evaluación / evaluación de proto), pero rápidamente confirmé que este no es el caso.

Entonces, el principal punto para llevar es:

• todo esto no va a funcionar para mostrar cualquier expresión regular AST
• Lo mejor que puedes hacer con lo anterior es visualizar una proto expresión, que necesariamente tendrás que crear directamente en tu código. Esa es una manera elegante de simplemente escribir el AST manualmente en ese mismo código ...

Las observaciones ligeramente menos estrictas incluyen

• Boost Proto y Boost Expressive son bibliotecas muy interesantes (no me importó ir a pescar allí). Obviamente, he aprendido algunas lecciones importantes sobre las bibliotecas de meta-programación de plantillas, y estas bibliotecas en particular.
• Es difícil diseñar un analizador de expresiones regulares que construya un árbol de expresiones de tipo estático. De hecho, es imposible en el caso general: requeriría al compilador crear una instancia de todas las combinaciones de árbol de expresiones posibles a una cierta profundidad. Esto obviamente no sería escalable. Puede evitar eso introduciendo la composición polimórfica y utilizando la invocación polimórfica, pero esto eliminaría los beneficios de la metaprogramación de plantillas (optimización en tiempo de compilación para los tipos / especializaciones con instancias estáticas).
• Tanto Boost Regex como Boost Expressive probablemente admitirán algún tipo de expresión regular AST internamente (para respaldar la evaluación correspondiente) pero
  • no ha sido expuesto / documentado
  • no hay ninguna facilidad de visualización obvia para eso

_{¹ Incluso Spirit Lex los admite, para el caso (pero no de forma predeterminada)}

Answer 2

Me tropecé con esta pregunta de nuevo. Y decidí echar un vistazo a lo difícil que sería escribir un analizador para un subconjunto significativo de la sintaxis de expresión regular con Boost Spirit.

Así que, como de costumbre, comencé con lápiz y papel, y después de un tiempo tuve en mente algunos borradores de reglas. Tiempo para dibujar el AST análogo hasta:

namespace ast
{
    struct multiplicity 
    {
        unsigned minoccurs;
        boost::optional<unsigned> maxoccurs;
        bool greedy;

        multiplicity(unsigned minoccurs = 1, boost::optional<unsigned> maxoccurs = 1) 
            : minoccurs(minoccurs), maxoccurs(maxoccurs), greedy(true)
        { }

        bool unbounded() const { return !maxoccurs; }
        bool repeating() const { return !maxoccurs || *maxoccurs > 1; }
    };

    struct charset
    {
        bool negated;

        using range   = boost::tuple<char, char>; // from, till
        using element = boost::variant<char, range>;

        std::set<element> elements; 
        // TODO: single set for loose elements, simplify() method
    };

    struct start_of_match {};
    struct end_of_match {};
    struct any_char {};
    struct group;

    typedef boost::variant<   // unquantified expression
        start_of_match,
        end_of_match,
        any_char,
        charset,
        std::string,          // literal
        boost::recursive_wrapper<group> // sub expression
    > simple;

    struct atom               // quantified simple expression
    {
        simple       expr;
        multiplicity mult;
    };

    using sequence    = std::vector<atom>;
    using alternative = std::vector<sequence>;
    using regex       = boost::variant<atom, sequence, alternative>;

    struct group {
        alternative root;

        group() = default;
        group(alternative root) : root(std::move(root)) { }
    };
}

Este es su AST típico (58 LoC) que funciona bien con Spirit (debido a que se integra con boost mediante la variant y optional , además de tener constructores estratégicamente elegidos).

La gramática terminó siendo solo un poco más larga:

template <typename It>
    struct parser : qi::grammar<It, ast::alternative()>
{
    parser() : parser::base_type(alternative)
    {
        using namespace qi;
        using phx::construct;
        using ast::multiplicity;

        alternative = sequence % ''|'';
        sequence    = *atom;

        simple      = 
                      (group)
                    | (charset)
                    | (''.'' >> qi::attr(ast::any_char()))
                    | (''^'' >> qi::attr(ast::start_of_match()))
                    | (''$'' >> qi::attr(ast::end_of_match()))
                    // optimize literal tree nodes by grouping unquantified literal chars
                    | (as_string [ +(literal >> !char_("{?+*")) ])
                    | (as_string [ literal ]) // lone char/escape + explicit_quantifier
                    ;

        atom        = (simple >> quantifier); // quantifier may be implicit

        explicit_quantifier  =
                    // bounded ranges:
                      lit(''?'')                                   [ _val = construct<multiplicity>( 0, 1)   ]
                    | (''{''  >> uint_ >> ''}'' )                    [ _val = construct<multiplicity>(_1, _1)  ]
                    // repeating ranges can be marked non-greedy:
                    | (                                        
                          lit(''+'')                               [ _val = construct<multiplicity>( 1, boost::none) ]
                        | lit(''*'')                               [ _val = construct<multiplicity>( 0, boost::none) ]
                        | (''{''  >> uint_ >> ",}")                [ _val = construct<multiplicity>(_1, boost::none) ]
                        | (''{''  >> uint_ >> "," >> uint_ >> ''}'') [ _val = construct<multiplicity>(_1, _2)  ]
                        | ("{," >> uint_ >> ''}'' )                [ _val = construct<multiplicity>( 0, _1)  ]
                      ) >> -lit(''?'')       [ phx::bind(&multiplicity::greedy, _val) = false ]
                    ;

        quantifier = explicit_quantifier | attr(ast::multiplicity());

        charset     = ''['' 
                   >> (lit(''^'') >> attr(true) | attr(false)) // negated
                   >> *(range | charset_el)
                    > '']''
                    ;

        range       = charset_el >> ''-'' >> charset_el;

        group       = ''('' >> alternative >> '')'';

        literal     = unescape | ~char_("//+*?.^$|{()") ;

        unescape    = (''//' > char_);

        // helper to optionally unescape waiting for raw '']''
        charset_el  = !lit('']'') >> (unescape|char_);
    }

  private:
    qi::rule<It, ast::alternative()>    alternative;
    qi::rule<It, ast::sequence()>       sequence;
    qi::rule<It, ast::atom()>           atom;
    qi::rule<It, ast::simple()>         simple;
    qi::rule<It, ast::multiplicity()>   explicit_quantifier, quantifier;
    qi::rule<It, ast::charset()>        charset;
    qi::rule<It, ast::charset::range()> range;
    qi::rule<It, ast::group()>          group;
    qi::rule<It, char()>                literal, unescape, charset_el;
};

Ahora, la verdadera diversión es hacer algo con el AST. Como desea visualizar el árbol, pensé en generar el gráfico DOT desde el AST. Así que lo hice:

int main()
{
    std::cout << "digraph common {/n";

    for (std::string pattern: { 
            "abc?",
            "ab+c",
            "(ab)+c",
            "[^-a//-f-z/"//]aaaa-]?",
            "abc|d",
            "a?",
            ".*?(a|b){,9}?",
            "(XYZ)|(123)",
        })
    {
        std::cout << "// ================= " << pattern << " ========/n";
        ast::regex tree;
        if (doParse(pattern, tree))
        {
            check_roundtrip(tree, pattern);

            regex_todigraph printer(std::cout, pattern);
            boost::apply_visitor(printer, tree);
        }
    }

    std::cout << "}/n";
}

Este programa da como resultado los siguientes gráficos:

Los bordes propios representan repeticiones y el color indica si la coincidencia es codiciosa (roja) o no codiciosa (azul). Como puede ver, he optimizado un poco el AST para mayor claridad, pero (des) comentar las líneas relevantes marcará la diferencia:

Creo que no sería demasiado difícil sintonizar. Esperemos que sirva de inspiración a alguien.

Código completo en esta lista: https://gist.github.com/sehe/8678988

Answer 3

boost :: regex parece tener un analizador de descenso recursivo escrito a mano en basic_regex_parser.hpp. A pesar de que se siente muy bien como reinventar la rueda, es probable que sea más rápido al escribir la gramática en boost :: spirit, especialmente con la multitud de formatos de expresiones regulares disponibles.