| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV Introducción 4.1 Frases, formas sentenciales, Handles (Mangos), Prefijo Viable 4.2 Eliminación de Recursión inmediata y no inmediata 4.3 Factorización de Gramáticas

4.4 Analizador Top-Down

4.4.1 Análisis Sintáctico por Descenso Recursivo sin Retroceso y con Retroceso

4.4.2 Análisis Sintáctico LL(1)

4.4.2.1 Cálculo de First y Follow

4.4.2.2 Definición de Gramáticas LL(1) con reglas Épsilon

4.4.2.3 Algoritmo de análisis sintáctico LL(1)

4.5 Analizador Bottom-UP

4.5.1 Análisis Sintáctico por Precedencia de Operadores

4.5.1.1 Definición de Gramáticas de Operadores

4.5.1.2 Definición Formal de las Relaciones de Precedencia de Operadores

4.5.1.3 Funciones Firstop y Lastop

4.5.1.4 Obtención de la tabla de precedencia de Operadores

4.5.1.5 Algoritmo de análisis Sintáctico por Precedencia de Operadores

4.5.2 Análisis Sintáctico LR

4.5.2.1 Algoritmo de Análisis Sintáctico LR

4.5.2.2 Análisis Sintáctico LR(0)

4.5.2.2.1 Construcción de la Máquina LR(0)

4.5.2.2.2 Construcción de la Tabla LR(0)

4.5.2.2.3 Análisis Sintáctico SLR

4.5.2.2.4 Obtención de Estados SLR

4.5.2.2.5 Construcción de la Máquina de Estados SLR

4.5.2.2.6 Construcción de la Tabla SLR

4.5.2.2.7 Análisis Sintáctico LR(1)

4.5.2.2.8 Definición de elementos LR(1)

4.5.2.2.9 Construcción de conjuntos de elementos

4.5.2.2.10 Construcción de Máquina de estados LR(1)

4.5.2.2.11 Construcción de la Tabla LR(1)

UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

4.4.1 Análisis Sintáctico por Descenso Recursivo sin Retroceso y con Retroceso

> El objetivo fundamental del análisis sintáctico es "construir un árbol sintáctico" con la cadena de entrada (el "programa"), en la forma de unidades léxicas que determina el analizador léxico.

> Si esto se consigue, el programa es sintácticamente correcto; y es incorrecto en caso contrario. Se supone que el analizador sintáctico informará de cualquier error de sintaxis de manera inteligible. También deberá recuperarse de los errores que ocurren frecuentemente para poder continuar procesando el resto de su entrada.

> Existen tres tipos generales de analizadores sintácticos para gramáticas. Los métodos universales de análisis sintáctico, como el algoritmo de Cocke-Younger-Kasami y el de Earley, pueden analizar cualquier gramática. Estos métodos sin embargo, son demasiado ineficientes para usarlos en la producción de compiladores. Los métodos empleados generalmente en la producción de compiladores se clasifican como descendentes o ascendentes.

> Los dos tipos principales de análisis sintáctico son:

> Descendente: construye el árbol desde la raíz hacia las hojas.

> Ascendente: construye el árbol desde las hojas hacia la raíz.

> En ambos casos, se examina la entrada al analizador sintáctico de izquierda a derecha, un símbolo a la vez. Los métodos descendentes y ascendentes más eficientes trabajan sólo con subclases de gramáticas.

> La salida del analizador sintáctico es una representación del árbol de análisis sintáctico para la cadena de componentes léxicos producida por el analizador léxico. En la práctica, hay varias tareas que se pueden realizar durante el análisis sintáctico, como recoger información sobre distintos componentes léxicos en la tabla de símbolos, realizar la verificación de tipo y otras clases de análisis semántico. Para la implementación del analizador sintáctico debe de ser necesaria la redefinición de la gramática dada en la práctica de modo que sea ``entendible'' por la computadora. Dentro de la gramática generada se deberá eliminar la recursividad a izquierdas.

> Se sabe que los programas pueden contener errores de muy diversos tipos. Por ejemplo los errores pueden ser:

