Cuándo usar el generador de analizador, ¿cuándo es suficiente la expresión regular?

Question

Todavía no he llegado al campo de los lenguajes formales en informática, así que tal vez mi pregunta es tonta. Estoy escribiendo un analizador NMEA simple en C++, y tengo que elegir:

Mi primera idea fue construir manualmente una máquina de estados finitos, pero luego pensé que tal vez podría hacerlo con menos trabajo, incluso de manera más eficiente . Antes usaba expresiones regulares, pero creo que la expresión regular NMEA es muy larga y debería tomar "mucho tiempo" para que coincida.

Luego pensé en usar un generador de analizador sintáctico. Creo que todos usan el mismo método: generan una FSA. Pero no sé cuál es más eficiente. ¿Cuándo usas normalmente generadores de analizadores en lugar de expresiones regulares (creo que podrías escribir expresiones regulares en el generador de analizadores)?

Explique las diferencias, me interesan tanto la teoría como la experiencia.

Answer 1

Bueno, una regla general simple es: Si la gramática de los datos que intenta analizar es regular, use expresiones regulares. Si no lo es, las expresiones regulares aún pueden funcionar (ya que la mayoría de los motores de expresiones regulares también admiten gramáticas no regulares), pero podría ser muy doloroso (rendimiento complicado/malo).

Otro aspecto es lo que está tratando de hacer con los datos analizados. Si solo está interesado en un campo, una expresión regular probablemente sea más fácil de leer. Si necesita leer estructuras profundamente anidadas, es probable que un analizador sea más fácil de mantener.

Answer 2

Regex es un analizador sintáctico.

de Wikipedia:

Las expresiones regulares (abreviado como expresiones regulares o expresiones regulares, con formas plurales expresiones regulares, expresiones regulares, o regexen) están escritos en un lenguaje formal que puede ser interpretado por un procesador de expresiones regulares, un programa que sirve como generador de analizadores o examina texto e identifica partes que coinciden con la especificación proporcionada.

Si está revisando una lista que solo necesita ir una vez, guarde la lista en un archivo y léala desde allí. Si está revisando cosas que son diferentes cada vez, use expresiones regulares y almacene los resultados en una matriz o algo.

Es mucho más rápido de lo que supondría. He visto expresiones más grandes que esta publicación.

Agregando que puede anidar tanto como desee, en el idioma que decida codificar. Incluso podría hacerlo en secciones, para la máxima reutilización.

Answer 3

Como señala Sneakyness, puede tener una expresión regular grande y complicada que sea sorprendentemente poderosa. He visto algunos ejemplos de esto, pero ninguno fue mantenible por simples mortales. Incluso el uso de Expresso solo ayudó mucho; aún era difícil de entender y arriesgado modificar. Así que a menos que seas un sabio con una obsesión por Grep, no recomendaría esta dirección.

En su lugar, considere centrarse en la gramática y dejar que un compiler compiler haga el trabajo pesado por usted.