Analizador sintáctico
Un analizador sintáctico (parser) o simplemente analizador, es un programa informático que analiza una cadena de símbolos según las reglas de una gramática formal. El término proviene del latín pars, que significa parte (del discurso). Usualmente hace uso de un compilador, en cuyo caso, transforma una entrada en un árbol sintáctico de derivación.[1][2]
El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.
El lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.
Los analizadores sintácticos fueron extensivamente estudiados durante los años 1970, detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas generadores de analizadores sintáticos a partir de una especificación de la sintaxis del lenguaje en forma Backus-Naur por ejemplo, tales como yacc, GNU bison y javaCC.
Idiomas
Algunos sistemas de traducción o procesamiento de lenguajes naturales son léxicamente analizados por programas informáticos. Las frases no son fácilmente analizables debido a la carga de ambigüedad que existe en la estructura del idioma humano. Para procesar el idioma humano los investigadores deben antes ponerse de acuerdo en la gramática a utilizar y esta decisión está influenciada por criterios lingüísticos y computacionales, por ejemplo algunos sistemas de análisis usan gramáticas léxico-funcionales. Pero en general el análisis de gramáticas de este tipo es un NP-completo.
El «Head-driven phrase structure grammar» es otro formalismo que ha sido popular en la comunidad, pero los esfuerzos en investigación se han centrado en algoritmos menos complejos como el de Penn Treebank. El análisis ligero «Shallow parsing» se encarga sólo de encontrar los componentes principales de la frase como nombres o verbos. Otra estrategia popular para evitar la controversia lingüística es la gramática de dependencias.
La mayoría de los analizadores modernos son al menos en parte estadísticos, esto quiere decir que se basan en unos datos de entrenamiento que han sido analizados a mano. Este enfoque permite al sistema reunir información sobre la frecuencia con que ocurren ciertas construcciones en un contexto específico. Algunos de estos enfoques han incluido gramáticas libres de contexto probabilísticas, sistemas de máxima entropía y redes neuronales.
Los sistemas más exitosos usan estadísticas léxicas, es decir obtienen la categoría gramatical de las palabras, estos sistemas son vulnerables debido a que terminan por tener una cantidad excesiva de parámetros y finalmente requieren simplificaciones.
Los algoritmos de análisis de idioma natural no se pueden basar en gramáticas que tengan unas buenas características como se hace con las gramáticas diseñadas, por ejemplo para los lenguajes de programación. Algunos formalismos gramaticales son muy difíciles de analizar computacionalmente, por lo que, en general se usa una aproximación libre de contexto incluso si la estructura en sí no es libre de contexto para obtener una primera simplificación.
Los algoritmos que usan gramáticas libres de contexto se suelen basar en alguna variante del algoritmo Cocke-Younger-Kasami (CYK) y heurística para la poda de análisis infructuosos. En todo caso algunos enfoques sacrifican la velocidad por la precisión usando, por ejemplo, versiones lineales del algoritmo «shift-reduce». Enfoques recientemente desarrollados utilizan un algoritmo que genera de múltiples análisis y otro que escoge la mejor opción.
Lenguajes de programación
El uso más común de los analizadores sintácticos es como parte de la fase de análisis de los compiladores. De modo que tienen que analizar el código fuente del lenguaje. Los lenguajes de programación tienden a basarse en gramáticas libres de contexto, debido a que se pueden escribir analizadores rápidos y eficientes para estas.
Las gramáticas libres de contexto tienen una expresividad limitada y sólo pueden expresar un conjunto limitado de lenguajes. Informalmente la razón de esto es que la memoria de un lenguaje de este tipo es limitada, la gramática no puede recordar la presencia de una construcción en una entrada arbitrariamente larga y esto es necesario en un lenguaje en el que por ejemplo una variable debe ser declarada antes de que pueda ser referenciada. Las gramáticas más complejas no pueden ser analizadas de forma eficiente. Por estas razones es común crear un analizador permisivo para una gramática libre de contexto que acepta un superconjunto del lenguaje (acepta algunas construcciones inválidas), después del análisis inicial las construcciones incorrectas pueden ser filtradas.
Normalmente es fácil definir una gramática libre de contexto que acepte todas las construcciones de un lenguaje pero por el contrario es prácticamente imposible construir una gramática libre de contexto que admita solo las construcciones deseadas. En cualquier caso la mayoría de analizadores no son construidos a mano sino usando generadores automáticos.
Visión general del proceso
El siguiente caso demuestra un caso común de análisis de un lenguaje de programación con dos niveles de gramática, léxica y sintáctica.
El primer estado es la generación de tokens o análisis léxico, en este proceso la cadena de entrada se parte en símbolos con significado definidos por una gramática de expresiones regulares, por ejemplo un programa calculadora con la siguiente entrada: "12*(3+4)^2", la dividiría en los siguientes tokens 12, *, (, 3, +, 4, ), ^ y 2, cada uno de estos símbolos tiene un significado en el contexto de la expresión aritmética. El analizador contendrá reglas para indicar que los símbolos *, +, ^, ( y ) indican el comienzo de un nuevo token, de modo que otros tokens que no tendrían sentido como 12 o 13 no se generarán.
El siguiente estado es el análisis sintáctico lo que significa comprobar que los tokens forman una expresión válida, esto se hace usualmente usando una gramática libre de contexto que define recursivamente componentes que pueden aparecer en una expresión y el orden en que estos deben aparecer. Las reglas que definen un lenguaje de programación no siempre se pueden expresar usando únicamente una gramática libre de contexto, por ejemplo la validación de tipos y la declaración correcta de identificadores. Estas reglas pueden expresarse formalmente usando gramáticas de atributos.
La fase final es el análisis semántico, que trabaja en las implicaciones de la expresión ya validada y realiza las actuaciones pertinentes. En el caso de la calculadora, la acción es evaluar la expresión. Un compilador por el contrario generará código. Las gramáticas de atributos pueden ser usadas también para definir estas acciones.
Análisis de dependencias
Otro método para realizar análisis sintáctico o parsing es utilizando gramáticas de dependencias, que surgen como una alternativa a las estructuras de frases.[3] En términos generales estas gramáticas definen una relación de dependencia entre cada elemento de una construcción (por lo general son oraciones pero también pueden ser solo frases) y su "cabeza" (o head ).[4] Estos elementos pueden ser palabras, tokens, lemas o incluso signos de puntuación. Adicionalmente se denomina a un elemento 0 o "raíz" (root) a la cabeza del constituyente principal, generalmente el verbo principal de la oración. Es importante no confundir dependencias con constituyentes, ya que las relaciones de dependencia generan pares únicos y ordenados.
Los criterios para determinar la cabeza H de un dependiente D en una construcción C son los siguientes:[4][5]
- H determina la categoría sintáctica de C y H puede reemplazar a C.
- H determina la categoría semántica de C; D especifica a H.
- H es obligatoria; D puede ser opcional.
- H selecciona a D y determina si D es obligatoria.
- La forma de D depende de H (agreement o government).
- La posición linear de D es especificada con respecto a H.
Sin embargo estos criterios pueden generar contradicciones o inconsistencias con criterios morfológicos o semánticos y no siempre es claro si los dependientes son opcionales o no.
La tarea de los analizadores de dependencias es, dada una oración, determinar las cabezas y el tipo de dependencia de cada uno de los elementos. La ventaja de utilizar este tipo de análisis es que se pueden evitar ciertos problemas en lenguajes con orden de palabras poco estricto. Existen muchas formas distintas de clasificar los tipos de dependencias pero CoNLL (Conference on Computational Natural Language Learning)[6] ha creado un formato para uso universal en análisis sintácticos de dependencias: CoNLL-U
Los resultados de los últimos sistemas en diferentes pruebas de análisis sintáctico han sido compilados en el sitio de la tarea compartida (shared task), en el 2017 la tarea consistió en crear un analizador plurilingüe, es decir capaz de analizar diferentes idiomas.
Clasificación
La tarea esencial de un analizador es determinar si una determinada entrada puede ser derivada desde el símbolo inicial, usando las reglas de una gramática formal, y como hacer esto, existen esencialmente dos formas:
- Analizador sintáctico descendente (Top-Down-Parser): ..un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la entrada progresivamente en partes cada vez más pequeñas, de esta forma funcionan los analizadores LL, un ejemplo es el javaCC. Una mejora en estos parsers se puede logar usando GLR (Generalized Left-to-right Rightmost derivation).
- Analizador sintáctico ascendente (Bottom-Up-Parser): un analizador puede empezar con la entrada e intentar llegar hasta el símbolo inicial, intuitivamente el analizador intenta encontrar los símbolos más pequeños y progresivamente construir la jerarquía de símbolos hasta el inicial, los analizadores LR funcionan así y un ejemplo es el Yacc. También existen SLR (Simple LR) o los LALR (Look-ahead LR) como también de los GLL[7] (Generalized Left-to-right Leftmost derivation).
Otros tipos de analizadores son:
- Analizador sintáctico descendente recursivo
- Chart parser
- Left corner parser
- Analizador sintáctico LR
- Analizador sintáctico LALR
Referencias
- V., Aho, Alfred; V., Aho, Alfred (2007). Compilers : principles, techniques, & tools. Pearson/Addison Wesley. ISBN 0321486811. OCLC 70775643.
- 1955-, Jacobs, Ceriel J. H., (2008). Parsing techniques : a practical guide. Springer. ISBN 9780387202488. OCLC 191726482.
- A., Hudson, Richard (1991). English word grammar. B. Blackwell. ISBN 0631164332. OCLC 21333285.
- ↑ Zwicky, Arnold M. (1985). «Heads». Journal of Linguistics 21 (1): 1-29. doi:10.2307/4175761. Consultado el 27 de octubre de 2017.
- A., Hudson, Richard (2010). An introduction to word grammar. Cambridge University Press. ISBN 9780521896900. OCLC 670430028.
- «CoNLL 2017 | CoNLL». www.conll.org (en inglés). Consultado el 27 de octubre de 2017.
- Scott, Elizabeth; Johnstone, Adrian (17 de septiembre de 2010). «GLL Parsing». Electronic Notes in Theoretical Computer Science. Proceedings of the Ninth Workshop on Language Descriptions Tools and Applications (LDTA 2009) 253 (7): 177-189. doi:10.1016/j.entcs.2010.08.041. Consultado el 25 de junio de 2017.