Analizador sintáctico Earley

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 . $Estilo de visualización {O}(n^{3})}$ $Estilo de visualización {O}(n^{2})}$

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

• la producción que se está igualando actualmente (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 correspondencia de esta producción: la posición de origen

(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 .

• Predicción : Para cada estado en S( k ) de la forma (X → α • Y β, j ) (donde j es la posición de origen como arriba), 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).
• Completamiento : Para cada estado en S( k ) de la forma (Y → γ •, j ), encuentre todos los estados en S( j ) de la forma (X → α • Y β, i ) y agregue (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 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 elementos predichos tienen un puntero SPPF nulo.
• El escáner crea un nodo SPPF que representa el no terminal que está escaneando.
• Luego, cuando el escáner o el completador avanzan un elemento, agregan una derivación cuyos hijos son el nodo del elemento cuyo punto se avanzó y el del nuevo símbolo sobre el que se avanzó (el elemento no terminal o completado).

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

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

• Aycock, John; Horspool, R. Nigel (2002). "Análisis sintáctico práctico de Earley". The Computer Journal . 45 (6): 620–630. CiteSeerX  10.1.1.12.4254 . doi :10.1093/comjnl/45.6.620.
• Leo, Joop MIM (1991), "Un algoritmo de análisis sintáctico general libre de contexto que se ejecuta en tiempo lineal en cada gramática LR( k ) sin utilizar la búsqueda anticipada", Theoretical Computer Science , 82 (1): 165–176, doi : 10.1016/0304-3975(91)90180-A , MR  1112117

• Tomita, Masaru (1984). "Analizadores LR para lenguajes naturales" (PDF) . COLING . 10.ª Conferencia Internacional sobre Lingüística Computacional. pp. 354–357.

• 'Otro analizador de Earley (YAEP)': bibliotecas de C / C++

• 'Earley': un analizador DSL de Earley en Haskell

• [1] – una implementación en Java del algoritmo Earley
• PEN: una biblioteca Java que implementa el algoritmo Earley
• Pep: una biblioteca Java que implementa el algoritmo Earley y proporciona gráficos y árboles de análisis como artefactos de análisis.
• digitalheir/java-probabilistic-earley-parser: una biblioteca Java que implementa el algoritmo probabilístico Earley, que es útil para determinar el árbol de análisis más probable a partir de una oración ambigua

• coonsta/earley - Un analizador de Earley en C#
• patrickhuber/pliant: un analizador Earley que integra las mejoras adoptadas por Marpa y demuestra el algoritmo de construcción de árboles de Elizabeth Scott.
• ellisonch/CFGLib - Biblioteca de gramática probabilística libre de contexto (PCFG) para C# (Earley + SPPF, CYK)

• Nearley: un analizador Earley que está comenzando a integrar las mejoras que adoptó Marpa
• Un analizador Earley del tamaño de una pinta: un analizador de juguete (con pseudocódigo anotado) para demostrar la técnica de Elizabeth Scott para construir el bosque de análisis empaquetado compartido
• lagodiuk/earley-parser-js: una pequeña implementación en JavaScript del analizador Earley (incluida la generación del bosque de análisis)
• digitalheir/probabilistic-earley-parser-javascript - Implementación en JavaScript del analizador probabilístico Earley

• Simple Earley: una implementación de un algoritmo de análisis simple similar a Earley, con documentación.

• Marpa::R2 – un módulo de Perl . Marpa Archivado el 7 de marzo de 2013 en Wayback Machine es un algoritmo de Earley que incluye las mejoras realizadas por Joop Leo y por Aycock y Horspool.
• Parse::Earley: un módulo Perl que implementa el algoritmo original de Jay Earley

• Lark: una implementación procedimental orientada a objetos de un analizador Earley, que genera un SPPF.
• NLTK: un conjunto de herramientas de Python con un analizador Earley
• Spark: un pequeño marco de lenguaje orientado a objetos para Python que implementa un analizador Earley
• spark_parser: versión actualizada y empaquetada del analizador Spark mencionado anteriormente, que se ejecuta tanto en Python 3 como en Python 2
• earley3.py: una implementación independiente del algoritmo en menos de 150 líneas de código, incluida la generación del bosque de análisis y las muestras
• tjr_python_earley_parser: un analizador Earley minimalista en Python
• Análisis de Earley: un tutorial del analizador de Earley bien explicado y completo en Python con manejo de épsilon y optimización de Leo para recursión derecha.

• Santiago: un kit de herramientas de análisis léxico y sintáctico para Rust que implementa un analizador Earley.

• CL-Earley-parser: una biblioteca Common Lisp que implementa un analizador Earley

• Charty-Racket: una implementación de Scheme - Racket de un analizador Earley

• properEarleyParser: una implementación mínima básica de un analizador Earley en el lenguaje de programación Wolfram con algunos casos de prueba esenciales.

• El compilador Accent-compilador Archivado el 18 de julio de 2011 en Wayback Machine