En informática , el analizador Earley es un algoritmo para analizar cadenas que pertenecen a un determinado lenguaje libre de contexto , aunque (dependiendo de la variante) puede sufrir problemas con ciertas gramáticas que aceptan valores NULL. [1] 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 el análisis en lingüística computacional . Se introdujo por primera vez en su disertación [2] en 1968 (y luego apareció en una forma abreviada y más legible en una revista [3] ).
Los analizadores Earley son atractivos porque pueden analizar todos los lenguajes libres de contexto, a diferencia de los analizadores LR y LL , que se usan más típicamente en compiladores pero que solo pueden manejar clases restringidas de lenguajes. El analizador Earley se ejecuta en tiempo cúbico en el caso general , donde n es la longitud de la cadena analizada, tiempo cuadrático para gramáticas inequívocas , [4] y tiempo lineal para todas las gramáticas deterministas libres de contexto . Funciona particularmente bien cuando las reglas se escriben de forma recursiva hacia la izquierda .
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.
En las siguientes descripciones, α, β y γ representan cualquier cadena de terminales/no terminales (incluida la cadena vacía ), X e Y representan no terminales únicos y a representa un símbolo de terminal.
El algoritmo de Earley es un algoritmo de programación dinámica de arriba hacia abajo . 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 analizada 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 enésimo token. (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
(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).
Un estado finaliza 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 consta únicamente de la regla de nivel superior. Luego, el analizador ejecuta repetidamente tres operaciones: predicción , escaneo y finalización .
Los estados duplicados no se agregan al conjunto de estados, sólo los nuevos. Estas tres operaciones se repiten hasta que no se puedan agregar nuevos estados al conjunto. El conjunto generalmente se implementa como una cola de estados para procesar, y la operación a realizar depende del tipo de estado que 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, rechaza.
Adaptado de Procesamiento del habla y el lenguaje [5] por Daniel Jurafsky y James H. Martin,
DECLARAR ARRAY S ; función INIT ( palabras ) S ← CREATE_ARRAY ( LENGTH ( palabras ) + 1 ) para k ← de 0 a LENGTH ( palabras ) haga S [ k ] ← EMPTY_ORDERED_SET función EARLEY_PARSE ( palabras , gramática ) INIT ( palabras ) ADD_TO_SET (( γ → • S , 0 ) , S [ 0 ]) para k ← de 0 a LENGTH ( palabras ) hacer para cada estado en S [ k ] hacer // S [k] puede expandirse durante este ciclo si no está FINALIZADO ( estado ) , entonces si NEXT_ELEMENT_OF ( estado ) es un no terminal, entonces PREDICTOR ( estado , k , gramática ) // no_terminal en caso contrario SCANNER ( estado , k , palabras ) // terminal en caso contrario COMPLETO ( estado , k ) tabla de retorno final procedimiento PREDICTOR (( A → α• B β , j ) , k , gramática ) para cada ( B → γ ) en GRAMMAR_RULES_FOR ( B , gramática ) hacer ADD_TO_SET (( B → •γ , k ) , S [ k ]) fin procedimiento ESCÁNER (( A → α• a β , j ) , k , palabras ) si j < LONGITUD ( palabras ) y a ⊂ PARTES_OF_SPEECH ( palabras [ k ] ) entonces ADD_TO_SET (( A → α a •β , j ) , S [ k + 1 ]) fin procedimiento COMPLETO (( B → γ• , x ) , k ) para cada ( A → α• B β , j ) en S [ x ] haga ADD_TO_SET (( A → α B •β , j ) , S [ k ]) fin Considere 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 completo. Este estado también aparece en S(3) y S(1), que son oraciones completas.
La disertación de Earley [6] describe brevemente un algoritmo para construir árboles de análisis añadiendo un conjunto de punteros desde cada no terminal en un elemento de Earley a los elementos que causaron su reconocimiento. Pero Tomita notó [7] 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 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 [8] es construir el bosque de análisis a medida que avanza, 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 Elemento LR(0) (regla de producción con punto), e i y j dan la sección de la cadena de entrada derivada de este nodo. El contenido de un nodo es un par de punteros secundarios 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 determinada), pero pueden contener más de una derivación para análisis ambiguos . Entonces, incluso si una operación no agrega un elemento Earley (porque ya existe), aún puede agregar una derivación al bosque de análisis del elemento.
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 qué producción alternativa provengan.
Philippe McLean y R. Nigel Horspool en su artículo "A Faster Earley Parser" combinan el análisis Earley con el análisis LR y logran una mejora en un orden de magnitud.