stringtranslate.com

Analizando

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.

Lenguajes humanos

Métodos tradicionales

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 que era 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 ]

Métodos computacionales

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]

Psicolingüística

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]

Análisis del discurso

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 .

Lenguajes informáticos

Analizador sintáctico

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 )

Descripción general del proceso

Flujo de datos en un analizador típico

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.

Tipos de analizadores sintácticos

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:

Análisis de arriba hacia abajo
El análisis de arriba hacia abajo puede considerarse como un intento de encontrar derivaciones más a la izquierda de un flujo de entrada mediante la búsqueda de árboles de análisis utilizando una expansión de arriba hacia abajo de las reglas gramaticales formales dadas . Los tokens se consumen de izquierda a derecha. La elección inclusiva se utiliza para dar cabida a la ambigüedad mediante la expansión de todos los lados derechos alternativos de las reglas gramaticales. [18] Esto se conoce como el enfoque de la sopa primordial. Muy similar a la diagramación de oraciones, la sopa primordial descompone los constituyentes de las oraciones. [19]
Análisis de abajo hacia arriba
Un analizador puede comenzar con la entrada e intentar reescribirla hasta el símbolo de inicio. Intuitivamente, el analizador intenta localizar los elementos más básicos, luego los elementos que los contienen, y así sucesivamente. Los analizadores LR son ejemplos de analizadores ascendentes. Otro término utilizado para este tipo de analizador es análisis Shift-Reduce .

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]

Implementación

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:

Software de desarrollo de analizadores sintácticos

Algunas de las herramientas de desarrollo de analizadores más conocidas incluyen las siguientes:

Mirar hacia adelante

