Analizador de gráficos

En informática, un parser gráfico es un tipo de analizador adecuado para gramáticas ambiguas (incluidas las gramáticas de lenguajes naturales). Utiliza el enfoque de programación dinámica: los resultados hipotéticos parciales se almacenan en una estructura llamada gráfico y se pueden reutilizar. Esto elimina el retroceso y evita una explosión combinatoria.

El análisis de gráficos generalmente se acredita a Martin Kay.

Tipos de analizadores de gráficos

Un enfoque común es utilizar una variante del algoritmo de Viterbi. El analizador Earley es un tipo de analizador de gráficos utilizado principalmente para analizar en lingüística computacional, llamado así por su inventor. Otro algoritmo de análisis de gráficos es el algoritmo Cocke-Younger-Kasami (CYK).

Los analizadores de gráficos también se pueden utilizar para analizar lenguajes informáticos. Los analizadores Earley, en particular, se han utilizado en compiladores-compiladores donde su capacidad para analizar utilizando gramáticas libres de contexto arbitrarias facilita la tarea de escribir la gramática para un idioma en particular. Sin embargo, su menor eficiencia ha llevado a que la gente los evite para la mayoría del trabajo de compilación.

En el análisis bidireccional de gráficos, los bordes del gráfico se marcan con una dirección, ya sea hacia adelante o hacia atrás, y se aplican reglas sobre la dirección en la que los bordes deben apuntar para combinarse en más bordes.

En el análisis de gráfico incremental, el gráfico se construye de forma incremental a medida que el usuario edita el texto, y cada cambio en el texto da como resultado el mínimo cambio correspondiente posible en el gráfico.

Los analizadores de gráficos se distinguen entre descendentes y ascendentes, así como activos y pasivos.