Analizador sintáctico

Un analizador sintáctico (o parser) es una de las partes de un compilador que transforma su entrada en un árbol de derivación.

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 análisis sintáctico también es un estado inicial del análisis de frases de 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 humanos

Algunos sistemas de traducción o procesamiento de idioma natural 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.

Other Languages