> Léxicos, como escribir mal un identificador, palabra clave u operador.
> Sintácticos, como una expresión aritmética con paréntesis no equilibrados.
> Semánticos, como un operador aplicado a un operando incompatible.

> Lógicos, como una llamada infinitamente recursiva.

> A menudo, gran parte de la detección y recuperación de errores en un compilador se centra en la fase de análisis sintáctico. Una razón es que muchos errores son de naturaleza sintáctica o se manifiestan cuando la cadena de componentes léxicos que proviene del analizador léxico desobedece las reglas gramaticales que definen el lenguaje de programación. Otra razón es la precisión de los métodos modernos de análisis sintáctico, que pueden detectar la presencia de errores dentro de los programas de una forma muy eficiente. La detección exacta de la presencia de errores semánticos y lógicos en el momento de la compilación es mucho más difícil.

> El manejador de errores en un analizador sintáctico tiene objetivos fáciles de establecer:

> - Debe de informar de la presencia de errores con claridad y exactitud.

> - Se debe de recuperar de cada error con la suficiente rapidez como para detectar errores posteriores.

> - De todos los niveles de análisis expuestos, la sintaxis ha sido durante mucho tiempo y aún sigue siendo el nivel al que la lingüística le ha prestado mayor atención. Está casi exclusiva atención se justifica por dos razones principales en cuanto al tratamiento automático del lenguaje natural (Rich & Knight 1994).

> 1. El procesamiento semántico funciona sobre los constituyentes de la oración. Si no existe un paso de análisis sintáctico, el sistema semántico debe identificar sus propios constituyentes. Por otro lado, si se realiza un análisis sintáctico, se restringe enormemente el número de constituyentes a considerar por el semántico, mucho más complejo y menos fiable. El análisis sintáctico es mucho menos costoso computacionalmente hablando que el análisis semántico (que requiere inferencias importantes). Por tanto, la existencia de un análisis sintáctico conlleva un considerable ahorro de recursos y una disminución de la complejidad del sistema.

> 2. Aunque frecuentemente se puede extraer el significado de una oración sin usar hechos gramaticales, no siempre es posible hacerlo.

> Por esto es evidente que la disponibilidad de un buen parser es determinante para conseguir buenos resultados en los niveles superiores de análisis. Aunque el objetivo del presente trabajo no es éste, nos detendremos a analizar el funcionamiento de los parsers típicos porque es importante para entender las necesidades de información que este tipo de aplicaciones requiere, así como los beneficios que tales aplicaciones pueden obtener de una correcta y exhaustiva estructuración de la información lingüística.

> La sintaxis contempla dos modos diferentes, pero no por ello opuestos, de análisis. El primero es el análisis de constituyentes o análisis de estructura de frase: la estructuración de las oraciones en sus partes constituyentes y la categorización de estas partes como nominales, verbales, adjetivales, etc. El segundo es el análisis de las relaciones o funciones gramaticales: la asignación de relacionales gramaticales tales como Sujeto, Objeto, etc.

> Desde el punto de vista del parser, una gramática es un conjunto de reglas que describen cómo los distintos constituyentes se pueden combinar. Las combinaciones permitidas por la gramática son consideradas gramaticales, mientras que el resto son agramaticales. Formalmente, una lengua es un conjunto de oraciones; cada oración es una cadena de uno o más símbolos pertenecientes al vocabulario de la lengua. Desde esta perspectiva, una gramática no es más que una especificación formal y finita de este conjunto de oraciones (Grishman 1986). Esta especificación puede ser llevada a cabo por enumeración si el conjunto de oraciones es finito. Si el conjunto de oraciones es infinito o el número de posibles oraciones es demasiado elevado, resulta imposible o poco económico describirlas por enumeración. La otra manera es idear un mecanismo, es decir una gramática, capaz de decidir, mediante la aplicación de un determinado número de reglas, si determinada oración es o no es gramatical.

