¿Debo usar un generador de analizador o debo rodar mi propio código lexer y analizador personalizado?

¿Qué ventajas y desventajas específicas de cada forma de trabajar en una gramática de lenguaje de programación?

¿Por qué / cuándo debo rodar el mío? ¿Por qué / cuándo debo usar un generador?

Hay tres opciones realmente, las tres preferibles en diferentes situaciones.

Opción 1: generadores de analizadores sintéticos, o "necesitas analizar un idioma y solo quieres que funcione, maldita sea"

Digamos que ahora se te pide que construyas un analizador para algún formato de datos antiguo. O necesita que su analizador sea rápido. O necesita que su analizador sea fácilmente mantenible.

En estos casos, probablemente sea mejor usar un generador de analizador sintáctico. No tiene que jugar con los detalles, no tiene que obtener un montón de código complicado para que funcione correctamente, simplemente escriba la gramática a la que se adherirá la entrada, escriba un código de manejo y listo: analizador instantáneo.

Las ventajas son claras:

• Es (generalmente) bastante fácil escribir una especificación, en particular si el formato de entrada no es demasiado extraño (la opción 2 sería mejor si lo fuera).
• Termina con un trabajo muy fácil de mantener que se entiende fácilmente: una definición gramatical generalmente fluye mucho más natural que el código.
• Los analizadores generados por buenos generadores de analizadores suelen ser mucho más rápidos que el código escrito a mano. El código escrito a mano puede ser más rápido, pero solo si conoce sus cosas; esta es la razón por la cual los compiladores más utilizados usan un analizador de descenso recursivo escrito a mano.

Hay una cosa que debes tener cuidado con los generadores de analizadores sintéticos: a veces pueden rechazar tus gramáticas. Para obtener una descripción general de los diferentes tipos de analizadores y cómo pueden morderte, puedes comenzar aquí . Aquí puede encontrar una descripción general de muchas implementaciones y los tipos de gramáticas que aceptan.

Opción 2: analizadores escritos a mano, o 'desea crear su propio analizador y le interesa ser fácil de usar'

Los generadores de analizadores son agradables, pero no son muy amigables para el usuario (el usuario final, no usted). Por lo general, no puede dar buenos mensajes de error, ni puede proporcionar recuperación de errores. Quizás su idioma es muy extraño y los analizadores rechazan su gramática o necesita más control del que le da el generador.

