regex - probar - regular expression creator online

Ejemplo corto de expresión regular convertida a una máquina de estado?

Question

En el podcast Stack Overflow # 36 ( http://blog.stackoverflow.com/2009/01/podcast-36/ ), se expresó esta opinión: una vez que comprenda lo fácil que es configurar una máquina de estado, nunca intente utilizar una expresión regular inapropiadamente nunca más.

He hecho un montón de búsqueda. He encontrado algunos artículos académicos y otros ejemplos complicados, pero me gustaría encontrar un ejemplo simple que me ayude a entender este proceso. Uso muchas expresiones regulares, y me gustaría asegurarme de nunca volver a utilizar una "inapropiada".

Answer 1

Estoy seguro de que alguien tiene mejores ejemplos, pero puedes consultar esta publicación de Phil Haack , que tiene un ejemplo de una expresión regular y una máquina de estado haciendo lo mismo (hay una publicación anterior con algunos ejemplos de expresiones regulares más allí también) Creo..)

Verifique el "HenriFormatter" en esa página.

Answer 2

No sé qué documentos académicos ya ha leído, pero realmente no es tan difícil de entender cómo implementar una máquina de estados finitos. Hay algunas matemáticas interesantes, pero la idea es realmente muy trivial de entender. La forma más fácil de entender un FSM es a través de entrada y salida (en realidad, esto comprende la mayor parte de la definición formal, que no describiré aquí). Un "estado" es básicamente describir un conjunto de entradas y salidas que han ocurrido y pueden ocurrir desde un cierto punto.

Las máquinas de estado finito son más fáciles de entender a través de diagramas. Por ejemplo:

texto alternativo http://img6.imageshack.us/img6/7571/mathfinitestatemachinedco3.gif

Todo lo que se está diciendo es que si comienzas en algún estado q0 (el que tiene el símbolo de Inicio al lado) puedes ir a otros estados. Cada estado es un círculo. Cada flecha representa una entrada o salida (dependiendo de cómo lo mires). Otra forma de pensar en una máquina de estados finitos es en términos de entrada "válida" o "aceptable". Hay ciertas cadenas de salida que NO son posibles ciertas máquinas de estados finitos; esto le permitirá "emparejar" expresiones.

Ahora supongamos que comienzas en q0. Ahora, si ingresas un 0 irás al estado q1. Sin embargo, si ingresas un 1 irás al estado q2. Puedes ver esto por los símbolos sobre las flechas de entrada / salida.

Digamos que comienzas en q0 y obtienes esta entrada

0, 1, 0, 1, 1, 1

Esto significa que ha pasado por estados (sin entrada para q0, simplemente comienza allí):

q0 -> q1 -> q0 -> q1 -> q0 -> q2 -> q3 -> q3

Traza la imagen con tu dedo si no tiene sentido. Observe que q3 vuelve a sí mismo para las dos entradas 0 y 1.

Otra forma de decir todo esto es "Si estás en el estado q0 y ves un 0, ve a q1 pero si ves un 1, ve a q2". Si realiza estas condiciones para cada estado, casi ha terminado de definir su máquina de estado. Todo lo que tienes que hacer es tener una variable de estado y luego una forma de insertar la entrada y eso es básicamente lo que está ahí.

Ok, entonces ¿por qué es esto importante con respecto a la declaración de Joel? Bueno, construir "UNA VERDADERA EXPRESIÓN REGULAR PARA REGIRLOS A TODOS" puede ser muy difícil y también difícil de mantener modificar o incluso que otros puedan volver y entender. Además, en algunos casos es más eficiente.

Por supuesto, las máquinas de estado tienen muchos otros usos. Espero que esto ayude de alguna manera pequeña. Tenga en cuenta que no me molesté en entrar en la teoría, pero hay algunas pruebas interesantes con respecto a los FSM.

Answer 3

Una forma bastante conveniente de ayudar a ver esto para usar el poco conocido marcador de REPRESENTACIÓN de python en cualquier patrón:

