Analizador Earley

En informática , el analizador Earley es un algoritmo para analizar cadenas que pertenecen a un lenguaje libre de contexto dado . Nombrado en honor a su inventor, Jay Earley , fue presentado por primera vez en su tesis doctoral en 1968 (y posteriormente apareció en una forma abreviada y más legible en una revista). ^{[ 1 ] [ 2 ]} Es un analizador gráfico que utiliza programación dinámica .

Los analizadores Earley resultan atractivos porque pueden analizar todos los lenguajes libres de contexto, a diferencia de los analizadores LR y LL , que se utilizan más comúnmente en compiladores pero que solo pueden manejar clases restringidas de lenguajes. Sin embargo, el algoritmo Earley original contenía un error, y su tiempo de ejecución y consumo de memoria eran elevados para las computadoras disponibles en el momento de su publicación. Desde entonces, el análisis Earley se ha convertido en una solución viable, gracias a las correcciones y optimizaciones del algoritmo y al aumento significativo de la potencia de las computadoras. ^{[ 3 ]}

Los analizadores sintácticos de Earley funcionan particularmente bien cuando las reglas se escriben de forma recursiva por la izquierda . Algunas gramáticas se pueden reescribir automáticamente para que el algoritmo de Earley analice el lenguaje que describen de manera más eficiente.

Los costos en el peor de los casos del algoritmo original de Earley son:${\displaystyle O(n)}$tiempo y espacio lineales para gramáticas recursivas LR(k) no derechas,${\displaystyle O(n^{2})}$tiempo y espacio cuadráticos para gramáticas no ambiguas , ^{[ 4 ]}${\displaystyle O(n^{3})}$tiempo cúbico y${\displaystyle O(n^{2})}$espacio cuadrático para todas las demás gramáticas libres de contexto, donde${\displaystyle n}$es la longitud de la cadena analizada. ^{[ 5 ]}

El siguiente algoritmo describe el reconocedor de Earley. Este reconocedor puede modificarse para crear un árbol de análisis sintáctico a medida que reconoce, y de esta manera puede convertirse en un analizador sintáctico.

En las siguientes descripciones, α, β y γ representan cualquier cadena de terminales/no terminales (incluida la cadena vacía ), X e Y representan no terminales individuales, y a representa un símbolo terminal.

A continuación, utilizamos la notación de puntos de Earley: dada una producción X → αβ, la notación X → α • β representa una condición en la que α ya ha sido analizado y se espera β.

La posición de entrada 0 es la posición anterior a la entrada. La posición de entrada n es la posición posterior a la aceptación del n -ésimo token. (Informalmente, las posiciones de entrada pueden considerarse como ubicaciones en los límites de los tokens ). Para cada posición de entrada, el analizador genera un conjunto de estados . Cada estado es una tupla (X → α • β, i ), que consta de

• la producción que actualmente se está igualando (X → α β)
• la posición actual en esa producción (representada visualmente por el punto •)
• la posición i en la entrada en la que comenzó la coincidencia de esta producción: la posición de origen

(El algoritmo original de Earley incluía una anticipación en el estado; investigaciones posteriores demostraron que esto tenía poco efecto práctico en la eficiencia del análisis sintáctico, y posteriormente se eliminó de la mayoría de las implementaciones).

Un estado está terminado cuando su posición actual es la última posición del lado derecho de la producción, es decir, cuando no hay ningún símbolo a la derecha del punto • en la representación visual del estado.

El estado establecido en la posición de entrada k se llama S( k ). El analizador se inicializa con S(0), que consiste únicamente en la regla de nivel superior. A continuación, el analizador ejecuta repetidamente tres operaciones: predicción , escaneo y finalización .

• Predicción : Para cada estado en S( k ) de la forma (X → α • Y β, j ) (donde j es la posición de origen como se indicó anteriormente), agregue (Y → • γ, k ) a S( k ) para cada producción en la gramática con Y en el lado izquierdo (Y → γ).
• Escaneo : Si a es el siguiente símbolo en el flujo de entrada, para cada estado en S( k ) de la forma (X → α • a β, j ), agregue (X → α a • β, j ) a S( k +1).
• Completar : Para cada estado en S( k ) de la forma (Y → γ •, j ), encontrar todos los estados en S( j ) de la forma (X → α • Y β, i ) y agregar (X → α Y • β, i ) a S( k ).

Los estados duplicados no se añaden al conjunto de estados, solo los nuevos. Estas tres operaciones se repiten hasta que no se puedan añadir más estados al conjunto. El conjunto se implementa generalmente como una cola de estados a procesar, y la operación a realizar depende del tipo de estado.

El algoritmo acepta si (X → γ •, 0) termina en S( n ), donde (X → γ) es la regla de nivel superior y n la longitud de entrada, de lo contrario rechaza.

