En informática , el analizador sintáctico 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 que aceptan valores nulos. [1] El algoritmo, llamado así por su inventor, Jay Earley , es un analizador sintáctico de gráficos que utiliza programación dinámica ; se utiliza principalmente para analizar en lingüística computacional . Fue presentado por primera vez en su disertación [2] en 1968 (y luego apareció en una forma abreviada, 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 no ambiguas , [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 individuales y a representa un símbolo terminal.
El algoritmo de Earley es un algoritmo de programación dinámica descendente . En el siguiente ejemplo, 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 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 . (De manera informal, 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 mirada hacia adelante en el estado; investigaciones posteriores demostraron que esto tenía poco efecto práctico en la eficiencia del análisis 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 denomina S( k ). El analizador se inicializa con S(0) que consiste únicamente en 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, solo 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 del que se trate.
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 Speech and Language Processing [5] de Daniel Jurafsky y James H. Martin,
DECLARAR MATRIZ S ; función INIT ( palabras ) S ← CREAR_MATIZACIÓN ( LONGITUD ( palabras ) + 1 ) para k ← de 0 a LONGITUD ( palabras ) hacer S [ k ] ← CONJUNTO_ORDENADO_VACÍO 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 bucle si no es FINISHED ( estado ) entonces si NEXT_ELEMENT_OF ( estado ) es no terminal entonces PREDICTOR ( estado , k , gramática ) // no terminal de lo contrario hacer SCANNER ( estado , k , palabras ) // terminal de lo contrario hacer COMPLETER ( estado , k ) fin fin devolver gráfico 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_DEL_DISCURSO ( palabras [ k ]) entonces AGREGAR_AL_CONJUNTO (( A → α a •β , j ) , S [ k + 1 ]) fin procedimiento COMPLETER (( B → γ• , x ) , k ) para cada ( A → α• B β , j ) en S [ x ] hacer 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 sintáctico 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 agregando un conjunto de punteros desde cada no terminal en un elemento de Earley a los elementos que hicieron que se reconociera. Pero Tomita notó [7] que esto no tiene en cuenta las relaciones entre los símbolos, por lo que si consideramos la gramática S → SS | b y la cadena bbb, solo se nota 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] consiste en construir el bosque de análisis a medida que se avanza, aumentando cada elemento 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 por 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" que contienen cada uno un par de punteros y representan 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 . Por lo tanto, 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 cambio, se etiquetan con el símbolo que se produce para que todas las derivaciones se combinen en un solo nodo, independientemente de qué producción alternativa provengan.
Philippe McLean y R. Nigel Horspool en su artículo "Un analizador Earley más rápido" combinan el análisis Earley con el análisis LR y logran una mejora de un orden de magnitud.