> Tal tipo de gramática suele ser una gramática de estructura de frase o gramática sintagmática (PSG: Phrase Structure Grammar) (Hopcroft & Ullmann 1979). Las gramáticas de estructura de frase han sido y son ampliamente utilizadas en las aplicaciones de análisis del lenguaje natural, ya que se caracterizan por aportar una especificación formal de una lengua, lo cual las hace susceptibles de ser implementadas mediante algoritmos computacionales. Esta implementación, es decir, el conjunto de reglas, junto con el algoritmo que ha de desarrollarlas, es lo que se denomina parser. Una PSG tiene cuatro componentes (Grishman 1986:25):

> Un vocabulario terminal T: las palabras o símbolos de la lengua definida.

> Un vocabulario no-terminal N: (los símbolos que no pertenecen al anterior y que se utilizan para especificar la gramática. Se define V como la unión de estos dos vocabularios: V = (T U N).

> Un conjunto de reglas o producciones P, donde cada regla es de la forma: a b donde a es una secuencia de uno o más símbolos de V (es decir, a V+) y b es una secuencia de cero o más símbolos de V (a V*).

> El símbolo inicial S, miembro de N.

> La operación básica de una PSG es la de reescritura, es decir, la conversión de una secuencia de símbolos LHS (Left Hand Side) en otra diferente (RHS: Right Hand Side). Por ejemplo, si a b es una regla, esto significa que podemos reescribir cualquier símbolo que contenga la subcadena a, reemplazando a por b. Por ejemplo:
> nav nbv donde el símbolo " " denota esta operación de reescritura.

> Una lengua definida por una PSG es el conjunto de cadenas terminales (es decir, secuencias compuestas totalmente por símbolos terminales) que pueden derivarse del símbolo inicial S.

> La gran mayoría de las gramáticas formales para la descripción formal del lenguaje natural que se han propuesto hasta ahora están basadas en la gramática de estructura de frase, lo cual determina el hecho de que casi todos los parsers estén basados también en ella.

> Una sencilla PSG, para un subconjunto del inglés, podría quedar determinada por el siguiente conjunto de reglas:

> 1. O SN, SV
> 2. SN Npr | DET, N
> 3. SV V | V, SN
> 4. DET the | a
> 5. Npr John
> 6. N printer
> 7. V cleaned, printed

> Esta gramática, por ejemplo, puede ser directamente implementada en un sistema prolog, que contenga un intérprete standard DCG (Definite Clause Grammar) (Pereira & Warren 1980), y podría generar las siguientes oraciones bien formadas según nuestra gramática:

> John cleaned
> John cleaned the printer
> John cleaned the document
> John printed
> John printed the printer
> John printed the document
> ? the printer cleaned
> ? the printer cleaned John
> ? the printer cleaned the document
> the printer printed
> ? the printer printed John
> the printer printed the document
> ? the document cleaned
> ? the document cleaned John
> ? the document cleaned the printer
> ? the document printed
> ? the document printed John
> ? the document printed the printer

> Esta pequeña gramática es una gramática independiente del contexto, porque satisface la condición

> A x

> Donde A es un símbolo no-terminal y x es una secuencia de cero o más símbolos terminales y no-terminales. La principal característica de este tipo de gramáticas (CF-PSG: Context-Free Phrase Structure Grammar) es que emplea un conjunto finito de reglas para especificar la forma en que las categorías LHS se pueden reescribir en la RHS. Cuando una regla determinada especifica una realización determinada, esta realización es siempre posible, independientemente del contexto en la que la categoría LHS aparece, de ahí el nombre.

> El problema con este tipo de gramáticas es que, como podemos comprobar en el ejemplo, tienden a generar más oraciones de las necesarias. Si una gramática puede generar un determinado número de oraciones, significa que el parser también puede reconocerlas como gramaticales para esa gramática.

> Como ya hemos mencionado, para poder analizar una frase es necesario encontrar una manera de generar a partir del símbolo inicial S. Básicamente, esto puede hacerse de dos formas diferentes (Grishman 1986; Rich & Knight 1991):

> Análisis descendente: se comienza por el S y se aplican las reglas de la gramática hacia abajo hasta que los símbolos terminales del árbol se correspondan con los componentes de la frase analizada (nodos terminales).
> Análisis ascendente: se comienza con la frase a analizar y se aplican las reglas de la gramática hacia arriba hasta producir un único árbol cuyos nodos terminales sean las palabras de la oración y cuyo nodo raíz sea el símbolo inicial.
> La consideración esencial para la elección de uno de estos dos métodos es la de ramificación, normalmente se usará el método que permita una menor ramificación a partir de los nodos. Además, estos dos enfoques pueden combinarse, y de hecho es usual, en un solo parser. Este método se denomina "análisis ascendente con filtraje descendente" (Rich & Knight 1991) o también "análisis descendente con retrotrazado"; en él el análisis sintáctico discurre esencialmente de forma descendente, pero el parser tiene la facultad de eliminar inmediatamente los constituyentes que nunca podrán combinarse en estructuras de alto nivel sin más que hacer uso de unas tablas que han sido precalculadas para una gramática concreta mediante un sistema de reglas heurísticas.

> Este algoritmo opera sobre una derivación de la forma
> O z1 O z2 O ... O zn
> Inicialmente la derivación contiene únicamente el símbolo inicial O. Asumimos que las reglas que tienen una A a la izquierda están Ordenadas: RA,1, RA,2..., RA,n.
> Sea B el símbolo no-terminal más a la izquierda en Zn; expándase B utilizándose RB,1 (añadiendo un elemento a la derivación: n = n+1).

> Sea i la posición del símbolo no-terminal más a la izquierda en Zn (i = [longitud de Zn] + 1 si Zn no tiene elementos no-terminales). Si los primeros i-1 símbolos terminales de Zn corresponden a las primeras palabras de i-1 de la oración, váyase a (3); si no, váyase a (5).

> Si Zn contiene algún elemento no-terminal, pásese a (1).

> Si Zn coincide con la oración que se analiza, anótese la derivación presente como una derivación de la oración.
> Sea RB,i la última regla aplicada en la derivación; si existe una regla RB,i+1 reemplácese el último paso de la derivación (n = n - 1); si no quedan reglas (es decir, la derivación contiene sólo el símbolo inicial), abandónese, si no váyase a (5).
> Éste se puede considerar como el algoritmo de parsing por antonomasia y se encuentra presente con más o menos variaciones en el corazón de muchos sistemas de NLP. Por supuesto no es el único; se han elaborado parsers dependientes del contexto, parsers transformacionales, parsers basados en las redes de transición aumentadas (ATN: Augmented Transition Networks), e incluso algunos parsers (poco afortunados) para gramáticas dependientes del contexto. Además diversas teorías lingüísticas (incluyendo el modelo generativo-transformacional) han tratado de probar sus hipótesis, entre otros medios, creando parsers basados en sus directrices fundamentales, aunque es bien sabido (p. ej. Gazdar & Mellish 1989) que tales modelos no suelen dar resultados prácticos, ya que su objetivo fundamental no es crear un sistema para ser usado, sino simplemente corroborar determinadas hipótesis.

> Las necesidades de enriquecer el lexicón con información de índole semántica quedan patentes incluso en esta pequeña gramática que hemos mostrado. Resulta obvio que la información aportada por nuestra gramática (categorías gramaticales y reglas de reescritura) debe ser complementada por información de otros tipos, especialmente semántica, pero también morfológica, fraseológica, pragmática, etc. La inclusión de información léxico-semántica básica, por ejemplo, bloquearía las dudosas oraciones que hemos marcado con "?", en los que a una entidad que típicamente no puede asumir el papel de Agente (la impresora) muestra propiedades agentivas.

> Un parser del tipo descrito anteriormente podría generar un análisis de estructura de frase, normalmente con una representación mediante corchetes, aunque algunos existen programas que pueden convertir ésta en una representación gráfica en forma de árbol, como la siguiente:

> Esencialmente, nuestro punto de vista es que para obtener un análisis lingüístico válido para la TA, se necesita un gran nivel de interacción entre los tradicionalmente separados módulos de análisis sintáctico y semántico.

> Desde esta perspectiva, la función de un análisis de constituyentes se reduciría a generar la estructura base sobre la que podemos hacer funcionar otros módulos del sistema, aunque por supuesto, como hemos apuntado, en muchas ocasiones el analizador deberá recurrir a otros módulos para poder generar la estructura correcta. Lo más usual, sin embargo, es quedarse en el simple análisis de constituyentes.
> Creemos que este modo de actuar obedece a la creencia que durante muchos años imperó en los estudios lingüísticos y de IA de que es posible acometer el análisis lingüístico de una forma modular y aislada según los distintos niveles de análisis.
> Como hemos mencionado, durante mucho tiempo todo análisis lingüístico quedó reducido prácticamente a señalar los distintos constituyentes de la oración. Este análisis de constituyentes, sin dejar de ser válido, se debería complementar con un análisis funcional en donde se señalen de forma explícita las funciones o características relacionales de los distintos constituyentes, y que además permita la inserción de otros tipos de información.

> La utilidad de este tipo de análisis en la traducción automática es obvia: en algunos idiomas, como el inglés, el orden normal de una oración es sujeto - verbo - objeto, mientras que en otros es diferente. Por ejemplo en japonés el orden normal es sujeto - objeto - verbo. En otros, como el ruso, el orden de los constituyentes que exhiben estas funciones puede ser cualquiera. También se ha de realizar una distinción entre aquellas frases que cumplen las funciones de sujeto, objeto, etc., de aquéllas que sirven como Adjuntos, Modificadores, etc., ya que mientras los primeros suelen ser obligatorios, los segundos no.

> La representación de un análisis funcional no es esencialmente diferente de la representación de un análisis de constituyentes. Gráficamente, en lugar de mostrar un árbol donde los nodos son etiquetas que hacen referencia a las distintas categorías, el análisis funcional suele hacerse de forma lineal. Un análisis funcional básico de la oración de ejemplo anterior sería el siguiente:

> Existen algunas diferencias entre estos dos métodos de análisis. En primer lugar los nodos son las relaciones funcionales propiamente y se ha añadido una nueva categoría (head), que es el elemento central en ese sintagma, gramaticalmente hablando: el nombre en un sintagma nominal, el verbo en un sintagma verbal, la preposición en un sintagma preposicional. También se ha perdido el nodo vp (ya que éste no desempeña ninguna función gramatical), consistiendo la representación de las relaciones gramaticales de esta oración en un verbo y dos sintagmas nominales. Además el orden de los distintos elementos es irrelevante puesto que las relaciones gramaticales contienen de forma implícita información sobre el orden de las palabras. Podríamos mostrar los elementos del análisis anterior en cualquier otro orden y la oración resultante seguiría siendo la misma, lo cual no es posible en una estructura arbórea (por tanto, jerárquica) de un análisis de constituyentes.

> La diferencia fundamental es sin duda la inclusión de rasgos en forma de pares atributos: valores. La notación gramatical estructuras de rasgos y los formalismos gramaticales modernos combinan reglas de CF-PSG con un sistema de rasgos. Se dice que esta característica permite extender el análisis sintáctico con rasgos semánticos de una forma mucho más natural que si lo hiciéramos con una estructura jerárquica, sobre todo en lo que respecta a la asignación de papeles temáticos, el primer paso para un análisis semántico más profundo.

> De este modo, nuestro análisis de ejemplo podría ser fácilmente mejorado con el añadido de los papeles temáticos, o funciones semánticas, que los distintos elementos relacionales tienen:

> En el presente trabajo abogamos por un análisis de este tipo, que podrá ser sucesivamente enriquecido. Obviamente, la información necesaria que un sistema ha de tener para llevar a cabo tal análisis va más allá de las simples partes de la oración. Éste es precisamente el tema principal de este trabajo: mostrar qué tipo de información es necesaria y cómo esta información ha de estar representada para obtener la máxima funcionalidad y economía de representación, al mismo tiempo que se aboga por una independencia de los datos que garantice su reutilización. La representación, por tanto, deberá ser todo lo independiente que pueda ser con respecto a la teoría lingüística que se encargue del análisis, así como mantener la capacidad de adaptarse a sistemas y entornos computacionales para los que no fue desarrollada en principio.

> Por supuesto, el análisis no debe quedarse en las funciones semánticas básicas, en realidad, debería extenderse hasta el conocimiento pragmático y conocimiento del mundo o conocimiento de sentido común.

> Se examinan interactivamente basándose sobre sublistas producidas por el sistema:

> a) El rol de la conjunción y de la coma:
> Separan a veces muchas unidades (normalmente adjetivos pero también sustantivos) referidas a un sólo componente identificador que las precede o las sigue; a dicho componente serán asignados por lo tanto las distintas unidades y de esta manera se generan más KPH a partir de aquel componente identificador;

