En ciencias de la computación , el analizador de 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 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 sintáctico en lingüística computacional . Fue introducido por primera vez en su disertación [2] en 1968 (y luego apareció de forma abreviada, más legible, en una revista [3] ).
Los analizadores sintácticos Earley son atractivos porque pueden analizar todos los lenguajes libres de contexto, a diferencia de los analizadores sintácticos LR y LL , que se utilizan con más frecuencia en compiladores pero que solo pueden manejar clases restringidas de lenguajes. El analizador de 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 a la izquierda .
Reconocedor de Earley
El siguiente algoritmo describe el reconocedor de Earley. El reconocedor se puede modificar fácilmente 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 de arriba hacia abajo . 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. Posición de entrada n es la posición después de aceptar la n º token. (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 actualmente emparejada (X → α β)
- la posición actual en esa producción (representada por el punto)
- la posición i en la entrada en la que comenzó el emparejamiento de esta producción: la posición de origen
(El algoritmo original de Earley incluía una anticipación en el estado; investigaciones posteriores mostraron 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 se inicia con S (0) que consta solo de la regla de nivel superior. El analizador luego 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), sume (Y → • γ, k ) a S ( k ) para cada producción en la gramática con Y en el lado izquierdo (Y → γ).
- Exploración : Si a es el siguiente símbolo en el flujo de entrada, para cada estado en S ( k ) de la forma (X → α • a β, j ), sume (X → α a • β, j ) a S ( k +1).
- Finalización : 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 sume (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 se implementa generalmente como una cola de estados para procesar, y la operación a realizar depende del tipo de estado en el que se encuentre.
El algoritmo acepta si (X → γ •, 0) termina en S ( n ), donde (X → γ) es la regla de nivel superior yn la longitud de entrada; de lo contrario, rechaza.
Pseudocódigo
Adaptado de Speech and Language Processing [5] por Daniel Jurafsky y James H. Martin,
DECLARAR ARRAY S;función INIT (palabras) S ← CREAR-ARRAY (LONGITUD (palabras) + 1) para k ← de 0 a LENGTH (palabras) hacer S [k] ← EMPTY-ORDERED-SETfunción EARLEY-PARSE (palabras, gramática) INIT (palabras) AÑADIR A AJUSTAR ((γ → • S, 0), S [0]) para k ← de 0 a LENGTH (palabras) hacer para cada estado en S [k] do // S [k] puede expandirse durante este ciclo si no está TERMINADO (indicar) entonces si NEXT-ELEMENT-OF (estado) es un no terminal, entonces PREDICTOR (estado, k, gramática) // no terminal más hacer ESCÁNER (estado, k, palabras) // terminal más hacer COMPLETAR (estado, k) final final tabla de devolucionesprocedimiento PREDICTOR ((A → α • Bβ, j), k, gramática) para cada (B → γ) en GRAMMAR-REGLAS-PARA (B, gramática) hacer AÑADIR A AJUSTAR ((B → • γ, k), S [k]) finalprocedimiento ESCÁNER ((A → α • aβ, j), k, palabras) si una ⊂ PARTES DEL HABLA (palabras [k]) entonces AÑADIR A CONJUNTO ((A → αa • β, j), S [k + 1]) finalprocedimiento COMPLETAR ((B → γ •, x), k) para cada (A → α • Bβ, j) en S [x] hacer AÑADIR AL CONJUNTO ((A → αB • β, j), S [k]) final
Ejemplo
Considere la siguiente gramática simple para expresiones aritméticas:
:: = # la regla de inicio
:: = "+" | :: = "*" | :: = "1" | "2" | "3" | "4"
Con la entrada:
2 + 3 * 4
Esta es la secuencia de conjuntos de estados:
(indicar no.) | Producción | (Origen) | Comentario |
---|---|---|---|
S (0): • 2 + 3 * 4 | |||
1 | P → • S | 0 | regla de inicio |
2 | S → • S + M | 0 | predecir a partir de (1) |
3 | S → • M | 0 | predecir a partir de (1) |
4 | M → • M * T | 0 | predecir a partir de (3) |
5 | M → • T | 0 | predecir a partir de (3) |
6 | T → • número | 0 | predecir a partir de (5) |
S (1): 2 • + 3 * 4 | |||
1 | T → número • | 0 | escanear desde S (0) (6) |
2 | M → T • | 0 | completar de (1) y S (0) (5) |
3 | M → M • * T | 0 | completar de (2) y S (0) (4) |
4 | S → M • | 0 | completar de (2) y S (0) (3) |
5 | S → S • + M | 0 | completar de (4) y S (0) (2) |
6 | P → S • | 0 | completar de (4) y S (0) (1) |
S (2): 2 + • 3 * 4 | |||
1 | S → S + • M | 0 | escanear desde S (1) (5) |
2 | M → • M * T | 2 | predecir a partir de (1) |
3 | M → • T | 2 | predecir a partir de (1) |
4 | T → • número | 2 | predecir a partir de (3) |
S (3): 2 + 3 • * 4 | |||
1 | T → número • | 2 | escanear desde S (2) (4) |
2 | M → T • | 2 | completar de (1) y S (2) (3) |
3 | M → M • * T | 2 | completar de (2) y S (2) (2) |
4 | S → S + M • | 0 | completar de (2) y S (2) (1) |
5 | S → S • + M | 0 | completar de (4) y S (0) (2) |
6 | P → S • | 0 | completar de (4) y S (0) (1) |
S (4): 2 + 3 * • 4 | |||
1 | M → M * • T | 2 | escanear desde S (3) (3) |
2 | T → • número | 4 | predecir a partir de (1) |
S (5): 2 + 3 * 4 • | |||
1 | T → número • | 4 | escanear desde S (4) (2) |
2 | M → M * T • | 2 | completar de (1) y S (4) (1) |
3 | M → M • * T | 2 | completar de (2) y S (2) (2) |
4 | S → S + M • | 0 | completar de (2) y S (2) (1) |
5 | S → S • + M | 0 | completar de (4) y S (0) (2) |
6 | P → S • | 0 | completar de (4) y S (0) (1) |
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 [6] 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ó [7] que esto no toma en cuenta las relaciones entre símbolos, por lo que si consideramos la gramática S → SS | by la cadena bbb, solo observa que cada S puede coincidir con una o dos b, y por lo tanto produce derivaciones falsas para bb y bbbb, así como las dos derivaciones correctas para bbb.
Otro método [8] 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 Elemento LR (0) (regla de producción con punto), e iyj dan la sección de la cadena de entrada derivada por este nodo. El contenido de un nodo es un par de apuntadores secundarios que dan una única derivación, o una lista de nodos "empaquetados", cada uno de los cuales contiene un par de apuntadores 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 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 avanza 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 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.
Ver también
Citas
- ^ Kegler, Jeffrey. "¿Qué es el algoritmo Marpa?" . Consultado el 20 de agosto de 2013 .
- ^ Earley, Jay (1968). Un algoritmo de análisis eficiente sin contexto (PDF) . Disertación Carnegie-Mellon.
- ^ Earley, Jay (1970), "Un algoritmo de análisis sin contexto eficiente" (PDF) , Communications of the ACM , 13 (2): 94–102, doi : 10.1145 / 362007.362035 , S2CID 47032707 , archivado desde el original (PDF) el 2004-07-08
- ^ John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Lectura / MA: Addison-Wesley. ISBN 978-0-201-02988-8. p.145
- ^ Jurafsky, D. (2009). Procesamiento del habla y el lenguaje: Introducción al procesamiento del lenguaje natural, la lingüística computacional y el reconocimiento del habla . Pearson Prentice Hall. ISBN 9780131873216.
- ^ Earley, Jay (1968). Un algoritmo de análisis eficiente sin contexto (PDF) . Disertación Carnegie-Mellon. pag. 106.
- ^ Tomita, Masaru (17 de abril de 2013). Análisis eficiente del lenguaje natural: un algoritmo rápido para sistemas prácticos . Springer Science and Business Media. pag. 74. ISBN 978-1475718850. Consultado el 16 de septiembre de 2015 .
- ^ Scott, Elizabeth (1 de abril de 2008). "Análisis de estilo SPPF de los reconocedores de Earley" . Notas electrónicas en informática teórica . 203 (2): 53–67. doi : 10.1016 / j.entcs.2008.03.044 .
Otros materiales de referencia
- Aycock, John; Horspool, R. Nigel (2002). "Análisis 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 libre de contexto general que se ejecuta en tiempo lineal en cada gramática LR ( k ) sin usar anticipación", Informática teórica , 82 (1): 165-176, doi : 10.1016 / 0304 -3975 (91) 90 180-A , MR 1112117
- Tomita, Masaru (1984). "Analizadores sintácticos LR para lenguajes naturales" (PDF) . COLING . X Congreso Internacional de Lingüística Computacional. págs. 354–357.
Implementaciones
C, C ++
- 'Yet Another Earley Parser (YAEP)' - Bibliotecas C / C ++
- 'C Earley Parser' - un analizador Earley C
Haskell
- 'Earley' : un analizador DSL de Earley en Haskell
Java
- [1] - una implementación Java del algoritmo Earley
- PEN : una biblioteca de Java que implementa el algoritmo Earley
- Pep : una biblioteca de 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 de Java que implementa el algoritmo probabilístico de Earley, que es útil para determinar el árbol de análisis más probable a partir de una oración ambigua
C#
- coonsta / earley : un analizador de Earley en C #
- patrickhuber / pliant : un analizador de 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 libre de contexto probabilístico (PCFG) para C # (Earley + SPPF, CYK)
JavaScript
- Nearley : un analizador de Earley que está comenzando a integrar las mejoras que adoptó Marpa
- Un analizador de 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 compactado compartido
- lagodiuk / earley-parser-js : una pequeña implementación de JavaScript del analizador Earley (incluida la generación del bosque de análisis)
- digitalheir / probabilistic-earley-parser-javascript - Implementación de JavaScript del analizador probabilístico de Earley
OCaml
- Simple Earley : una implementación de un algoritmo de análisis simple similar a Earley, con documentación.
Perl
- Marpa :: R2 - un módulo de Perl . Marpa es un algoritmo de Earley que incluye las mejoras realizadas por Joop Leo y por Aycock y Horspool.
- Parse :: Earley : un módulo de Perl que implementa el algoritmo original de Jay Earley
Pitón
- Lark : una implementación de procedimiento orientada a objetos de un analizador de 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 anterior, 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 mínimo en Python
Lisp común
- CL-Earley-parser : una biblioteca Common Lisp que implementa un analizador Earley
Esquema, Raqueta
- Charty-Racket - a Scheme - Implementación de raqueta de un analizador Earley
Recursos
- El compilador-compilador de Accent