DECLARAR MATRIZ S ;función INIT ( palabras ) S ← CREATE_ARRAY ( LENGTH ( palabras ) + 1 ) para k ← desde 0 hasta LENGTH ( palabras ) hacer S [ k ] ← EMPTY_ORDERED_SETfunción EARLEY_PARSE ( palabras , gramática ) INIT ( palabras ) ADD_TO_SET (( γ → • S , 0 ) , S [ 0 ]) para k ← desde 0 hasta LENGTH ( palabras ) hacer para cada estado en S [ k ] hacer // S[k] puede expandirse durante este bucle si no FINISHED ( estado ) entonces si NEXT_ELEMENT_OF ( estado ) es un no terminal entonces PREDICTOR ( estado , k , gramática ) // no terminal sino hacer SCANNER ( estado , k , palabras ) // terminal sino hacer COMPLETER ( estado , k ) fin fin devolver chartprocedimiento PREDICTOR (( A → α• B β , j ) , k , gramática ) para cada ( B → γ ) en REGLAS_GRAMÁTICAS_PARA ( B , gramática ) hacer AÑADIR_AL_CONJUNTO (( B → •γ , k ) , S [ k ]) finprocedimiento ESCÁNER (( A → α• a β , j ) , k , palabras ) si j < LONGITUD ( palabras ) y a ⊂ PARTES_DE_LA_ORACIÓN ( palabras [ k ]) entonces AÑADIR_AL_CONJUNTO (( A → α a •β , j ) , S [ k + 1 ]) finprocedimiento COMPLETER (( B → γ• , x ) , k ) para cada ( A → α• B β , j ) en S [ x ] hacer ADD_TO_SET (( A → α B •β , j ) , S [ k ]) fin

Consideremos la siguiente gramática simple para expresiones aritméticas:

<P> ::= <S> # la regla de inicio <S> ::= <S> "+" <M> | <M> <M> ::= <M> "*" <T> | <T> <T> ::= "1" | "2" | "3" | "4" 

Con la entrada:

2 + 3 * 4

Esta es la secuencia de conjuntos de estados:

El estado (P → S •, 0) representa un análisis sintáctico completo. Este estado también aparece en S(3) y S(1), que son oraciones completas.

La disertación de Earley ^{[ 7 ]} describe brevemente un algoritmo para construir árboles de análisis sintáctico agregando un conjunto de punteros desde cada no terminal en un elemento de Earley hacia los elementos que causaron su reconocimiento. Pero Tomita notó ^{[ 8 ]} que esto no toma en cuenta las relaciones entre símbolos, por lo que si consideramos la gramática S → SS | b y la cadena bbb, solo observa que cada S puede coincidir con una o dos b, y por lo tanto produce derivaciones espurias para bb y bbbb, así como las dos derivaciones correctas para bbb.

Otro método ^{[ 9 ]} consiste en construir el bosque de análisis sintáctico a medida que se avanza, aumentando cada elemento de Earley con un puntero a un nodo de bosque de análisis sintáctico empaquetado compartido (SPPF) etiquetado con una tripleta (s, i, j) donde s es un símbolo o un elemento LR(0) (regla de producción con punto), e i y j dan la sección de la cadena de entrada derivada por este nodo. El contenido de un nodo es un par de punteros hijos que dan una única derivación, o una lista de nodos "empaquetados" cada uno de los cuales contiene un par de punteros y representa una derivación. Los nodos SPPF son únicos (solo hay uno con una etiqueta dada), pero pueden contener más de una derivación para análisis sintácticos ambiguos . Así que incluso si una operación no agrega un elemento de Earley (porque ya existe), aún puede agregar una derivación al bosque de análisis sintáctico del elemento.

• Los elementos previstos tienen un puntero SPPF nulo.
• El escáner crea un nodo SPPF que representa el dispositivo no terminal que está escaneando.
• Luego, cuando el escáner o el completador avanza un elemento, agregan una derivación cuyos hijos son el nodo del elemento cuyo punto fue avanzado y el del nuevo símbolo que fue avanzado (el elemento no terminal o completado).

Los nodos SPPF nunca se etiquetan con un elemento LR(0) completo: en su lugar, se etiquetan con el símbolo que se produce para que todas las derivaciones se combinen bajo un solo nodo, independientemente de la producción alternativa de la que provengan.

En 1972, Alfred Aho y Jeffrey Ullman corrigen el error de la regla vacía en el algoritmo de Earley, pero su solución hace que el algoritmo sea aún más costoso de ejecutar. ^{[ 10 ]}

En 1991, Joop Leo logra el análisis sintáctico en tiempo y espacio lineales para cada gramática LR( k ). ^{[ 5 ]}

En 1996, Philippe McLean y R. Nigel Horspool, aparentemente sin conocer el trabajo de Leo, combinan el análisis sintáctico de Earley con el análisis sintáctico de LR. ^{[ 11 ]}

En 2002, John Aycock y R. Nigel Horspool, aparentemente aún sin conocer el trabajo de Leo, resolvieron el problema de la regla vacía del algoritmo de Earley sin aumentar su costo. ^{[ 12 ]}

En 2010, Jeffrey Kegler combina las optimizaciones de 1991 y 2002 en su analizador sintáctico de código abierto Marpa. ^{[ 13 ] [ 14 ]} Posteriormente publica una descripción formal del reconocedor Marpa, afirmando que se ejecuta en tiempo lineal para todas las clases de gramática actualmente en uso práctico. ^{[ 15 ] [ 16 ]} Con más detalle, afirma que Marpa se ejecuta en tiempo lineal para: ^{[ 17 ]}

• Todas las clases gramaticales que analiza el descenso recursivo .
• La clase gramatical que analiza la familia yacc .
• Todas las gramáticas no ambiguas, libres de recursiones intermedias no marcadas y recursiones derechas ambiguas.
• Gramáticas ambiguas que son uniones de un conjunto finito de cualquiera de las gramáticas anteriores.

• Algoritmo CYK
• Gramática libre de contexto
• Algoritmos de análisis sintáctico

• Tomita, Masaru (1984). "Analizadores sintácticos LR para lenguajes naturales" (PDF) . COLING . 10.ª Conferencia Internacional sobre Lingüística Computacional. pp. 354–357 . Archivado del original (PDF) el 23 de mayo de 2018.