> b) El rol de la preposición de especificación:
> En la primera fase no se ha considerado un separador atendibile, puesto que une dos componentes del párrafo que, en la mayoría de los casos, son indivisibles entre sí; en esta fase se subdividen con la ayuda del correspondiente léxico las KPH que contienen dichas preposiciones y se analizan en forma separada las partes obtenidas; no se acepta la subdivisión cuando en efecto la KPH completa presenta valencia semántica;

> c) KPH constituidas por componentes nominales:
> si una componente identifica una clase muy amplia y la otra, aplicada a la anterior, limita su connotación y la vuelve más específica, se mantiene la forma compuesta por ser científicamente más significativa;

> d) KPH constituidas por sintagmas adjetivales:
> Es necesario tener en cuenta que, como regla general, los adjetivos no constituyen KPH autónomas. Se pueden aplicar diferentes criterios:

> 1) Las KPH de uso común en el lenguaje científico corriente se dejan en su forma;

> 2) Las KPH en las cuales el componente identificador es adjetival, mientras el componente nominal tiene un significado muy amplio, se pueden transformar en un sustantivo que pertenezca al mismo campo semántico del adjetivo;

> 3) Las KPH en las cuales tanto el componente adjetival como aquella nominal tienen un propio significado se sustituyen con dichos componentes; el adjetivo se transforma en el sustantivo correspondiente y ambos elementos se incorporan a las KPHs.
> Asimismo, los problemas que se detallan a continuación están relacionados con el carácter de específico del conjunto que se quiere representar, o con consideraciones científicas verificables para confrontar textos de reconocida validez; éstos por ende tienen valencia exclusivamente semántica y la solución en gran medida está determinada por el experto, por lo cual aquellas que siguen son únicamente sugerencias relacionadas a experiencias anteriores.