En estos casos, usar un analizador de descenso recursivo escrito a mano es probablemente el mejor. Si bien hacerlo bien puede ser complicado, tiene un control completo sobre su analizador, por lo que puede hacer todo tipo de cosas buenas que no puede hacer con generadores de analizadores, como mensajes de error e incluso recuperación de errores (intente eliminar todos los puntos y coma de un archivo C # : el compilador de C # se quejará, pero detectará la mayoría de los otros errores de todos modos, independientemente de la presencia de punto y coma).

Los analizadores escritos a mano también suelen funcionar mejor que los generados, suponiendo que la calidad del analizador sea lo suficientemente alta. Por otro lado, si no logras escribir un buen analizador, generalmente debido a (una combinación de) falta de experiencia, conocimiento o diseño, entonces el rendimiento suele ser más lento. Sin embargo, para los léxers es cierto lo contrario: los léxers generalmente generados usan búsquedas en tablas, lo que los hace más rápidos que (la mayoría) escritos a mano.

En cuanto a la educación, escribir su propio analizador le enseñará más que usar un generador. Después de todo, debe escribir un código cada vez más complicado, además de comprender exactamente cómo analiza un idioma. Por otro lado, si desea aprender a crear su propio idioma (por lo tanto, adquirir experiencia en el diseño del lenguaje), es preferible la opción 1 o la opción 3: si está desarrollando un idioma, probablemente cambie mucho, y las opciones 1 y 3 le brindan un tiempo más fácil con eso.

Opción 3: generadores de analizadores escritos a mano, o 'estás tratando de aprender mucho de este proyecto y no te importaría terminar con un ingenioso código que puedes reutilizar mucho'

Este es el camino por el que estoy caminando actualmente: escribes tu propio generador de analizador. Si bien es altamente no trivial, hacer esto probablemente te enseñará más.

Para darle una idea de lo que implica hacer un proyecto como este, le contaré sobre mi propio progreso.

El generador lexer

Primero creé mi propio generador de lexer. Por lo general, diseño software que comienza con cómo se usará el código, así que pensé en cómo quería poder usar mi código y escribí este fragmento de código (está en C #):

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a lex specification:
      //                    regex   token
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

Los pares de cadena de caracteres de entrada se convierten en una estructura recursiva correspondiente que describe las expresiones regulares que representan utilizando las ideas de una pila aritmética. Esto se convierte en un NFA (autómata finito no determinista), que a su vez se convierte en un DFA (autómata finito determinista). Luego puede hacer coincidir cadenas con el DFA.

De esta manera, obtienes una buena idea de cómo funcionan exactamente los lexers. Además, si lo hace de la manera correcta, los resultados de su generador de lexer pueden ser aproximadamente tan rápidos como las implementaciones profesionales. Tampoco pierde ninguna expresividad en comparación con la opción 2, y no mucha expresividad en comparación con la opción 1.

Implementé mi generador lexer en poco más de 1600 líneas de código. Este código hace que el trabajo anterior funcione, pero aún genera el lexer sobre la marcha cada vez que inicia el programa: voy a agregar código para escribirlo en el disco en algún momento.

Si desea saber cómo escribir su propio lexer, este es un buen lugar para comenzar.

El generador de analizadores

Luego escribe su generador de analizador. Me remito aquí nuevamente para obtener una descripción general de los diferentes tipos de analizadores: como regla general, cuanto más puedan analizar, más lentos serán.

La velocidad no es un problema para mí, elegí implementar un analizador Earley. Se ha demostrado que las implementaciones avanzadas de un analizador Earley son aproximadamente dos veces más lentas que otros tipos de analizador.

A cambio de ese golpe de velocidad, obtienes la capacidad de analizar cualquier tipo de gramática, incluso las ambiguas. Esto significa que nunca tendrá que preocuparse por si su analizador tiene alguna recursividad izquierda, o qué es un conflicto de reducción de turnos. También puede definir gramáticas más fácilmente usando gramáticas ambiguas si no importa qué árbol de análisis es el resultado, de modo que no importa si analiza 1 + 2 + 3 como (1 + 2) +3 o como 1 + (2 + 3).

Este es el aspecto que puede tener un código que usa mi generador de analizador sintáctico:

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(Tenga en cuenta que IntWrapper es simplemente un Int32, excepto que C # requiere que sea una clase, por lo tanto, tuve que introducir una clase de contenedor)

Espero que veas que el código anterior es muy poderoso: cualquier gramática que se te ocurra se puede analizar. Puede agregar bits arbitrarios de código en la gramática capaz de realizar muchas tareas. Si logra que todo funcione, puede reutilizar el código resultante para realizar muchas tareas con mucha facilidad: solo imagine crear un intérprete de línea de comandos utilizando este código.

Si nunca ha escrito un analizador, le recomendaría que lo haga. Es divertido, y aprendes cómo funcionan las cosas, y aprendes a apreciar el esfuerzo que los generadores de analizadores y lexer te evitan hacer la próxima vez que necesites un analizador.

También te sugiero que intentes leer http://compilers.iecc.com/crenshaw/ ya que tiene una actitud muy realista sobre cómo hacerlo.

La ventaja de escribir su propio analizador de descenso recursivo es que puede generar mensajes de error de alta calidad en errores de sintaxis. Con los generadores de analizadores, puede realizar producciones de errores y agregar mensajes de error personalizados en ciertos puntos, pero los generadores de analizadores simplemente no coinciden con el poder de tener un control completo sobre el análisis.

Otra ventaja de escribir el suyo es que es más fácil analizar una representación más simple que no tiene una correspondencia uno a uno con su gramática.

Si su gramática es fija y los mensajes de error son importantes, considere la posibilidad de rodar los suyos, o al menos usar un generador de analizador que le brinde los mensajes de error que necesita. Si su gramática cambia constantemente, debería considerar usar generadores de analizadores sintéticos.

Bjarne Stroustrup habla sobre cómo usó YACC para la primera implementación de C ++ (ver Diseño y evolución de C ++ ). En ese primer caso, ¡deseó haber escrito su propio analizador de descenso recursivo!

Opción 3: Ninguno (Rodar su propio generador de analizador)

Solo porque hay una razón para no usar ANTLR , bison , Coco / R , Grammatica , JavaCC , Lemon , Parboiled , SableCC , Quex , etc. , eso no significa que deba lanzar instantáneamente su propio analizador + lexer.

Identifique por qué todas estas herramientas no son lo suficientemente buenas, ¿por qué no le permiten alcanzar su objetivo?

A menos que esté seguro de que las rarezas en la gramática con la que está tratando son únicas, no debe crear un solo analizador + lexer personalizado para él. En su lugar, cree una herramienta que cree lo que desea, pero que también se pueda usar para satisfacer necesidades futuras, luego publíquela como Software Libre para evitar que otras personas tengan el mismo problema que usted.

Hacer rodar su propio analizador lo obliga a pensar directamente sobre la complejidad de su idioma. Si el lenguaje es difícil de analizar, probablemente será difícil de entender.

Hubo mucho interés en los generadores de analizadores sintéticos en los primeros días, motivados por una sintaxis de lenguaje altamente complicada (algunos dirían "torturada"). JOVIAL fue un ejemplo particularmente malo: requería dos símbolos con anticipación, en un momento en que todo lo demás requería como máximo un símbolo. Esto hizo que generar el analizador para un compilador JOVIAL fuera más difícil de lo esperado (ya que la División General Dynamics / Fort Worth aprendió de la manera difícil cuando adquirieron compiladores JOVIAL para el programa F-16).

Hoy, el descenso recursivo es universalmente el método preferido, porque es más fácil para los escritores de compiladores. Los compiladores de descendencia recursiva recompensan fuertemente el diseño de lenguaje simple y limpio, ya que es mucho más fácil escribir un analizador de descenso recursivo para un lenguaje simple y limpio que para un lenguaje complicado y desordenado.

Finalmente: ¿Ha considerado incorporar su idioma en LISP y dejar que un intérprete de LISP haga el trabajo pesado por usted? AutoCAD hizo eso y descubrió que les hacía la vida mucho más fácil. Hay bastantes intérpretes LISP livianos, algunos incorporables.

Una vez escribí un analizador para aplicaciones comerciales y usé yacc . Hubo un prototipo competitivo en el que un desarrollador escribió todo a mano en C ++ y funcionó unas cinco veces más lento.

En cuanto al lexer para este analizador, lo escribí completamente a mano. Tomó - lo siento, fue hace casi 10 años, así que no recuerdo con precisión - alrededor de 1000 líneas en C .

La razón por la que escribí el lexer a mano fue la gramática de entrada del analizador. Era un requisito, algo que mi implementación del analizador tenía que cumplir, a diferencia de algo que diseñé. (Por supuesto, lo hubiera diseñado de manera diferente. ¡Y mejor!) La gramática dependía severamente del contexto e incluso el lexing dependía de la semántica en algunos lugares. Por ejemplo, un punto y coma podría ser parte de una ficha en un lugar, pero un separador en un lugar diferente, basado en una interpretación semántica de algún elemento que se analizó anteriormente. Entonces, "enterré" tales dependencias semánticas en el lexer escrito a mano y eso me dejó con un BNF bastante sencillo que fue fácil de implementar en yacc.

AÑADIDO en respuesta a Macneil : yacc proporciona una abstracción muy poderosa que permite al programador pensar en términos de terminales, no terminales, producciones y cosas por el estilo. Además, al implementar la yylex()función, me ayudó a centrarme en devolver el token actual y no preocuparme por lo que estaba antes o después. El programador de C ++ trabajó en el nivel de los personajes, sin el beneficio de tal abstracción y terminó creando un algoritmo más complicado y menos eficiente. Llegamos a la conclusión de que la velocidad más lenta no tenía nada que ver con C ++ ni con ninguna biblioteca. Medimos la velocidad de análisis puro con archivos cargados en la memoria; Si tuviéramos un problema de almacenamiento de archivos, yacc no sería nuestra herramienta de elección para resolverlo.

TAMBIÉN QUIERO AGREGAR : esta no es una receta para escribir analizadores en general, solo un ejemplo de cómo funcionó en una situación particular.

Eso depende completamente de lo que necesita analizar. ¿Puedes rodar el tuyo más rápido de lo que podrías alcanzar la curva de aprendizaje de un lexer? ¿Es lo que hay que analizar lo suficientemente estático como para que no te arrepientas de la decisión más tarde? ¿Encuentra implementaciones existentes demasiado complejas? Si es así, diviértete rodando el tuyo, pero solo si no estás esquivando una curva de aprendizaje.

Últimamente, me ha gustado mucho el analizador de limón , que es posiblemente el más simple y fácil que he usado. En aras de hacer que las cosas sean fáciles de mantener, solo lo uso para la mayoría de las necesidades. SQLite lo usa así como otros proyectos notables.

Pero no estoy interesado en absoluto en los lexers, más allá de que no se interpongan en mi camino cuando necesito usar uno (por lo tanto, limón). Puede ser, y si es así, ¿por qué no hacer uno? Tengo la sensación de que volverás a usar uno que existe, pero rasca la picazón si es necesario :)

Depende de cuál sea tu objetivo.

¿Estás tratando de aprender cómo funcionan los analizadores / compiladores? Luego escribe el tuyo desde cero. Esa es la única forma en que realmente aprenderías a apreciar todos los entresijos de lo que están haciendo. He estado escribiendo uno en los últimos dos meses, y ha sido una experiencia interesante y valiosa, especialmente los momentos 'ah, así que por eso el lenguaje X hace esto ...'.

¿Necesita armar algo rápidamente para una solicitud en una fecha límite? Entonces, tal vez use una herramienta de análisis.

¿Necesita algo sobre lo que quiera expandirse en los próximos 10, 20, quizás incluso 30 años? Escribe el tuyo y tómate tu tiempo. Valdrá la pena.

¿Has considerado el enfoque del banco de trabajo de idiomas de Martin Fowlers ? Citando del artículo

El cambio más obvio que un banco de trabajo de idiomas hace a la ecuación es la facilidad de crear DSL externos. Ya no tienes que escribir un analizador. Debe definir la sintaxis abstracta, pero en realidad es un paso de modelado de datos bastante sencillo. Además, su DSL obtiene un IDE potente, aunque debe dedicar un tiempo a definir ese editor. El generador sigue siendo algo que tienes que hacer, y creo que no es mucho más fácil de lo que nunca fue. Pero construir un generador para un DSL bueno y simple es una de las partes más fáciles del ejercicio.

Al leer eso, diría que los días de escribir su propio analizador han terminado y es mejor usar una de las bibliotecas disponibles. Una vez que haya dominado la biblioteca, todos los DSL que cree en el futuro se beneficiarán de ese conocimiento. Además, otros no tienen que aprender su enfoque para analizar.

Editar para cubrir el comentario (y la pregunta revisada)

Ventajas de rodar tu propio

1. Serás dueño del analizador y obtendrás toda esa experiencia encantadora de pensar a través de una intrincada serie de problemas.
2. Es posible que se te ocurra algo especial en lo que nadie más haya pensado (es improbable pero pareces un tipo inteligente)
3. Te mantendrá ocupado con un problema interesante.

En resumen, debes rodar el tuyo cuando realmente quieras hackear profundamente las entrañas de un problema muy difícil que te sientes fuertemente motivado para dominar.

Ventajas de usar la biblioteca de otra persona

1. Evitará reinventar la rueda (un problema común en la programación estará de acuerdo)
2. Puede centrarse en el resultado final (nuevo lenguaje brillante) y no preocuparse demasiado por cómo se analiza, etc.
3. Verá su idioma en acción mucho más rápido (pero su recompensa será menor porque no fue todo lo que hizo)

Por lo tanto, si desea un resultado final rápido, use la biblioteca de otra persona.

En general, esto se reduce a una elección de cuánto quiere ser dueño del problema y, por lo tanto, la solución. Si lo quieres todo, rueda el tuyo.

La gran ventaja de escribir el suyo es que sabrá cómo escribir el suyo. La gran ventaja de usar una herramienta como yacc es que sabrá cómo usar la herramienta. Soy fanático de la copa de los árboles para la exploración inicial.

¿Por qué no bifurcar un generador de analizador de código abierto y hacerlo suyo? Si no usa generadores de analizadores, su código será muy difícil de mantener, si realizó grandes cambios en la sintaxis de su idioma.

En mis analizadores, utilicé expresiones regulares (quiero decir, estilo Perl) para simular, y utilicé algunas funciones convenientes para aumentar la legibilidad del código. Sin embargo, un código generado analizador-puede ser más rápido al hacer tablas de estado y larga switch- cases, lo que puede aumentar el tamaño del código fuente a menos que .gitignoreellos.

Aquí hay dos ejemplos de mis analizadores personalizados:

https://github.com/SHiNKiROU/DesignScript : un dialecto BÁSICO, porque era demasiado flojo para escribir lookaheads en notación de matriz, sacrifiqué la calidad de los mensajes de error https://github.com/SHiNKiROU/ExprParser - Una calculadora de fórmulas. Observe los extraños trucos de metaprogramación

"¿Debo usar esta probada 'rueda' o reinventarla?"