• Author / Uploaded
• Andres Elias Ruiz Rodriguez

Citation preview

Universidad Nacional Experimental de Guayana Vice-Rectorado Académico Proyecto de Carrera: Ingeniería en Informática Lenguajes y Compiladores 2016-I Sección “2”

Analizador Sintáctico

PROFESOR: INTEGRANTES: Félix Márquez.

Capella

Genghis V-19800720 Castro Jhon V-18579925 Fernández Carlos V-20219273 Morales Néstor V-19995576

Ciudad Guayana, julio 2016.

Actividad del tema. 1. Presentar un informe de investigación teórico-práctico en el cual explique el método de cada tipo de parser, es necesario que indique la fuente donde se obtienen los conceptos que presentará en dicho informe y presente al menos dos ejemplos 2 de parser realizado a la gramática seleccionada en el tema 3 tanto para análisis ascendentes como descendentes para una secuencia de componentes léxicos elegidos por Usted. En otras palabras, se mencionaron 5 métodos, el grupo debe presentar 2 ejemplos de parser por cada método.

Qué es el analizador sintáctico Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce. En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico. En la práctica, el analizador sintáctico también hace: 

Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador

  

semántico). Chequeo de tipos (del analizador semántico). Generar código intermedio. Generar errores cuando se producen. En definitiva, realiza casi todas las operaciones de la compilación. Este método

de trabajo da lugar a los métodos de compilación dirigidos por sintaxis.

Tipo de gramática que acepta un analizador sintáctico

Centrándonos en el análisis sintáctico para lenguajes basados en gramáticas formales, es la mejor forma para comprensión del compilador ya que de otra forma se no aria difícil, y se pueden corregir, quizás más fácilmente, errores de muy difícil localización, como es la ambigüedad en el reconocimiento de ciertas sentencias.

La gramática que acepta el analizador sintáctico es una gramática de contexto libre:



Gramática: G (N, T, P, S) N = No terminales. T = Terminales. P = Reglas de Producción. S = Axioma Inicial.

Tipos de Análisis De la forma de construir el árbol sintáctico se desprenden dos tipos o clases de analizadores sintácticos. Pueden ser descendentes o ascendente 

Descendentes: Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia.

Pueden ser: Con retroceso. Con recursión. LL(1) 