>>> re.compile(r''<([A-Z][A-Z0-9]*)/b[^>]*>(.*?)<//1>'', re.DEBUG)
literal 60
subpattern 1
  in
    range (65, 90)
  max_repeat 0 65535
    in
      range (65, 90)
      range (48, 57)
at at_boundary
max_repeat 0 65535
  not_literal 62
literal 62
subpattern 2
  min_repeat 0 65535
    any None
literal 60
literal 47
groupref 1
literal 62

Los números después de ''literal'' y ''rango'' se refieren a los valores enteros de los caracteres ascii con los que se supone que coinciden.

Answer 4

Claro, aunque necesitará ejemplos más complicados para comprender realmente cómo funcionan los RE. Considere la siguiente RE:

^[A-Za-z][A-Za-z0-9_]*$

que es un identificador típico (debe comenzar con alfa y puede tener cualquier cantidad de caracteres alfanuméricos y de indescisión a continuación, incluido ninguno). El siguiente pseudocódigo muestra cómo se puede hacer esto con una máquina de estados finitos:

state = FIRSTCHAR
for char in all_chars_in(string):
    if state == FIRSTCHAR:
            if char is not in the set "A-Z" or "a-z":
                error "Invalid first character"
            state = SUBSEQUENTCHARS
            next char
    if state == SUBSEQUENTCHARS:
            if char is not in the set "A-Z" or "a-z" or "0-9" or "_":
                error "Invalid subsequent character"
            state = SUBSEQUENTCHARS
            next char

Ahora, como dije, este es un ejemplo muy simple. No muestra cómo hacer coincidencias ambiciosas / no aleatorias, retroceder, hacer coincidir dentro de una línea (en lugar de toda la línea) y otras características más esotéricas de las máquinas de estado que son fácilmente manejadas por la sintaxis de RE.

Es por eso que los RE son tan poderosos. El código de máquina de estado finito real requerido para hacer lo que un RE de una línea puede hacer generalmente es muy largo y complejo.

Lo mejor que puede hacer es tomar una copia de algún código lex / yacc (o equivalente) para un lenguaje simple específico y ver el código que genera. No es bonito (no tiene que ser así porque los humanos no deben leerlo, se supone que deben mirar el código lex / yacc), pero puede darte una mejor idea de cómo funcionan.

Answer 5

Haga su propio sobre la marcha!

http: //osteele.com/tools/reanimator/ ???

Esta es una herramienta realmente bien conjunta que visualiza expresiones regulares como FSM. No es compatible con la sintaxis que encontrará en los motores de expresiones regulares del mundo real, pero sí lo suficiente como para entender exactamente lo que está sucediendo.

Answer 6

¿La pregunta es "¿Cómo elijo los estados y las condiciones de transición?" O "¿Cómo implemento mi máquina de estados abstractos en Foo?"

¿Cómo elijo los estados y las condiciones de transición?

Usualmente uso FSM para problemas bastante simples y los elijo intuitivamente. En mi respuesta a otra pregunta sobre expresiones regulares , simplemente miré el problema de análisis sintáctico como uno Inside o outside un par de etiquetas, y escribí las transiciones desde allí (con un estado inicial y final para mantener la implementación limpia).

¿Cómo implemento mi máquina de estado abstracto en Foo?

Si su lenguaje de implementación admite una estructura como la declaración de switch c , entonces enciende el estado actual y procesa la entrada para ver qué acción y / o transición también realizarán a continuación.

Sin estructuras parecidas a switch , o si son deficientes de alguna manera, usted if estilo ramificación. Ugh.

Escrito todo en un solo lugar en c el ejemplo que vinculaba se vería así:

token_t token;
state_t state=BEGIN_STATE;
do {
   switch ( state.getValue() ) {
   case BEGIN_STATE;
      state=OUT_STATE;
      break;
   case OUT_STATE:
      switch ( token.getValue() ) {
         case CODE_TOKEN:
            state = IN_STATE;
            output(token.string());
            break;
         case NEWLINE_TOKEN;
            output("<break>");
            output(token.string());
            break;
         ...
      }
      break;
   ...
   }
} while (state != END_STATE);

que es bastante desordenado, por lo que usualmente arranco los casos de state para separar las funciones.