A saber, ¿existe alguna herramienta que muestre automáticamente el idioma completo de una gramática dada, incluyendo resaltar las ambigüedades (si las hay)?¿Cuál es la forma más fácil de saber si una gramática BNF es ambigua o no?
Puede haber alguna peculiaridad acerca de las gramáticas de estilo BNF, pero, en general, no es posible decidir si una gramática libre de contexto dada (como BNF) es ambigua.
En resumen, no existe una herramienta porque, en general, esa herramienta es matemáticamente imposible. Sin embargo, podría haber algunos casos especiales que podrían funcionar para usted.
Más específicamente, puede verificar si una gramática es ambigua si lo es, pero no se puede probar que no. – OrangeDog
@OrangeDog: Bueno, en general no puedes probarlo, pero es posible para algunas gramáticas (Aquí hay una pequeña gramática para la cual puedes probarla fácilmente: "goal = a;"). –
En general, no.
Pero como un enfoque práctico, lo que se puede hacer, se le da una gramática, es para cada regla, enumerar posibles cadenas de terminales válidos/no terminales, para ver si alguna regla tiene dos o más derivaciones equivalentes (que serían una ambigüedad).
Nuestro DMS Software Reengineering Toolkit es un sistema de transformación de programas para lenguajes informáticos arbitrarios, impulsado por descripciones gramaticales explícitas. DMS usa un generador de analizador para controlar su motor de análisis GLR.
El generador de analizadores de DMS opcionalmente controlará la ambigüedad esbozada arriba, ejecutando una búsqueda iterativa de profundización en todas las reglas de la gramática. Esto es práctico porque tiene tablas de análisis para guiar eficientemente la enumeración de opciones. Puedes decirle que ejecute este control hasta cierta profundidad elegida. Puede tomar mucho tiempo si elige una profundidad de cualquier tamaño interesante, pero de hecho una profundidad de 3 o 4 es suficiente para encontrar muchas ambigüedades estúpidas introducidas en una gramática grande. Generalmente hacemos esto durante nuestra depuración inicial de la gramática, y en el punto donde creemos que lo tenemos bastante correcto.
Nota: el software DMS vinculado cuesta dinero. El sitio web no muestra el precio; debe llamar para una cotización. –
Quizás esto es relevante: http://cstheory.stackexchange.com/questions/4352/how-is-proving-a-context-free-language-to-be-ambiguous-undecidable –