El análisis sintáctico , análisis de sintaxis 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 , conforme a las reglas de una gramática formal . El término análisis proviene del latín pars ( orationis ), que significa parte (del discurso) . [1]
El término tiene significados ligeramente diferentes en diferentes ramas de la lingüística y la informática . El análisis de oraciones tradicional se realiza a menudo como método para comprender el significado exacto de una oración o palabra, a veces con la ayuda de dispositivos como diagramas de oraciones . Suele enfatizar la importancia de las divisiones gramaticales como sujeto y predicado .
Dentro de la lingüística computacional, el término se utiliza para referirse al análisis formal realizado por 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 necesaria ] Algunos algoritmos de análisis pueden generar un bosque de análisis o una lista de árboles de análisis para una entrada 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 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, identificando las partes del discurso, relaciones sintácticas, etc." [1] Este término es especialmente común cuando se analiza qué señales lingüísticas ayudan a los hablantes a interpretar oraciones en el camino del jardín .
Dentro de la informática, el término se utiliza en el análisis de lenguajes informáticos , refiriéndose 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 usarse para describir una escisión o separación.
El ejercicio gramatical tradicional de análisis, a veces conocido como análisis de cláusulas , implica dividir un texto en las partes que lo componen 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 complejas para idiomas con muchas flexiones . Analizar una frase como "el hombre muerde al perro" implica observar que el sustantivo singular "hombre" es el sujeto de la oración, el verbo "muerde" es la tercera persona del singular del tiempo presente del verbo "morder" y el sustantivo singular "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.
Anteriormente, el análisis sintáctico era fundamental para la enseñanza de la gramática en todo el mundo de habla inglesa y, en general, se lo consideraba básico para el uso y la comprensión del lenguaje escrito. Sin embargo, la enseñanza general de tales técnicas ya no es actual. [ cita necesaria ]
En algunos sistemas de traducción automática y procesamiento de lenguaje natural , los textos escritos en lenguajes humanos son analizados mediante 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. el caso concreto. [5] Por lo tanto, una expresión "El hombre muerde al perro" frente a "El perro muerde al hombre" es definitiva en un detalle, pero en otro idioma podría aparecer como "El hombre muerde al perro" basándose en el contexto más amplio para distinguir entre esas dos posibilidades, si es que efectivamente esa diferencia era motivo de preocupación. Es difícil preparar reglas formales para describir el comportamiento informal aunque esté claro que algunas reglas se siguen. [ cita necesaria ]
Para analizar datos del 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 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 frases basada en la cabeza es otro formalismo lingüístico que ha sido popular en la comunidad de análisis sintáctico, 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 sólo los límites de los constituyentes principales, como las frases nominales. Otra estrategia popular para evitar controversias lingüísticas es el análisis de la gramática de dependencia .
La mayoría de los analizadores modernos son al menos parcialmente estadísticos ; es decir, se basan en un corpus de datos de entrenamiento que ya han sido anotados (analizados a mano). Este enfoque permite que el sistema recopile información sobre la frecuencia con la que ocurren diversas construcciones en contextos específicos. (Ver aprendizaje automático .) Los enfoques que se han utilizado incluyen PCFG (gramáticas probabilísticas libres de contexto) sencillas, [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, dichos sistemas son vulnerables al sobreajuste y requieren algún tipo de suavizado para ser efectivos. [ cita necesaria ]
Los algoritmos de análisis de lenguaje natural no pueden depender de que la gramática tenga propiedades "agradables" como ocurre 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 está libre de contexto , se utiliza algún tipo de aproximación a la gramática libre de contexto para realizar una primera pasada. 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 análisis improbables y ahorrar tiempo. (Ver análisis de gráficos ). Sin embargo, algunos sistemas intercambian velocidad por precisión utilizando, por ejemplo, versiones de tiempo lineal del algoritmo de reducción de desplazamiento . Un desarrollo algo reciente ha sido la reclasificación de análisis en la que el analizador propone una gran cantidad de análisis y un sistema más complejo selecciona la mejor opción. [ cita necesaria ] 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 implica no sólo 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 de acuerdo con las reglas de sintaxis extraídas mediante inferencias hechas a partir de cada palabra de la oración (conocido como connotación ). . Esto normalmente ocurre cuando se escuchan o leen palabras.
La neurolingüística generalmente entiende que el análisis es una función de la memoria de trabajo, lo que significa que el análisis se utiliza para mantener en juego en la mente varias partes de una oración al mismo tiempo, todas fácilmente accesibles para ser analizadas según sea necesario. Debido a que la memoria de trabajo humana tiene limitaciones, también las tiene la función de análisis de oraciones. [10] Esto se evidencia en varios tipos diferentes de oraciones sintácticamente complejas que plantean problemas potenciales para el análisis mental de las oraciones.
El primer tipo de oración, y quizás el más conocido, que desafía la capacidad de análisis es la oración del camino del jardín. Estas oraciones están diseñadas para que la interpretación más común de la oración parezca gramaticalmente defectuosa, pero tras una inspección más detallada, estas oraciones son gramaticalmente sólidas. Las oraciones del camino del jardín son difíciles de analizar porque contienen una frase o una palabra con más de un significado, siendo a menudo su significado más típico una parte diferente del discurso. [11] Por ejemplo, en la oración "el caballo corrió más allá del granero cayó", corrió se interpreta inicialmente como un verbo en tiempo pasado, pero en esta oración funciona como parte de una frase adjetiva. Dado que el análisis se utiliza para identificar partes del discurso, estas oraciones desafían la capacidad de análisis del lector.
Otro tipo de oración que es difícil de analizar es la ambigüedad de apego, que incluye una frase que potencialmente podría modificar diferentes partes de una oración y, por lo tanto, presenta un desafío a la hora de identificar la relación sintáctica (es decir, "El niño vio a la dama con el telescopio", en el que la frase ambigua con el telescopio podría modificar el niño vio o la señora.) [12]
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 (es decir, "La rata, el gato que el hombre persiguió, corrió hacia la trampa".) Oraciones con 2 o en el En los casos más extremos, las incrustaciones de 3 centros son un desafío para el análisis mental, nuevamente debido a la ambigüedad de la relación sintáctica. [13]
Dentro de la neurolingüística existen múltiples teorías que tienen como objetivo describir cómo se produce el análisis sintáctico en el cerebro. Uno de esos modelos es un 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 de oraciones, que es precedido por el acceso al reconocimiento y recuperación léxico, y luego seguido por un procesamiento sintáctico que considera una sola resultado sintáctico del análisis, volviendo solo 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 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 se integran estos procesos. [15]
Aunque todavía queda mucho por aprender sobre la neurología del análisis, los estudios han mostrado evidencia de que varias áreas del cerebro podrían desempeñar un papel en el análisis. Estos incluyen el polo temporal anterior izquierdo, la circunvolución frontal inferior izquierda, la circunvolución temporal superior izquierda, la circunvolución frontal superior izquierda, la corteza cingulada posterior derecha y la circunvolución angular izquierda. Aunque no se ha demostrado absolutamente, se ha sugerido que estas diferentes estructuras podrían favorecer el análisis de estructura de frase o el análisis de estructura de dependencia, lo que significa que diferentes tipos de análisis podrían procesarse de diferentes maneras que aún no se han entendido. [dieciséis]
El análisis del discurso examina formas de analizar el uso del lenguaje y los eventos semióticos. El lenguaje persuasivo puede denominarse retórica .
Un analizador es un componente de software que toma datos de entrada (frecuentemente texto) y construye una estructura de datos , a menudo algún tipo de árbol de análisis , árbol de sintaxis abstracta u otra estructura jerárquica, que proporciona una representación estructural de la entrada mientras verifica la sintaxis correcta. El análisis puede ir precedido o seguido de otros pasos, o estos pueden combinarse en un solo paso. El analizador suele ir precedido de un analizador léxico independiente , que crea tokens a partir de la secuencia de caracteres de entrada; alternativamente, estos se pueden combinar en un análisis sin escáner . Los analizadores pueden programarse manualmente o pueden generarse automática o semiautomáticamente mediante un generador de analizadores . El análisis es complementario a las plantillas , que producen resultados formateados. Estos pueden aplicarse a diferentes dominios, pero a menudo aparecen juntos, como el par scanf / printf , o las etapas de entrada (análisis frontal) y salida (generación de código back-end) de un compilador.
La entrada a un analizador suele ser texto en algún lenguaje informático , 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 van desde funciones muy simples como scanf , hasta programas complejos como la interfaz de un compilador de C++ o el analizador HTML de un navegador web . Una clase importante de análisis simple se realiza mediante 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 antes del análisis, como paso de lexing cuya salida luego utiliza el analizador.
El uso de analizadores varía según la entrada. En el caso de los lenguajes de datos, un analizador a menudo se encuentra como la función 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 para ellos se pueden escribir analizadores rápidos y eficientes. Para los compiladores, el análisis en sí se puede realizar 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 ha reconocido que el segmento actual del programa ha sido eliminado. terminado. Un ejemplo en el que un mecanismo de reparación de este tipo sería útil sería una declaración GOTO directa, donde el objetivo de GOTO se desconoce hasta que se completa el segmento del programa. En este caso, la aplicación del arreglo se retrasaría hasta que se reconociera el objetivo del GOTO. Por el contrario, un GOTO hacia atrás no requiere reparación, ya que la ubicación ya será conocida.
Las gramáticas libres de contexto están limitadas en la medida en que pueden expresar todos los requisitos de un idioma. Informalmente, la razón es que la memoria de dicho lenguaje es limitada. La gramática no puede recordar la presencia de una construcción en una entrada arbitrariamente larga; esto es necesario para un idioma 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 tanto, es una estrategia común crear un analizador relajado para una gramática libre de contexto que acepte un superconjunto de las construcciones del lenguaje deseadas (es decir, acepte algunas construcciones no válidas); Posteriormente, 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 );El siguiente código, sin embargo, es sintácticamente válido en términos de 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 analizar 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 miraría una entrada como " 12 * (3 + 4)^2" y la dividiría en 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 lexer contendría reglas para indicarle que los caracteres *, +, ^y (marcan )el inicio de un nuevo token, por lo que no se generarán tokens sin sentido como " 12*" o " ".(3
La siguiente etapa es el análisis sintáctico, que consiste en verificar que los tokens formen una expresión permitida. Esto generalmente se hace con referencia a una gramática libre de contexto que define recursivamente 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 pueden expresarse únicamente mediante gramáticas libres de contexto, por ejemplo, la validez de tipo 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 recién validada y tomar las medidas adecuadas. [17] En el caso de una calculadora o intérprete, la acción es evaluar la expresión o programa; un compilador, por otro lado, generaría algún tipo de código. También se pueden utilizar gramáticas de atributos para definir estas acciones.
La tarea del analizador es esencialmente determinar si la entrada puede derivarse del símbolo inicial de la gramática y cómo. Esto se puede hacer esencialmente de dos maneras:
Los analizadores LL y los analizadores de descenso recursivo son ejemplos de analizadores de arriba hacia abajo que no pueden adaptarse a las reglas de producción recursivas por la izquierda . Aunque se ha creído que las implementaciones simples de análisis de arriba hacia abajo no pueden acomodar la recursión izquierda directa e indirecta y pueden requerir una complejidad exponencial de tiempo y espacio mientras se analizan gramáticas ambiguas libres de contexto , Frost ha creado algoritmos más sofisticados para el análisis de arriba hacia abajo. , Hafiz y Callaghan [20] [21] que se adaptan a la ambigüedad y la recursividad por la izquierda en tiempo polinomial y que generan representaciones de tamaño polinomial del número potencialmente exponencial de árboles de análisis. Su algoritmo es capaz de producir derivaciones tanto hacia la izquierda como hacia la derecha de una entrada con respecto a una gramática libre de contexto determinada .
Una distinción importante con respecto a los analizadores es si un analizador 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 LL generarán una derivación más a la izquierda y los analizadores LR generarán una derivación más a la derecha (aunque normalmente a la inversa). [18]
AlgunoSe han diseñado algoritmos de análisis gráfico para lenguajes de programación visual. [22][23]Los analizadores de 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 "autoextendibles" . [25]
Las API de analizador más simples leen el archivo de entrada completo, realizan algunos cálculos intermedios y luego escriben el archivo de salida completo. (Como compiladores de múltiples pasadas en memoria ).
Esos analizadores simples no funcionarán cuando no haya suficiente memoria para almacenar todo el archivo de entrada o todo el archivo de salida. Tampoco funcionarán con flujos interminables de datos del mundo real.
Algunos enfoques API alternativos para analizar dichos datos:
Algunas de las herramientas de desarrollo de analizadores más conocidas incluyen las siguientes:
int v;main(){vLookahead establece el número máximo de tokens entrantes que un analizador puede usar para decidir qué regla debe usar. La anticipación es especialmente relevante para los analizadores LL , LR y LALR , donde a menudo se indica explícitamente colocando la anticipación 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, se definen cuidadosamente de tal manera que un analizador con anticipación limitada, generalmente uno, pueda analizarlos, porque los analizadores con anticipación limitada suelen ser más eficientes. Un cambio importante [ cita necesaria ] en esta tendencia se produjo en 1990 cuando Terence Parr creó ANTLR para su doctorado. tesis, un generador de analizadores para analizadores LL( k ) eficientes, donde k es cualquier valor fijo.
Los analizadores LR normalmente solo realizan unas pocas acciones después de ver cada token. Son desplazamiento (agregue este token a la pila para su posterior reducción), reducción (saque tokens de la pila y forme una construcción sintáctica), fin, error (no se aplica ninguna regla conocida) o conflicto (no sabe si cambiar o reducir). .
La anticipación tiene dos ventajas. [ se necesita aclaración ]
Ejemplo: análisis de la expresión 1 + 2 * 3 [ dudoso ]
La mayoría de los lenguajes de programación (excepto algunos como APL y Smalltalk) y 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.
Inicialmente entrada = [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 mirar hacia adelante, existen tres soluciones:
El árbol de análisis generado es correcto y simplemente más eficiente [ aclarar ] [ cita necesaria ] que los analizadores sin anticipación. Esta es la estrategia seguida en los analizadores LALR .
{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ) Mantenimiento CS1: nombres numéricos: lista de autores ( enlace )