Analizador de Earley

En informática, el analizador Earley es un algoritmo para analizar cadenas que pertenecen a un lenguaje libre de contexto dado, aunque (dependiendo de la variante) puede sufrir problemas con ciertas gramáticas anulables. El algoritmo, que lleva el nombre de su inventor, Jay Earley, es un analizador de gráficos que utiliza programación dinámica; se utiliza principalmente para analizar en lingüística computacional. Se introdujo por primera vez en su disertación en 1968 (y luego apareció en una forma abreviada, más legible, en un diario).

Los analizadores Earley son atractivos porque pueden analizar todos los idiomas sin contexto, a diferencia de los analizadores LR y los analizadores LL, que son más típicamente utilizados en los compiladores pero que sólo pueden manejar clases restringidas de idiomas. El analizador Earley ejecuta en tiempo cúbico en el caso general O()n3){displaystyle {}(n^{3})}, donde n es la longitud de la cadena parsed, tiempo cuadrático para gramáticas inequívocas O()n2){displaystyle {}(n^{2})}, y tiempo lineal para todas las gramáticas libres de contexto determinista. Se realiza particularmente bien cuando las reglas están escritas de forma izquierda-recursiva.

Reconocedor temprano

El siguiente algoritmo describe el reconocedor Earley. El reconocedor se puede modificar para crear un árbol de análisis a medida que reconoce, y de esa manera se puede convertir en un analizador.

El algoritmo

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 de terminal.

El algoritmo de Earley es un algoritmo de programación dinámica descendente. A continuación, usamos la notación de puntos de Earley: dada una producción X → αβ, la notación X → α • β representa una condición en la que α ya se ha 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 después de aceptar el token nésimo. (Informalmente, las posiciones de entrada se pueden considerar 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 actualmente en juego (X → α β)
• la posición actual en esa producción (representada por el punto)
• la posición i en la entrada en la que comenzó la concordancia de esta producción: posición de origen

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

El estado establecido en la posición de entrada k se llama S(k). El analizador está sembrado con S(0) que consta solo de la regla de nivel superior. Luego, el analizador ejecuta repetidamente tres operaciones: predicción, escaneo y finalización.

• Predicción: Por cada estado en S(k) de la forma (X → α • Y β, j(donde) j es la posición de origen como arriba), añadir (Y → • γ, k) a S(k) para cada producción en la gramática con Y en el lado izquierdo (Y → γ).
• ScanningSi a es el siguiente símbolo en el flujo de entrada, para cada estado en S(k) de la forma (X → α • a β, j), añadir (X → α a • β, j) a S(k+1).
• Terminación: Por cada estado en S(k) de la forma (Y → γ •, j), encontrar todos los estados en S(j) de la forma (X → α • Y β, i) y añadir (X → α Y • β, i) a S(k).

Los estados duplicados no se agregan al conjunto de estados, solo los nuevos. Estas tres operaciones se repiten hasta que no se pueden agregar nuevos estados al conjunto. El conjunto generalmente se implementa como una cola de estados para procesar, y la operación a realizar depende de qué tipo de estado sea.

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 se rechaza.

Pseudocódigo

Adaptado de Speech and Language Processing de Daniel Jurafsky y James H. Martin,

DECLARE ARRAY S;función INIT()palabras) S ← CREATE_ARRAY()LENGTH()palabras) + 1) para k ← desde 0 a LENGTH()palabras) do S[k] ← EMPTY_ORDERED_SETfunción EARLEY_PARSE()palabras, gramática) INIT()palabras) ADD_TO_SET()γ → •S, 0), S[0]) para k ← desde 0 a LENGTH()palabras) do para cada uno estado dentro S[k] do // S[k] puede expandirse durante este bucle si no FINISHED()estado) entonces si NEXT_ELEMENT_OF()estado) es a nonterminal entonces PREDICTOR()estado, k, gramática) // no_terminal más do SCANNER()estado, k, palabras) // terminal más do COMPLETO()estado, k) final final retorno Gráficoprocedimiento PREDICTOR()A → α•Bβ, j), k, gramática) para cada uno ()B → γ) dentro GRAMMAR_RULES_FOR()B, gramática) do ADD_TO_SET()B → •γ, k), S[k]) finalprocedimiento SCANNER()A → α•aβ, j), k, palabras) si a ⊂ PARTES_OF_SPEECH()palabras[k]) entonces ADD_TO_SET()A → αa•β, j), S[k+1]) finalprocedimiento COMPLETO()B → γ•, x), k) para cada uno ()A → α•Bβ, j) dentro S[x] do ADD_TO_SET()A → αB•β, j), S[k]) final

Ejemplo

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

* * * = * * *
< < > > > > > >
■M título::= < > > > > >
" "1" Silencio "2"

Con la entrada:

2 + 3 * 4

Esta es la secuencia de conjuntos de estados:

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

Construyendo el bosque de análisis

La disertación de Earley describe brevemente un algoritmo para construir árboles de análisis sintáctico agregando un conjunto de punteros de cada elemento no terminal en un elemento de Earley a los elementos que hicieron que se reconociera. Pero Tomita notó que esto no tiene en cuenta las relaciones entre símbolos, por lo que si consideramos la gramática S → SS | b y la cadena bbb, solo señala que cada S puede coincidir con una o dos b's y, por lo tanto, produce derivaciones espurias para bb y bbbb, así como las dos derivaciones correctas para bbb.

Otro método es construir el bosque de análisis sobre la marcha, aumentando cada elemento de Earley con un puntero a un nodo de bosque de análisis empaquetado compartido (SPPF) etiquetado con un triple (s, i, j) donde s es un símbolo o un LR(0) elemento (regla de producción con punto), 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 secundarios que proporcionan una única derivación o una lista de elementos "empaquetados" nodos, 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 ambiguos. Entonces, 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 del elemento.

• Los elementos predecidos tienen un puntero SPPF nulo.
• El escáner crea un nodo SPPF que representa al no-terminal que está escaneando.
• Luego, cuando el escáner o el completo avance un artículo, añaden una derivación cuyos hijos son el nodo del elemento cuyo punto fue avanzado, y el del nuevo símbolo que se adelantó (el elemento no final 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 en un nodo, independientemente de la producción alternativa de la que provengan.

Optimizaciones

Philippe McLean y R. Nigel Horspool en su artículo "A Faster Earley Parser" combine el análisis de Earley con el análisis de LR y logre una mejora en un orden de magnitud.

Otros materiales de referencia

• Aycock, John; Horspool, R. Nigel (2002). "Practical Earley Parsing". The Computer Journal. 45 (6): 620-630. CiteSeerX10.1.1.12.4254. doi:10.1093/comjnl/45.6.620.
• Leo, Joop M. I. M. (1991), "Un algoritmo sin contexto general que funciona en tiempo lineal en cada LR(k) gramática sin usar cabeza de mira", Theoretical Computer Science, 82 (1): 165–176, doi:10.1016/0304-3975(91)90180-A, MR 1112117

Implementaciones

C, C++