Analizador de gráficos

En informática , un analizador de gráficos 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 atribuye a Martin Kay . ^[1]

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 que se utiliza principalmente para el análisis sintáctico en lingüística computacional y recibe su nombre de su inventor. Otro algoritmo de análisis sintáctico 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 de Earley, en particular, se han utilizado en compiladores-compiladores , donde su capacidad para analizar utilizando gramáticas arbitrarias libres de contexto facilita la tarea de escribir la gramática para un lenguaje en particular. Sin embargo, su menor eficiencia ha llevado a que la gente los evite para la mayoría de los trabajos de compilación.

En el análisis de gráficos bidireccionales, 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 deben apuntar los bordes para combinarse en otros bordes.

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

Los analizadores de gráficos se distinguen entre de arriba hacia abajo y de abajo hacia arriba , así como entre activos y pasivos.