Analizador de gráficos - Chart parser
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 .
Tipos de analizadores de gráficos
Un enfoque común es utilizar una variante del algoritmo de Viterbi . El analizador de Earley es un tipo de analizador de gráficos utilizado principalmente para el análisis sintáctico 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 sintácticos Earley, en particular, se han utilizado en compiladores-compiladores en los que 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 parte del trabajo del compilador.
En el análisis de gráfico bidireccional, los bordes del gráfico se marcan con una dirección, ya sea hacia adelante o hacia atrás, y las reglas se aplican en la dirección en la que deben apuntar los bordes para que se combinen 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 da como resultado el cambio correspondiente mínimo posible en el gráfico.
Los analizadores de gráficos se distinguen entre descendente y ascendente , así como activos y pasivos.