¿Se puede convertir un Earley Parser en un analizador difuso similar al Levenshtein Automata Algo para DFA?

Hay una manera de realizar un análisis difuso (acepta cadenas incluso con errores tipográficos a una cierta distancia de edición), con un DFA y un Autómata Levenshtein construido en tiempo de ejecución de la palabra de entrada. ¿Se puede hacer algo similar con un analizador Earley? Me resulta difícil entender el algoritmo, y mucho menos responder esta pregunta.

La respuesta es sí. Sin embargo, no haría eso con un analizador Earley porque hay otros más simples con las mismas capacidades.

Básicamente, el analizador Earley pertenece a una familia de analizadores generales sin contexto, que produce todos los análisis posibles para una cadena dada, cuando la gramática es ambigua.

Hay dos formas (al menos) de entender estos analizadores:

• como interpretación de programación dinámica de un autómata pushdown correspondiente a la gramática en la cadena de entrada;

• como la construcción de la intersección de la gramática con un autómata de estado finito.

Al analizar una sola cadena, el autómata de estado finito a considerar es un autómata lineal que reconoce solo la cadena a analizar, un símbolo a la vez (el número de estado es | w | + 1 ). Si aplica la construcción de productos cruzados de un FA A y una gramática CF G (Bar Hillel, Perlis, Shamir 1961), obtendrá una nueva gramática CF que es una nueva gramática F que genera L ( A ) ∩ L ( G ) . El punto interesante que generalmente se pasa por alto es que F conserva los árboles de análisis utilizados por $w$$|w|+1$$A$$G$$F$$\mathcal L(A)\cap\mathcal L(G)$$F$$G$, hasta el cambio de nombre de no terminales (debido a productos cruzados).

Por lo tanto, si la FA genera solo su cadena de entrada, la gramática F generará solo esa cadena (si está en L ( G ) , de lo contrario genera el lenguaje vacío ∅ ). Además, lo genera con todos los árboles de análisis que G podría usar para generarlo.$A$$F$$\mathcal L(G)$$\emptyset$$G$

Esta gramática es lo que generalmente se llama un bosque de análisis compartido , y todos los algoritmos generales de análisis de CF son una versión más o menos optimizada de la construcción de productos cruzados, ya sea CYK, Earley, LR generalizado o LL, u otros. Entonces, todo lo que digo se aplica a ellos también.$F$

Pero, como puede ver, esto se generaliza al análisis de un conjunto regular completo, si alguien está interesado en hacerlo.

$w$$w$

$G$$F$

Si es deseable, esto se puede usar para mantener solo las cadenas con una distancia mínima.

Sin embargo, esto puede mejorarse un poco ya que la composición con máquinas de estados finitos es asociativa.

$G$$w$$\Sigma^*$

Sería fácil podar esa construcción para obtener el mismo resultado que antes, pero la mejor manera es una construcción de intersección más controlada, como la organización de programación dinámica utilizada por la mayoría de los analizadores en la literatura, incluida Earley, y usarla para evitar generar regla inútil calculando distancias y abortando cualquier ruta computacional cuando excede el umbral deseado. La programación dinámica también se puede utilizar para calcular directamente el bosque de análisis (o árbol de análisis) para la cadena que tiene la distancia más corta a la entrada.