El análisis sintáctico , análisis sintáctico o análisis sintáctico es el proceso de analizar una cadena de símbolos , ya sea en lenguaje natural , lenguajes informáticos o estructuras de datos , de acuerdo con las reglas de una gramática formal . El término análisis sintáctico proviene del latín pars ( orationis ), que significa parte (del discurso) . [1]
El término tiene significados ligeramente diferentes en distintas ramas de la lingüística y la informática . El análisis sintáctico tradicional de oraciones se realiza a menudo como un método para comprender el significado exacto de una oración o palabra, a veces con la ayuda de dispositivos como los diagramas de oraciones . Por lo general, enfatiza la importancia de las divisiones gramaticales como sujeto y predicado .
En lingüística computacional, el término se utiliza para referirse al análisis formal por parte de una computadora de una oración u otra cadena de palabras en sus constituyentes, lo que da como resultado un árbol de análisis que muestra su relación sintáctica entre sí, que también puede contener información semántica . [ cita requerida ] Algunos algoritmos de análisis generan un bosque de análisis o una lista de árboles de análisis a partir de una cadena que es sintácticamente ambigua . [2]
El término también se utiliza en psicolingüística para describir la comprensión del lenguaje. En este contexto, el análisis sintáctico se refiere a la forma en que los seres humanos analizan una oración o frase (en lenguaje hablado o texto) "en términos de constituyentes gramaticales, identificación de las partes del discurso, relaciones sintácticas, etc." [1] Este término es especialmente común cuando se habla de qué señales lingüísticas ayudan a los hablantes a interpretar oraciones sencillas .
En informática, el término se utiliza en el análisis de lenguajes informáticos , haciendo referencia al análisis sintáctico del código de entrada en sus partes componentes con el fin de facilitar la escritura de compiladores e intérpretes . El término también puede utilizarse para describir una división o separación.
El ejercicio gramatical tradicional del análisis sintáctico, a veces conocido como análisis de cláusulas , implica descomponer un texto en sus partes componentes del discurso con una explicación de la forma, función y relación sintáctica de cada parte. [3] Esto se determina en gran parte a partir del estudio de las conjugaciones y declinaciones del idioma , que pueden ser bastante intrincadas para idiomas con mucha inflexión . Para analizar una frase como "man bites dog" (hombre muerde perro), es necesario observar que el sustantivo singular "man" (hombre) es el sujeto de la oración, el verbo "bites" (muerde) es la tercera persona del singular del tiempo presente del verbo "to bite" (morder) y el sustantivo singular "dog" (perro) es el objeto de la oración. A veces se utilizan técnicas como los diagramas de oraciones para indicar la relación entre los elementos de la oración.
En el pasado, el análisis sintáctico era fundamental para la enseñanza de la gramática en todo el mundo angloparlante y se consideraba en general fundamental para el uso y la comprensión del lenguaje escrito. Sin embargo, la enseñanza general de estas técnicas ya no es habitual. [ cita requerida ]
En algunos sistemas de traducción automática y procesamiento del lenguaje natural , los textos escritos en lenguajes humanos son analizados por programas informáticos. [4] Los programas no analizan fácilmente las oraciones humanas, ya que existe una ambigüedad sustancial en la estructura del lenguaje humano, cuyo uso es transmitir significado (o semántica ) entre una gama potencialmente ilimitada de posibilidades, pero solo algunas de las cuales son pertinentes para el caso particular. [5] Por lo tanto, un enunciado "Hombre muerde a perro" frente a "Perro muerde a hombre" es definido en un detalle, pero en otro idioma podría aparecer como "Hombre perro muerde" con una dependencia del contexto más amplio para distinguir entre esas dos posibilidades, si de hecho esa diferencia fuera motivo de preocupación. Es difícil preparar reglas formales para describir el comportamiento informal, aunque esté claro que se están siguiendo algunas reglas. [ cita requerida ]
Para analizar datos de lenguaje natural, los investigadores primero deben ponerse de acuerdo sobre la gramática que se utilizará. La elección de la sintaxis se ve afectada tanto por preocupaciones lingüísticas como computacionales; por ejemplo, algunos sistemas de análisis utilizan la gramática funcional léxica , pero en general, se sabe que el análisis de gramáticas de este tipo es NP-completo . La gramática de estructura de frase impulsada por la cabeza es otro formalismo lingüístico que ha sido popular en la comunidad de análisis, pero otros esfuerzos de investigación se han centrado en formalismos menos complejos como el utilizado en Penn Treebank . El análisis superficial tiene como objetivo encontrar solo los límites de los constituyentes principales, como las frases nominales. Otra estrategia popular para evitar la controversia lingüística es el análisis de gramática de dependencia .
La mayoría de los analizadores sintácticos modernos son, al menos en parte, estadísticos; es decir, se basan en un corpus de datos de entrenamiento que ya han sido anotados (analizados a mano). Este enfoque permite al sistema recopilar información sobre la frecuencia con la que se producen varias construcciones en contextos específicos. (Véase aprendizaje automático ). Los enfoques que se han utilizado incluyen PCFGs sencillos (gramáticas probabilísticas libres de contexto), [6] entropía máxima [7] y redes neuronales [8] . La mayoría de los sistemas más exitosos utilizan estadísticas léxicas (es decir , consideran las identidades de las palabras involucradas, así como su parte del discurso ). Sin embargo, estos sistemas son vulnerables al sobreajuste y requieren algún tipo de suavizado para ser efectivos. [ cita requerida ]
Los algoritmos de análisis para lenguaje natural no pueden depender de que la gramática tenga propiedades "agradables" como sucede con las gramáticas diseñadas manualmente para lenguajes de programación. Como se mencionó anteriormente, algunos formalismos gramaticales son muy difíciles de analizar computacionalmente; en general, incluso si la estructura deseada no es libre de contexto , se utiliza algún tipo de aproximación libre de contexto a la gramática para realizar un primer paso. Los algoritmos que utilizan gramáticas libres de contexto a menudo se basan en alguna variante del algoritmo CYK , generalmente con alguna heurística para eliminar los análisis improbables para ahorrar tiempo. (Véase análisis de gráficos ). Sin embargo, algunos sistemas intercambian velocidad por precisión utilizando, por ejemplo, versiones de tiempo lineal del algoritmo shift-reduce . Un desarrollo algo reciente ha sido la reclasificación del análisis en el que el analizador propone una gran cantidad de análisis y un sistema más complejo selecciona la mejor opción. [ cita requerida ] En aplicaciones de comprensión del lenguaje natural , los analizadores semánticos convierten el texto en una representación de su significado. [9]
En psicolingüística , el análisis sintáctico no solo implica la asignación de palabras a categorías (formación de conocimientos ontológicos), sino también la evaluación del significado de una oración según las reglas de sintaxis extraídas de las inferencias realizadas a partir de cada palabra de la oración (lo que se conoce como connotación ). Esto normalmente ocurre mientras se escuchan o leen las palabras.
En general, la neurolingüística entiende que el análisis sintáctico es una función de la memoria de trabajo, lo que significa que el análisis sintáctico se utiliza para mantener en funcionamiento en la mente varias partes de una oración al mismo tiempo, todas ellas fácilmente accesibles para su análisis según sea necesario. Dado que la memoria de trabajo humana tiene limitaciones, también las tiene la función de análisis sintáctico de oraciones. [10] Esto se evidencia en varios tipos diferentes de oraciones sintácticamente complejas que plantean posibles problemas para el análisis mental de oraciones.
El primer tipo de oración, y quizás el más conocido, que desafía la capacidad de análisis sintáctico es la oración de camino de jardín. Estas oraciones están diseñadas de modo que la interpretación más común de la oración parezca gramaticalmente defectuosa, pero al examinarlas más de cerca, estas oraciones son gramaticalmente correctas. Las oraciones de camino de jardín son difíciles de analizar sintácticamente porque contienen una frase o una palabra con más de un significado, y a menudo su significado más típico es una parte diferente del discurso. [11] Por ejemplo, en la oración "el caballo corrió más allá del granero caído", corrió inicialmente se interpreta como un verbo en tiempo pasado, pero en esta oración funciona como parte de una frase adjetiva. [12] Dado que el análisis sintáctico se utiliza para identificar partes del discurso, estas oraciones desafían la capacidad de análisis sintáctico del lector.
Otro tipo de oración que es difícil de analizar es una ambigüedad de adjunto, que incluye una frase que potencialmente podría modificar diferentes partes de una oración y, por lo tanto, presenta un desafío para identificar la relación sintáctica (por ejemplo, "El niño vio a la dama con el telescopio", en el que la frase ambigua con el telescopio podría modificar al niño vio o a la dama). [11]
Un tercer tipo de oración que desafía la capacidad de análisis es la incrustación central, en la que las frases se colocan en el centro de otras frases formadas de manera similar (por ejemplo, "La rata que el gato que el hombre golpeó persiguió corrió hacia la trampa"). Las oraciones con 2 o, en los casos más extremos, 3 incrustaciones centrales son un desafío para el análisis mental, nuevamente debido a la ambigüedad de la relación sintáctica. [13]
En el campo de la neurolingüística existen múltiples teorías que pretenden describir cómo se lleva a cabo el análisis sintáctico en el cerebro. Uno de estos modelos es el modelo generativo más tradicional de procesamiento de oraciones, que teoriza que dentro del cerebro hay un módulo distinto diseñado para el análisis sintáctico de oraciones, que es precedido por el acceso al reconocimiento y recuperación léxica, y luego seguido por el procesamiento sintáctico que considera un único resultado sintáctico del análisis sintáctico, y solo vuelve a revisar esa interpretación sintáctica si se detecta un problema potencial. [14] El modelo opuesto, más contemporáneo, teoriza que dentro de la mente, el procesamiento de una oración no es modular, ni ocurre en una secuencia estricta. Más bien, plantea que se pueden considerar varias posibilidades sintácticas diferentes al mismo tiempo, porque el acceso léxico, el procesamiento sintáctico y la determinación del significado ocurren en paralelo en el cerebro. De esta manera, estos procesos están integrados. [15]
Aunque todavía queda mucho por aprender sobre la neurología del análisis sintáctico, los estudios han demostrado evidencia de que varias áreas del cerebro podrían desempeñar un papel en el análisis sintáctico. Estas incluyen el polo temporal anterior izquierdo, el giro frontal inferior izquierdo, el giro temporal superior izquierdo, el giro frontal superior izquierdo, la corteza cingulada posterior derecha y el giro angular izquierdo. Aunque no se ha demostrado absolutamente, se ha sugerido que estas diferentes estructuras podrían favorecer el análisis sintáctico de la estructura de la frase o el análisis sintáctico de la estructura de la dependencia, lo que significa que diferentes tipos de análisis sintáctico podrían procesarse de diferentes maneras que aún no se han comprendido. [16]
El análisis del discurso examina las formas de analizar el uso del lenguaje y los acontecimientos semióticos. El lenguaje persuasivo puede denominarse retórica .
Un analizador sintáctico es un componente de software que toma datos de entrada (normalmente texto) y construye una estructura de datos (a menudo algún tipo de árbol de análisis sintáctico , árbol de sintaxis abstracta u otra estructura jerárquica) que proporciona una representación estructural de la entrada mientras comprueba la sintaxis correcta. El análisis sintáctico puede ir precedido o seguido de otros pasos, o bien pueden combinarse en un único paso. El analizador sintáctico suele ir precedido de un analizador léxico independiente , que crea tokens a partir de la secuencia de caracteres de entrada; alternativamente, estos pueden combinarse en un análisis sintáctico sin escáner . Los analizadores sintácticos pueden programarse a mano o pueden generarse de forma automática o semiautomática mediante un generador de analizadores sintácticos . El análisis sintáctico es complementario a la creación de plantillas , que produce una salida formateada . Estas pueden aplicarse a diferentes dominios, pero a menudo aparecen juntas, como el par scanf / printf , o las etapas de entrada (análisis sintáctico del front-end) y salida (generación de código del back-end) de un compilador .
La entrada a un analizador es típicamente texto en algún lenguaje de programación , pero también puede ser texto en un lenguaje natural o datos textuales menos estructurados, en cuyo caso generalmente solo se extraen ciertas partes del texto, en lugar de construir un árbol de análisis. Los analizadores varían desde funciones muy simples como scanf , hasta programas complejos como el frontend de un compilador de C++ o el analizador HTML de un navegador web . Una clase importante de análisis simple se realiza utilizando expresiones regulares , en las que un grupo de expresiones regulares define un lenguaje regular y un motor de expresiones regulares genera automáticamente un analizador para ese lenguaje, lo que permite la coincidencia de patrones y la extracción de texto. En otros contextos, las expresiones regulares se utilizan en cambio antes del análisis, como el paso de análisis léxico cuya salida es luego utilizada por el analizador.
El uso de analizadores varía según la entrada. En el caso de los lenguajes de datos, un analizador se suele encontrar como la facilidad de lectura de archivos de un programa, como la lectura de texto HTML o XML ; estos ejemplos son lenguajes de marcado . En el caso de los lenguajes de programación , un analizador es un componente de un compilador o intérprete , que analiza el código fuente de un lenguaje de programación informática para crear alguna forma de representación interna; el analizador es un paso clave en la interfaz del compilador . Los lenguajes de programación tienden a especificarse en términos de una gramática determinista libre de contexto porque se pueden escribir analizadores rápidos y eficientes para ellos. Para los compiladores, el análisis en sí puede realizarse en una o varias pasadas; consulte compilador de una sola pasada y compilador de varias pasadas .
Las desventajas implícitas de un compilador de una sola pasada se pueden superar en gran medida añadiendo correcciones , donde se prevé la reubicación del código durante la pasada hacia adelante, y las correcciones se aplican hacia atrás cuando se reconoce que el segmento de programa actual se ha completado. Un ejemplo en el que un mecanismo de corrección de este tipo sería útil sería una instrucción GOTO hacia adelante, donde el objetivo de GOTO es desconocido hasta que se completa el segmento de programa. En este caso, la aplicación de la corrección se retrasaría hasta que se reconociera el objetivo de GOTO. Por el contrario, una instrucción GOTO hacia atrás no requiere una corrección, ya que la ubicación ya se conocerá.
Las gramáticas libres de contexto tienen limitaciones en cuanto a la capacidad de expresar todos los requisitos de un lenguaje. De manera informal, la razón 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; esto es necesario para un lenguaje en el que, por ejemplo, se debe declarar un nombre antes de poder hacer referencia a él. Sin embargo, las gramáticas más potentes que pueden expresar esta restricción no se pueden analizar de manera eficiente. Por lo tanto, una estrategia común es crear un analizador relajado para una gramática libre de contexto que acepte un superconjunto de las construcciones del lenguaje deseadas (es decir, que acepte algunas construcciones no válidas); más tarde, las construcciones no deseadas se pueden filtrar en el paso de análisis semántico (análisis contextual).
Por ejemplo, en Python el siguiente es un código sintácticamente válido:
x = 1 imprimir ( x )Sin embargo, el código siguiente es sintácticamente válido en términos de la gramática libre de contexto, produciendo un árbol de sintaxis con la misma estructura que el anterior, pero viola la regla semántica que requiere que las variables se inicialicen antes de su uso:
x = 1 imprimir ( y )El siguiente ejemplo demuestra el caso común de análisis de un lenguaje informático con dos niveles de gramática: léxico y sintáctico.
La primera etapa es la generación de tokens, o análisis léxico , mediante el cual el flujo de caracteres de entrada se divide en símbolos significativos definidos por una gramática de expresiones regulares . Por ejemplo, un programa de calculadora analizaría una entrada como " 12 * (3 + 4)^2" y la dividiría en los tokens 12, *, (, 3, +, 4, ), ^, 2, cada uno de los cuales es un símbolo significativo en el contexto de una expresión aritmética. El analizador léxico contendría reglas para indicarle que los caracteres *, +, ^, (y marcan el comienzo de un nuevo token, por lo que no se generarán )tokens sin significado como " 12*" o " ".(3
La siguiente etapa es el análisis sintáctico, que consiste en comprobar que los tokens forman una expresión permitida. Esto se hace normalmente con referencia a una gramática libre de contexto que define de forma recursiva los componentes que pueden formar una expresión y el orden en el que deben aparecer. Sin embargo, no todas las reglas que definen los lenguajes de programación se pueden expresar únicamente mediante gramáticas libres de contexto, por ejemplo, la validez de tipos y la declaración adecuada de identificadores. Estas reglas se pueden expresar formalmente con gramáticas de atributos .
La fase final es el análisis semántico , que consiste en determinar las implicaciones de la expresión que se acaba de validar y tomar la acción adecuada. [17] En el caso de una calculadora o intérprete, la acción consiste en evaluar la expresión o el programa; un compilador, por otro lado, generaría algún tipo de código. Las gramáticas de atributos también se pueden utilizar para definir estas acciones.
La tarea del analizador es básicamente determinar si la entrada puede derivarse del símbolo inicial de la gramática y cómo hacerlo. Esto se puede hacer básicamente de dos maneras:
Los analizadores sintácticos LL y los analizadores sintácticos de descenso recursivo son ejemplos de analizadores sintácticos de arriba hacia abajo que no pueden adaptarse a las reglas de producción recursiva por la izquierda . Aunque se ha creído que las implementaciones simples de análisis sintáctico de arriba hacia abajo no pueden adaptarse a la recursión por la izquierda directa e indirecta y pueden requerir una complejidad espacial y temporal exponencial al analizar gramáticas ambiguas libres de contexto , Frost, Hafiz y Callaghan [20] [21] han creado algoritmos más sofisticados para el análisis sintáctico de arriba hacia abajo que se adaptan a la ambigüedad y la recursión por la izquierda en tiempo polinomial y que generan representaciones de tamaño polinomial del número potencialmente exponencial de árboles de análisis sintáctico. Su algoritmo puede producir derivaciones tanto de más a la izquierda como de más a la derecha de una entrada con respecto a una gramática libre de contexto dada .
Una distinción importante con respecto a los analizadores sintácticos es si un analizador sintáctico genera una derivación más a la izquierda o una derivación más a la derecha (ver gramática libre de contexto ). Los analizadores sintácticos LL generarán una derivación más a la izquierda y los analizadores sintácticos LR generarán una derivación más a la derecha (aunque generalmente a la inversa). [18]
AlgunoSe han diseñado algoritmos de análisis gráfico para lenguajes de programación visual.[22][23]Los analizadores para lenguajes visuales a veces se basan engramáticas gráficas.[24]
Se han utilizado algoritmos de análisis adaptativo para construir interfaces de usuario de lenguaje natural "autoextensibles" . [25]
Una implementación de analizador simple lee el archivo de entrada completo, realiza un cálculo o traducción intermedio y luego escribe el archivo de salida completo, como los compiladores de múltiples pasadas en memoria .
Enfoques alternativos de implementación del analizador:
Algunas de las herramientas de desarrollo de analizadores más conocidas incluyen las siguientes:
int v;main(){vEl lookahead establece la cantidad máxima de tokens entrantes que un analizador puede usar para decidir qué regla debe usar. El lookahead es especialmente relevante para los analizadores LL , LR y LALR , donde a menudo se indica explícitamente agregando el lookahead al nombre del algoritmo entre paréntesis, como LALR(1).
La mayoría de los lenguajes de programación , el objetivo principal de los analizadores sintácticos, están cuidadosamente definidos de tal manera que un analizador sintáctico con una lectura anticipada limitada, normalmente uno, puede analizarlos, porque los analizadores sintácticos con una lectura anticipada limitada suelen ser más eficientes. Un cambio importante [ cita requerida ] en esta tendencia se produjo en 1990 cuando Terence Parr creó ANTLR para su tesis doctoral, un generador de analizadores sintácticos para analizadores sintácticos LL( k ) eficientes, donde k es cualquier valor fijo.
Los analizadores LR suelen tener solo unas pocas acciones después de ver cada token. Son: desplazamiento (agregar este token a la pila para una reducción posterior), reducción (extraer tokens de la pila y formar una construcción sintáctica), fin, error (no se aplica ninguna regla conocida) o conflicto (no se sabe si se debe desplazar o reducir).
La previsión tiene dos ventajas. [ aclaración necesaria ]
Ejemplo: Análisis de la expresión 1 + 2 * 3 [ dudoso – discutir ]
La mayoría de los lenguajes de programación (excepto algunos como APL y Smalltalk) y las fórmulas algebraicas dan mayor prioridad a la multiplicación que a la suma, en cuyo caso la interpretación correcta del ejemplo anterior es 1 + (2 * 3) . Tenga en cuenta que la regla 4 anterior es una regla semántica. Es posible reescribir la gramática para incorporarla a la sintaxis. Sin embargo, no todas estas reglas se pueden traducir a la sintaxis.
Entrada inicial = [1, +, 2, *, 3]
El árbol de análisis y el código resultante no son correctos según la semántica del lenguaje.
Para analizar correctamente sin lookahead, hay tres soluciones:
El árbol de análisis generado es correcto y simplemente más eficiente [ aclaración ] [ cita requerida ] que los analizadores sin lookahead. Esta es la estrategia que se sigue en los analizadores LALR .
{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)