Programa en C que no se puede analizar con menos de 2 tokens de anticipación. Arriba: extracto de gramática de C. [28] Abajo: un analizador ha digerido los tokens " " y está a punto de elegir una regla para derivar Stmt . Al observar solo el primer token de anticipación " ", no puede decidir cuál de las dos alternativas elegir para Stmt ; la última requiere echar un vistazo al segundo token.int v;main(){v

El 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 [ dudosodiscutir ]

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.

Acciones simples del analizador sin anticipación

Entrada inicial = [1, +, 2, *, 3]

  1. Desplazar "1" a la pila desde la entrada (anticipándose a la regla 3). Entrada = [+, 2, *, 3] Pila = [1]
  2. Reduce "1" a la expresión "E" según la regla 3. Pila = [E]
  3. Desplazar "+" desde la entrada a la pila (anticipándose a la regla 1). Entrada = [2, *, 3] Pila = [E, +]
  4. Desplazar "2" desde la entrada a la pila (anticipándose a la regla 3). Entrada = [*, 3] Pila = [E, +, 2]
  5. Reducir el elemento de pila "2" a la expresión "E" según la regla 3. Pila = [E, +, E]
  6. Reducir los elementos de la pila [E, +, E] y la nueva entrada "E" a "E" según la regla 1. Pila = [E]
  7. Desplazar "*" desde la entrada a la pila (anticipándose a la regla 2). Entrada = [3] Pila = [E,*]
  8. Desplazar "3" a la pila desde la entrada (anticipándose a la regla 3). Entrada = [] (vacía) Pila = [E, *, 3]
  9. Reducir el elemento de pila "3" a la expresión "E" según la regla 3. Pila = [E, *, E]
  10. Reducir los elementos de la pila [E, *, E] y la nueva entrada "E" a "E" según la regla 2. Pila = [E]

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:

Acciones del analizador de búsqueda anticipada [ aclaración necesaria ]
  1. Desplazar 1 a la pila en la entrada 1 en anticipación de la regla 3. No se reduce inmediatamente.
  2. Reducir el elemento 1 de la pila a una expresión simple en la entrada + según la regla 3. La búsqueda anticipada es +, por lo que estamos en la ruta hacia E +, por lo que podemos reducir la pila a E.
  3. Shift + en la pila en la entrada + en anticipación de la regla 1.
  4. Desplazar 2 a la pila en la entrada 2 en anticipación de la regla 3.
  5. Reduce el elemento 2 de la pila a Expresión en la entrada * según la regla 3. La búsqueda anticipada * solo espera E antes de ella.
  6. Ahora, la pila tiene E + E y la entrada sigue siendo *. Ahora tiene dos opciones: desplazarse según la regla 2 o reducirse según la regla 1. Como * tiene mayor precedencia que + según la regla 4, desplazamos * a la pila en previsión de la regla 2.
  7. Desplazar 3 a la pila en la entrada 3 en anticipación de la regla 3.
  8. Reduce el elemento 3 de la pila a Expresión después de ver el final de la entrada según la regla 3.
  9. Reduce los elementos de la pila E * E a E según la regla 2.
  10. Reduce los elementos de la pila E + E a E según la regla 1.

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 .

Lista de algoritmos de análisis

Véase también

Referencias

  1. ^ ab "Parse". dictionary.reference.com . Consultado el 27 de noviembre de 2010 .
  2. ^ Masaru Tomita (6 de diciembre de 2012). Análisis LR generalizado. Springer Science & Business Media. ISBN 978-1-4615-4034-2.
  3. ^ "Gramática y composición". Archivado desde el original el 1 de diciembre de 2016. Consultado el 24 de noviembre de 2012 .
  4. ^ Christopher D. Manning; Christopher D. Manning; Hinrich Schütze (1999). Fundamentos del procesamiento estadístico del lenguaje natural. Prensa del MIT. ISBN 978-0-262-13360-9.
  5. ^ Jurafsky, Daniel (1996). "Un modelo probabilístico de acceso y desambiguación léxica y sintáctica". Cognitive Science . 20 (2): 137–194. CiteSeerX 10.1.1.150.5711 . doi :10.1207/s15516709cog2002_1. 
  6. ^ Klein, Dan y Christopher D. Manning. "Análisis sintáctico preciso y sin lexicalización". Actas de la 41.ª reunión anual de la Asociación de Lingüística Computacional, volumen 1. Asociación de Lingüística Computacional, 2003.
  7. ^ Charniak, Eugene. "Un analizador sintáctico inspirado en la máxima entropía Archivado el 1 de abril de 2019 en Wayback Machine ." Actas de la 1.ª conferencia del capítulo norteamericano de la Asociación de Lingüística Computacional. Asociación de Lingüística Computacional, 2000.
  8. ^ Chen, Danqi y Christopher Manning. "Un analizador de dependencias rápido y preciso que utiliza redes neuronales". Actas de la conferencia de 2014 sobre métodos empíricos en el procesamiento del lenguaje natural (EMNLP). 2014.
  9. ^ Jia, Robin; Liang, Percy (11 de junio de 2016). "Recombinación de datos para análisis semántico neuronal". arXiv : 1606.03622 [cs.CL].
  10. ^ Sandra H. Vos, Thomas C. Gunter, Herbert Schriefers y Angela D. Friederici (2001) Análisis sintáctico y memoria de trabajo: los efectos de la complejidad sintáctica, la amplitud de lectura y la carga concurrente, Language and Cognitive Processes, 16:1, 65-103, DOI: 10.1080/01690960042000085
  11. ^ ab Pritchett, BL (1988). Fenómenos de Garden Path y la base gramatical del procesamiento del lenguaje. Language, 64(3), 539–576. https://doi.org/10.2307/414532
  12. ^ Thomas G Bever (1970). La base cognitiva de las estructuras lingüísticas . OCLC  43300456.
  13. ^ Karlsson, F. (2010). Restricciones de la memoria de trabajo en la incrustación de múltiples centros. Actas de la Reunión Anual de la Sociedad de Ciencias Cognitivas, 32. Recuperado de https://escholarship.org/uc/item/4j00v1j2
  14. ^ Ferreira, F., y Clifton, C. (1986). La independencia del procesamiento sintáctico. Journal of Memory and Language, 25(3), 348–368. https://doi.org/10.1016/0749-596X(86)90006-9
  15. ^ Atlas, JD (1997). Sobre la modularidad del procesamiento de oraciones: generalidad semántica y el lenguaje del pensamiento. Lenguaje y conceptualización, 213-214.
  16. ^ Lopopolo, Alessandro, van den Bosch, Antal, Petersson, Karl-Magnus y Roel M. Willems; Distinguir las operaciones sintácticas en el cerebro: dependencia y análisis sintáctico de la estructura de la frase. Neurobiología del lenguaje 2021; 2 (1): 152–175. doi: https://doi.org/10.1162/nol_a_00029
  17. ^ Berant, Jonathan y Percy Liang. "Análisis semántico mediante paráfrasis". Actas de la 52.ª reunión anual de la Asociación de Lingüística Computacional (volumen 1: artículos extensos). 2014.
  18. ^ ab Aho, AV, Sethi, R. y Ullman, JD (1986) "Compiladores: principios, técnicas y herramientas". Addison-Wesley Longman Publishing Co., Inc. Boston, MA, EE. UU.
  19. ^ Sikkel, Klaas, 1954- (1997). Esquemas de análisis sintáctico: un marco para la especificación y el análisis de algoritmos de análisis sintáctico . Berlín: Springer. ISBN 9783642605413.OCLC 606012644  .{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
  20. ^ Frost, R., Hafiz, R. y Callaghan, P. (2007) " Análisis descendente modular y eficiente para gramáticas recursivas por la izquierda ambiguas Archivado el 22 de agosto de 2018 en Wayback Machine ". 10.º Taller internacional sobre tecnologías de análisis (IWPT), ACL-SIGPARSE , páginas: 109-120, junio de 2007, Praga.
  21. ^ Frost, R., Hafiz, R. y Callaghan, P. (2008) "Combinadores de analizadores sintácticos para gramáticas recursivas por la izquierda ambiguas". 10º Simposio Internacional sobre Aspectos Prácticos de los Lenguajes Declarativos (PADL), ACM-SIGPLAN , Volumen 4902/2008, Páginas: 167 - 181, enero de 2008, San Francisco.
  22. ^ Rekers, Jan y Andy Schürr. "Definición y análisis de lenguajes visuales con gramáticas de gráficos en capas". Journal of Visual Languages ​​& Computing 8.1 (1997): 27-55.
  23. ^ Rekers, Jan y A. Schurr. "Un enfoque de gramática gráfica para el análisis gráfico". Visual Languages, Actas, 11.º Simposio Internacional IEEE sobre. IEEE, 1995.
  24. ^ Zhang, Da-Qian, Kang Zhang y Jiannong Cao. "Un formalismo gramatical de grafos sensible al contexto para la especificación de lenguajes visuales". The Computer Journal 44.3 (2001): 186-200.
  25. ^ Jill Fain Lehman (6 de diciembre de 2012). Análisis adaptativo: interfaces de lenguaje natural autoextensibles. Springer Science & Business Media. ISBN 978-1-4615-3622-2.
  26. ^ Patrick Blackburn y Kristina Striegnitz. "Técnicas de procesamiento del lenguaje natural en Prolog".
  27. ^ Song-Chun Zhu. "Algoritmos de análisis clásicos".
  28. ^ extraído de Brian W. Kernighan y Dennis M. Ritchie (abril de 1988). El lenguaje de programación C. Serie de software de Prentice Hall (2.ª edición). Englewood Cliffs/NJ: Prentice Hall. ISBN 0131103628.(Apéndice A.13 “Gramática”, pág. 193 y siguientes)

Lectura adicional

Enlaces externos