Ascendentes: Parten de la sentencia de entrada, y van aplicando reglas de producción hacia atrás (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial.

Pueden ser: Con retroceso. LR(1) Análisis descendente con retroceso. 

Objetivo: El método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda.

Ejemplo: Utilizaremos la siguiente gramática (No recursiva por la izquierda)

Para reconocer la cadena de entrada: (a + b) * a + b

Mediante este árbol se pueden derivar todas las posibles sentencias reconocibles por esta gramática y el objetivo de este algoritmo es hacer una búsqueda en este árbol de la rama que culmine en la sentencia a reconocer. El mecanismo funciona mediante una

búsqueda primero en profundidad. Mira si todos los tokens a la izquierda de un No Terminal coinciden con la cabeza de la secuencia a reconocer. En todo el árbol de derivaciones, se pretende profundizar por cada rama hasta llegar a encontrar una forma sentencial que no puede coincidir con lo que se busca, en cuyo caso se desecha, o que coincide con lo buscado, momento en que se acepta la sentencia. Si por ninguna rama se puede reconocer, se rechaza la sentencia. NOTA: Este método no funciona con gramáticas recursivas a la izquierda, ya que puede ocurrir que entre en un bucle infinito. No existen muchos analizadores sintácticos con retroceso. En parte, porque casi nunca se necesita el retroceso para analizar sintácticamente las construcciones de los lenguajes de programación. En casos como el análisis sintáctico del lenguaje natural, el retroceso tampoco es muy eficiente, y se prefieren otros métodos. Reconocer con el algoritmo (a+b)*a+b

Análisis descendente con recursión. Diagramas de Conway Una gramática de contexto libre puede expresar un lenguaje al igual que puede hacerlo la notación BNF, y los diagramas de Conway. 

Definición: Un diagrama de Conway es un grafo dirigido donde los elementos no terminales aparecen como rectángulos, y los terminales como círculos.

Para demostrar que permite representar las mismas gramáticas que la BNF, se hace por inducción sobre las operaciones básicas de BNF:

De esta forma todos los posibles caminos desde el inicio del grafo hasta el final, representan formas sentenciales válidas. En todo diagrama de Conway hay un origen y un destino.

Ejemplo: Yuxtaposición

Ejemplo:

Consideremos la siguiente gramática: S : 'c' A 'd' A : 'a' 'b' A : 'a Cadena de entrada: w=cad

Análisis descendente de gramáticas LL(1) Una gramática LL(1) es aquella en la que su tabla de chequeo de sintaxis no posee entradas múltiples, o sea, es suficiente con examinar sólo un símbolo a la entrada, para saber qué regla aplicar. Toda gramática reconocible mediante el método de los diagramas de Conway es LL(1) El método consiste en seguir un algoritmo partiendo de: 

La cadena a reconocer, junto con un apuntador, que nos indica cual es el token

 

actual. Una pila de símbolos (terminales y no terminales) Una tabla asociada de forma unívoca a una gramática.

En este ejemplo no vamos a ver como calcular dicha tabla. La cadena de entrada acabará en el símbolo $, que consideramos como si fuese un EOF (End Of File - Fin de Fichero). Sea X el elemento encima de la pila, y a, el apuntado en la entrada. El algoritmo consiste en: 1.- Si X = a = $ entonces ACEPTAR. 2.- Si X = a g $ entonces - se quita X de la pila - y se avanza el apuntador. 3.- Si X € T y X g a entonces RECHAZAR. 4.- Si X € N entonces consultamos la entrada M[X,a] de la tabla: - M[X,a] es vacia: RECHAZAR. - M [X,a] no es vacia, se quita a X de la pila y se inserta el consecuente en orden inverso - M [X,a] no es vacia, se quita a X de la pila y se inserta el consecuente en orden inverso. Ejemplo: Si M[X,a] = {X € UVY}, se quita a X de la pila, y se meten UVY en orden

inverso

5.- Ir al paso 1. Una vez aplicada una regla, no será desaplicada por ningún tipo de retroceso. El algoritmo comienza con $ y con el axioma inicial metidos en la pila. Ejemplo:

Ejemplo:

Análisis Ascendente con retroceso.

Cuando se da cuenta que llega a una situación en la que no puede continuar, entonces vuelve atrás deshaciendo todos los cambios. En el análisis con retroceso no se permiten las reglas ɛ, puesto que estas se podrán aplicar de forma indefinida. Este método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda. 

Se usa el retroceso para resolver la incertidumbre.



Sencillo de implementar.



Muy eficiente.

Ejemplo:

Ejemplo: (Vamos a ver por qué no se permiten las reglas ɛ). Supongamos la siguiente gramática.

No puede aparecer ɛ en una gramática ascendente con retroceso porque da lugar a recursión infinita. Ejemplo: Reconocer a*a = id * id, dada la siguiente gramática:

(Llevaremos una pila para el Backtraking)

Analizadores LR Análisis sintáctico LR(k); la “L” es por el examen de la entrada de izquierda a derecha (en inglés, left-to-right), la “R” por construir una derivación por la derecha (en inglés, rightmost derivation) en orden inverso, y la k por el número de símbolos de entrada de examen por anticipado utilizados para tomar las decisiones del análisis sintáctico. Cuando se omite, se asume que k, es 1. El análisis LR es atractivo por varias razones. Pueden reconocer la inmensa mayoría de los lenguajes de programación que puedan ser generados mediante gramáticas de contexto-libre. El método de funcionamiento de estos analizadores posee la ventaja de localizar un error sintáctico en el mismo instante que se produce con lo que se adquiere una gran eficiencia de tiempo de compilación frente a procedimientos menos adecuados como puedan ser los de retroceso.

El principal inconveniente del método es que supone demasiado trabajo construir un analizador sintáctico LR a mano para una gramática de un lenguaje de programación típico. Se necesita una herramienta especializada, un generador de analizadores sintácticos LR para ello. Existen tres técnicas para construir una tabla de análisis sintáctico LR para una gramática. 

El primer método, llamado LR sencillo (SLR, en inglés) es el más fácil de implantar, pero el menos poderoso de los tres. Puede que no consiga producir una tabla de análisis sintáctico para algunas gramáticas que otros

 

métodos si consiguen. El segundo método, llamado LR canónico, es el más poderoso y costoso. El tercer método, llamado LR con examen por anticipado (LALR, en inglés), está entre los otros dos en cuanto a poder y costo. El método LALR funciona con las gramáticas de la mayoría de los lenguajes de programación y, con un poco de esfuerzo, se puede implantar en forma eficiente.

Funcionalmente hablando, un analizador LR consta de dos partes diferenciadas, un programa de proceso y una tabla del análisis. El funcionamiento del analizador LR es el siguiente 1.- Se determina el estado sm en cabeza de la pila y el símbolo actual ai en el instante de la cadena de entrada. 2.- Se consulta en la tabla de análisis la función acción con los parámetros anteriores y que puede dar como resultado.

por su parte la función GOTO actúa igualmente con un estado y un símbolo de la gramática produciendo un nuevo estado.

Ejemplo: Expresiones aritméticas y tablas LR Sea la gramática ya conocida de generación de expresiones aritméticas.

La figura siguiente muestra la tabla de análisis con las funciones ACCIÓN y GOTO para la gramática anterior.

El significado de las entradas de la tabla anterior es la siguiente: 1. 2. 3. 4.

Di significa desplazar y meter en la pila el estado i, Rj significa reducir por la regla de producción con número j, ACEP significa aceptar. las entradas en blanco significan un error sintáctico.

Ejemplo de reconocimiento para la cadena de entrada

a * ( a + a) = id * (id + id) (Suponemos que el estado s0 queda representado por 0).

Se ha considerado reducir la cadena de entrada al símbolo inicial S, por lo tanto, la sentencia pertenece al lenguaje generado por la gramática dada. A la hora de hacer una reducción hay que tener cuidado al elegir las reglas a usar. Si en el paso 6 del ejemplo del ejemplo anterior se fuese reducido usando la regla 3 en lugar de la 2 nos habría quedado en la pila.

Y no se podría seguir a partir de aquí porque en la gramática no existe ninguna regla a esa combinación de símbolos. Para que no se presente este problema, cada vez que vaya a hacer una reducción, el analizador sintáctico ascendente tiene que saber reconocer las reglas de producción, que no bloqueen el análisis y produzcan el retroceso (backtracking). La gramática LR posee la propiedad de realizar el análisis ascendente sin retroceso.

2. Informe del metacompilador para análisis sintáctico y su integración al léxico.

El metacompilador es sinónimo de compilador de compiladores y se refiere a un programa que recibe como entrada las especificaciones del lenguaje para el que se desea obtener un compilador y genera como salida el compilador para ese lenguaje. Sabiendo esto, en nuestro compilador tendremos por un lado un generador de analizador léxico (JFlex) y un generador de analizador sintáctico (CUP), ambos pueden integrar cada uno de sus procesos de estos compiladores y de esta forma obtener un compilador mucho más completo y personalizado. JFlex es un metacompilador que permite generar rápidamente analizadores léxicos que se integran con Java.

Las características sobre salientes de JFlex son las siguientes:  

Soporte completo con caracteres Unicode. Permite generar analizadores léxicos rápidamente.

 

Tiene una sintaxis cómoda de manipular y fácil de interpretar. Es independiente de la plataforma debido a que está diseñado para ser



integrado con Java. Permite la integración con CUP (Analizador sintáctico)

Un archivo jflex está dividido en 3 secciones: 

Opciones y declaraciones La primera parte del archivo es el bloque donde se importarán los paquetes que se van a utilizar para nuestro analizador, es decir, si en nuestro programa utilizaremos componentes del paquete útil debemos importar aquí dicho paquete: import java.util.*; Luego sigue un par de signos de porcentaje (%) para indicar que empezará la definición del bloque de configuración del analizador. El bloque de configuración se define por el conjunto de parámetros que se especifican en el archivo para decirle a nuestro a analizador como se debe comportar, cada parámetro empieza con el símbolo % y se escribe solo uno por línea, es decir, uno de bajo del otro. %unicode %line %column



Código de usuario En el siguiente fragmento de código podremos incluir código Java el cual podemos utilizar en el analizador, cabe notar que el código que aquí se escriba será incluido sin ninguna alteración al resultado final del analizador, dicho fragmento ira enmarcado entre las etiquetas%{ al inicio del código y %} al final del mismo. %{ public static void escribir(String cadena) {

System.out.println(cadena); } %} 

Reglas lexicográficas El siguiente fragmento formará parte esencial dentro del funcionamiento del

analizador, en este se definirán el conjunto de expresiones regulares que se utilizarán durante el proceso de análisis, a continuación, se presentan unos ejemplos de este tipo de declaraciones: FinDeLinea = nr | nn | nrnn

Variable = [:jletter:][:jletterdigit:]* Si = Si Entero = 0 | [1-9][0-9]*

En la próxima línea de código se especifican los posibles estados en los que se encontrará el analizador, esta funcionalidad es muy útil a la hora de identificar el contexto en el que se está realizando el análisis. %state CADENA La última parte de código es donde se le especificará al analizador los tokens y que acciones realizar cuando se encuentren dichos tokens, para inicial este fragmento debemos insertar nuevamente un doble símbolo de porcentaje (%%): "Inicio" {System.out.println("Palabra Inicio")} "+" {System.out.println("Símbolo +")} {FinDeLinea} {System.out.println("Fin de línea")} Reglas y acciones La sección de Reglas léxicas de JFlex contiene expresiones regulares y acciones (Código Java) que son ejecutadas cuando el analizador encuentra cadenas asociadas a las expresiones regulares. Así como el escáner lee las entradas, también hace seguimiento a todas las expresiones regulares y activa la acción del patrón que tenga la más grande coincidencia, por ejemplo, para la especificación anterior, la cadena Sino coincide en parte con la expresión Si, pero como la expresión regular Variable tiene mayor número de coincidencias (coincide totalmente) entonces es esta última quien ejecuta la acción. Para el caso en que dos expresiones regulares coincidan en su totalidad con una cadena entrante entonces es el patrón que se ha especificado primero el que ejecuta la acción. Estados léxicos Adicionalmente a las expresiones regulares, se pueden utilizar estados léxicos para hacer las especificaciones más exactas. Un estado léxico como una condición de inicio, una cadena, entre otros. Si el escáner se encuentra en estado CADENA, entonces solo las expresiones regulares que se estén precedidas por la condición inicial podrán ser evaluados. La condición inicial de una expresión regular puede contener más de un estado léxico, de ser así, dicha expresión regular se evaluará cuando el escáner se encuentre en cualquiera de esos estados iniciales. El estado léxico inicial del escáner es YYINITIAL y es con este el cual se empieza a escanear, si una expresión regular no tiene

condición inicial esto quiere decir que podrá ser evaluada en cualquier estado léxico que se encuentre el escáner. "Inicio" {System.out.println("Palabra Inicio")} Dos métodos importantes que se utilizan en el código de acción de una expresión regular son yybegin y yytext. yybegin se utiliza para decirle al escáner que cambie el estado léxico, por ejemplo: yybegin(CADENA), esto indica al escáner que a partir del llamado de esa función el escáner se encontrará en el estado léxico CADENA, por otro lado, tenemos yytext la cual devuelve la entrada la cual coincidió con la respectiva expresión regular. Reglas léxicas Las reglas léxicas contienen un conjunto de expresiones regulares y acciones. Definición de la sintaxis La sintaxis de las reglas léxicas de JFlex esta descrita por la siguiente gramática: LexicalRules ::= Rule+ Rule ::= [StateList] ['^'] RegExp [LookAhead] Action | [StateList] 'EOF' Action | StateGroup StateGroup ::= StateList '{'Rule+ '}' StateList ::= '' LookAhead ::= '$'| '/'RegExp

Action ::= '{'JavaCode '}'| '|' RegExp ::= RegExp '|'RegExp | RegExp RegExp | '('RegExp ')' | ('!'|'') RegExp | RegExp ('*'|'+'|'?') | RegExp "{"Number [","Number] "}" | '['['^'] (Character|Character'-'Character)* ']' | PredefinedClass | '{' Identifier '}'

| '"'StringCharacter+ '"' | Character PredefinedClass ::= '[:jletter:]' | '[:jletterdigit:]' | '[:letter:]' | '[:digit:]' | '[:uppercase:]' | '[:lowercase:]' | '.' La gramática usa los siguientes símbolos terminales: 

JavaCode Es una secuencia que describe las especificaciones del lenguaje Java.

 

Number Un número entero no negativo. Identifier Una secuencia de letras seguidas de cero o más letras, dígitos o rallas al pie (_).



Character Una secuencia de caracteres que no sean ninguno de los siguientes: |(){}[]n.*+?^$/"!



StringCharacter Una secuancia de caracteres que no sean ninguno de los siguientes: \ " Operadores en las expresiones regulares Ahora se mostrarán los operadores que se pueden utilizar en la definición de

expresiones regulares en el analizador léxico JFlex. Sean a y b expresiones regulares, entonces: 

a | b Unión Es una expresión regular que encuentra todas las entradas que sean válidas para

a ó b. 

a b Concatenación Es una expresión regular que encuentra todas las entradas que sean válidas para a

seguida de b.



a* Cerradura de Kleene Es una expresión regular que encuentra todas las entradas que sean válidas para

cero o más repeticiones de a. 

a+ Iteración Es una expresión regular que encuentra todas las entradas que sean válidas para

una o más repeticiones de a. Es equivalente a aa* 

a? Opción Es una expresión regular que encuentra todas las entradas que sean válidas para

cero o una ocurrencia de a. 

!a Negación Es una expresión regular que encuentra todas las entradas que sean válidas para

cualquier expresión diferente de a. 

a{n} Repetición Es una expresión regular que encuentra todas las entradas que sean válidas para

exactamente n repeticiones de a. 

a{n}{m} Es una expresión regular que encuentra todas las entradas que sean válidas para

entre n y m repeticiones de a. 

a Es una expresión regular que encuentra todas las entradas que coincidan

exactamente con a.

Precedencia de operadores JFlex usa la siguiente precedencia de operadores estándar para expresiones regulares:    

Operadores unarios posfijos ('*', '+', '?', {n}, {n,m}) Operadores unarios prefijos ('!', '∼') Concatenación (RegExp::= RegExp Regexp) Unión (RegExp::= RegExp '|'RegExp)

Entonces la expresión a | abc | !cd* terminará convertida en (a|(abc)) | ((!c)(d*)).

Métodos y atributos de JFlex asequibles en el código de acción Todos los métodos y atributos asequibles para el código de acción de JFlex tiene el prefijo yy para evitar que al momento de que el usuario. Los use generen conflicto con otros métodos o atributos de las demás clases. JFlex no tiene métodos ni atributos públicos o privados, por el contrario utiliza los prefijos yy y zz para indicar que estos pueden ser usados en el código de acción o para el código interno respectivamente. El API actual que se puede utilizar en el código de acción es: 

String yytext() Devuelve la cadena que coincidió con la respectiva expresión



regular. int yylength() Devuelve el tamaño de la cadena que coincidió con la respectiva



expresión regular. char yycharat(int pos) Devuelve el carácter que se encuentra en la posición pos de



la cadena que coincidió con la respectiva expresión regular. void yyclose() Cierra el ujo de la entrada de datos, por tanto a todas las entradas

 

siguientes arrojara n de archivo. int yystate() Devuelve el estado léxico actual del analizador. void yybegin(int estado) Cambia el estado léxico actual del analizador por el



nuevo estado especicado como parámetro. int yyline Contiene el número de la línea en la que se encuentra el analizador. (Solo si se incluyó la directiva%line).

 

int yychar Contiene el número del carácter que se está analizando. int yycolumn Contiene el número de la columna en la que se encuentra el analizador. (Solo si se incluyó la directiva%column)

CUP es un metacompilador utilizado para generar un analizador sintáctico ascendente con algoritmos LALR. CUP es el homólogo para Java del programa YACC utilizado en C. Sintaxis de un archivo .CUP Un archivo de entrada CUP consta de las siguientes cinco partes:

1. Definición de paquete y sentencias import. 2. Sección de código de usuario. 3. Declaración de símbolos terminales y no terminales. 4. Declaraciones de precedencia. 5. Definición del símbolo inicial de la gramática y reglas de producción. Sentencias import e inclusión de paquete Las especificaciones comienzan de forma opcional con las directivas package y import Estas tienen la misma sintaxis y juegan el mismo rol que el package y el import de un programa normal escrito en Java. La declaración de un paquete tiene la forma: package nombre_del_paquete; donde nombre_del_paquetes es el nombre del paquete al que se está incluyendo la clase en Java. En general, CUP implementa las convenciones léxicas de Java, como por ejemplo, soporta los dos tipos de comentarios que soporta Java. Después de la declaración opcional de package, luego se pueden importar cero o más paquetes Java. Al igual que un programa escrito en Java importar un paquete se hace de la forma: import nombre_del_paquete.nombre_de_la_clase; o import nombre_del_paquete.*; En general, la declaración del paquete indica en donde se van a incluir las clases sym y parser que son generadas por el analizador. Todos los import que aparezcan en el archivo fuente parecerán luego en el archivo de la clase parser permitiendo de esta forma utilizar las clases incluidas en el código de acción. Código del programador Después de la declaración opcional de import y package, viene una serie de declaraciones opcionales que permiten al usuario escribir código que luego hará parte del analizador generado como parte del archivo parser, pero separado en una clase no-pública que contendrá todo el código escrito por el usuario. Este código va incluido entre la siguiente directiva: action code {: ... :};

en donde el código que se incluirá en el archivo parser será el que esta incluido entre las etiquetas {: :}. Luego de la declaración del código de acción se puede hacer la declaración opcional del código del analizador el cual se agregará directamente a la clase parser, este código es útil cuando se va a personalizar algunos de los métodos del analizador: parser code {: ... :}; Otra vez, el código que se copia dentro de la clase parser es el que se encuentra entre las etiquetas {: :}. La siguiente declaración opcional es: init with {: ... :}; Esta declaración provee el código que se va a ejecutar antes de que el analizador llame al primer token. Esta declaración es usada usualmente para inicializar el escáner con tablas y cierto tipos de datos que luego podrán ser utilizados por las acciones semánticas. En este caso, el código se escribirá en un metodo void que se encuentra dentro de la clase parser. La siguiente declaración opcional permite indicar al analizador como debe preguntar por el siguiente token del escáner. scan with {: ... :}; Al igual que la declaración init el código de este bloque se incluye en un método dentro de la clase parser, de cualquier forma este método deberá devolver un objeto de tipo java_cup.runtime.Symbol, en consecuencia con esto el código que sea incluido dentro de la declaración scan with deberá devolver un objeto de este tipo.

Símbolos terminales y no terminales Seguido de las declaraciones de código de usuario viene la primera parte requerida de las especificaciones: la lista de símbolos. Esta declaración es la responsable de listar y asignar un tipo para cada símbolo terminal o no terminal que aparece en la gramática. Como se mostrará, cada símbolo terminal o no terminal está representado en tiempo real por un objeto de tipo Symbol. En el caso de los terminales, estos son retornados por el escáner y colocados en la pila del analizador. En el caso de los no terminales reemplazan una serie de objetos Symbol en la pila del analizador siempre y cuando este concuerde con

la parte derecha de alguna producción. Para efectos de especificar al analizador que tipo de objeto es cada símbolo terminal o no terminal, se hace de la siguiente forma: terminal Nombre_de_la_clase simbolo1, simbolo2, ... ; terminal simbolo1, simbolo2, ... ; non terminal Nombre_de_la_clase simbolo1, simbolo2, ... ; non terminal simbolo1, simbolo2, ... ; donde Nombre_de_la_clase es la clase a la que pertenece el objeto simbolox.

Definición de la precedencia de operadores La siguiente sección que es opcional, es donde se especifica la precedencia y asociatividad de los terminales. Esta herramienta es muy útil a la hora de analizar gramáticas ambiguas. Como se muestra en el siguiente ejemplo existen tres tipos de declaraciones: precedence left terminal, terminal, ...; precedence right terminal, terminal, ...; precedence nonassoc terminal, terminal, ...; La coma separa los terminales que deben tener asociatividad y en ese nivel de precedencia que se esta declarando. El orden de la precedencia del mayor a menor es de abajo a arriba. En el siguiente ejemplo el producto y la división son asociativos y tiene mayor precedencia que la suma y la resta que son asociativos entre ellos. precedence left SUMA, RESTA; precedence left PRODUCTO, DIVISION;

La precedencia resuelve problemas de reducción. Por ejemplo, en la entrada 3 + 5∗3, el analizador no sabe si reducir la pila, si por el + o por el ∗, de cualquier forma, utilizando precedencia se tiene que el ∗ tiene mayor precedencia que el + por lo tanto reducirá primero por el ∗. Definición del símbolo inicial de la gramática y reglas de producción Para denir el símbolo inicial de la gramática se utiliza la construcción start with...;

start with Prog; Ejecutando en generador de analizadores sintácticos Como se ha mencionado, CUP esta escrito en Java. Para invocarlo se necesita un interprete Java para invocar el método estático java_cup.Main(), pasando un arreglo de string que contiene las opciones. La forma mas fácil de invocarlo es directamente desde la línea de comando de la siguiente forma: java -jar java-cup-11a.jar opciones erchivo_de_entrada Si todo ha salido bien se deberán generar dos archivos .java, el sym.java y el parser.java. La siguiente es la lista de opciones que se pueden pasar al archivo que genera el código del analizador: package name: Se le especifica al analizador que las clases sym y parser serán agregadas al paquete name. Por defecto estas clases no serán agregadas a ningún paquete. 

parser name: Hace que el archivo del analizador se llame name en vez de parser



symbols namr: Hace que el archivo de símbolos se llame name en vez de sym expect



number: Por lo general el analizador resuelve problemas de precedencia, esta opción coloca un límite a ese número de errores que se pueden corregir, una vez exceda este límite el analizador se detendrá por sí solo.



nowarn: Evita que analizador arroje mensajes de prevención o alertas (En ingles: warnings)



nosummary: Normalmente, el sistema imprime una lista con cierto tipo de cosas como los terminales, no terminales, estados del analizador, etc. al final de cada ejecución. Esta opción elimina esta funcionalidad.



progress: Esta opción causa que el sistema imprima pequeños mensajes indicando varias partes del proceso de la creación del analizador.



dump: Esta opción causa que el sistema imprima pedazos de la gramática, estados del analizador y tablas de análisis con el en de resolver conflictos en el análisis.



time: Causa que el sistema muestre detalles de las estadisticas sobre los tiempos resultantes del analizador. Muy útil para futuros mantenimientos y optimización del analizador.



version: Causa que CUP imprima la versión actual con la que se esta trabajando.

3. Informe de actividad donde documente paso a paso como construyó su analizador sintáctico. En la construcción de nuestro analizador sintáctico resaltaremos los pasos más importantes en la construcción del mismo a continuación: 1. Descargar CUP y agregarlo a nuestro proyecto de NetBeams 2. Luego de descargado el CUP descomprimir y ese archivo copiarlo en nuestro

directorio donde se aloja nuestro proyecto en nuestro caso

3. Ahora construimos nuestro archivo flex el cual tendrá la siguiente estructura (cada sección se separa mediante %%):  Código de usuario  Opciones y declaraciones  Reglas léxicas Quedará definido de la siguiente manera: import java.lang.System; import java_cup.runtime.Symbol; %% %cup %ignorecase %type java_cup.runtime.Symbol %class scanner %implements java_cup.runtime.Scanner %{ public void PrintToken(String str){ System.out.println(str); }

%} %eofval{ {System.exit(0);} %eofval} %line %char

%state COMENTARIO EspacioOTerminador = [\ \t\f\r|\n|\r\n] Digito = [0-9] Letra = [a-zA-Z] INTAUX = ((("+"|"-")?({Digito})+)(("Ox(OX)"|"0")?)) ENTERO =((("+"|"-")?({Digito})(({Digito})*))(("Ox(OX)"|"0")?)) INT = ({ENTERO}) SEMI = ";" COMMA = "," TYPE = "int" BINARYOP = ("+"|"-"|"*"|"/"|"%") UNARYOP = ("++"|"--") LOGICOSOP = (">"|">="|"", ">=", "