> 4) Se efectúa un examen semántico interactivo, sobre las frases hasta ahora obtenidas, basado en sublistas propuestas por el sistema:

> a) KPH de significado ambiguo: se cotejan con el contexto de procedencia.

> b) KPH relacionadas exclusivamente a la contingencia: (como por ej. fechas, nombres propios de persona, sustantivos de significado muy genérico, etc.) son eliminadas;

> c) KPH complejas: se efectúa opera una rectificación o "afinamiento" tanto eliminando aquellas partes que la hacen demasiado específica y/o que no influyen sobre el significado de la KPH como subdividiendo, donde sea necesario y posible, la KPH en sus componentes; en algunos casos se puede dejar tanto la KPH en su forma compuesta o subdividirla en sus componentes.

> Como regla general las KPHs deben representar conceptos individuales o unitarios y las KPHs compuestas deben ser subdivididas en elementos más simples excepto cuando ello comprometa el significado de las KPHs mismas.
> Al finalizar esta fase, se obtiene una lista constituida por frases de significado científico, relativas al campo en examen y afinadas al grado de especificación considerado aceptable.

> Se puede considerar que a esta altura de la elaboración, los términos corrientes de la literatura en el campo examinado forman parte de la lista obtenida, pero que no está formada sólo por ellos. Forman parte un número considerable de frases que no pueden ser considerados "términos", por lo menos actualmente, pero que pueden estar de muchas maneras vinculadas a los términos con relaciones de jerarquía semántica que comprenden dependencia, ascendencia y sinonimia.

Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello