Comparación de generadores de analizadores sintácticos

Esta es una lista de generadores de analizadores léxicos y sintácticos destacados para diversas clases de lenguajes.

Los lenguajes regulares son una categoría de lenguajes (a veces denominados de tipo 3 de Chomsky ) que pueden ser representados por una máquina de estados (más específicamente, por un autómata finito determinista o no determinista ) construida a partir de una expresión regular . En particular, un lenguaje regular puede representar construcciones como "A sigue a B", "A o B", "A, seguido de cero o más instancias de B", pero no puede representar construcciones que requieren consistencia entre elementos no adyacentes, como "algunas instancias de A seguidas por el mismo número de instancias de B", y tampoco puede expresar el concepto de "anidamiento" recursivo ("cada A es seguido eventualmente por un B correspondiente"). Un ejemplo clásico de un problema que una gramática regular no puede manejar es la cuestión de si una cadena dada contiene paréntesis correctamente anidados. (Esto generalmente lo maneja una gramática de tipo 2 de Chomsky, también denominada gramática libre de contexto ).

Los lenguajes libres de contexto son una categoría de lenguajes (a veces denominados de tipo 2 de Chomsky ) que pueden ser emparejados por una secuencia de reglas de reemplazo, cada una de las cuales esencialmente asigna cada elemento no terminal a una secuencia de elementos terminales y/u otros elementos no terminales. Las gramáticas de este tipo pueden emparejar cualquier cosa que pueda ser emparejada por una gramática regular y, además, pueden manejar el concepto de "anidamiento" recursivo ("cada A es seguido eventualmente por un B correspondiente"), como la cuestión de si una cadena dada contiene paréntesis correctamente anidados. Sin embargo, las reglas de las gramáticas libres de contexto son puramente locales y, por lo tanto, no pueden manejar preguntas que requieren análisis no local, como "¿Existe una declaración para cada variable que se usa en una función?". Para hacerlo técnicamente se requeriría una gramática más sofisticada, como una gramática de tipo 1 de Chomsky, también denominada gramática sensible al contexto . Sin embargo, los generadores de analizadores sintácticos para gramáticas libres de contexto suelen permitir que el código escrito por el usuario introduzca una sensibilidad al contexto limitada. (Por ejemplo, al encontrar una declaración de variable, el código escrito por el usuario podría guardar el nombre y el tipo de la variable en una estructura de datos externa, de modo que estos se puedan comparar con referencias a variables detectadas posteriormente por el analizador).

Los lenguajes libres de contexto deterministas son un subconjunto propio de los lenguajes libres de contexto que pueden ser analizados eficientemente por autómatas de pila deterministas .

Esta tabla compara los generadores de analizadores sintácticos con las gramáticas de expresiones de análisis sintáctico y las gramáticas booleanas deterministas .

Esta tabla compara los lenguajes generadores de analizadores sintácticos con una gramática general libre de contexto , una gramática conjuntiva o una gramática booleana .

Esta tabla compara los generadores de analizadores sintácticos con las gramáticas sensibles al contexto .

• Compilador-compilador
• Lista de sistemas de transformación de programas
• Comparación de motores de expresiones regulares

• El catálogo de herramientas para la construcción de compiladores se archivó el 13 de agosto de 2011 en la Wayback Machine.
• Generadores de analizadores sintácticos de código abierto en Java