1

ANALISIS SINTACTICO POR PRECEDENCIA DE OPERADORES

Para una peque a clase de gramticas se puede construir con facilidad n a analizadores sintcticos por desplazamiento y reduccin. a o Estas gramticas tiene la propiedad: a No tiene reglas de produccin del tipo E o No tiene dos no terminales adyacentes A B C Se denen tres relaciones de precedencia * a <. b si a tiene menos precedencia que b . * a = b si a tiene igual precedencia que b * a .> b si a tiene ms precedencia que b a Siguiendo el algoritmo: Insertar $ al principio y al nal de la cadena de entrada Insertar las relaciones de precedencia en la cadena de entrada Mientras entrada = $ E $ hacer Recorrer entrada desde la izquierda hasta encontrar .> Buscar a la izquierda, a partir de ese punto, el primer <. Reducir el pivote que se encuentra en el medio Reinsertar las relaciones de precedencia, ignorando los no terminales.

1.1

Obtencin de relaciones de precedencia de operadores o a partir de asociatividad y la precedencia

Se establecen las siguientes reglas para seleccionar mangos apropiados para reejar un determinado conjunto de reglas de asociativad y precedencia para operadores binarios Si el operador 1 tiene mayor precedencia que 2 entonces hacer 1 .> 2 y 2 <. 1 Si los operadores 1 y 2 son de igual precedencia (por ejemplo el mismo operador), entonces hacer: * 1 .> 2 y 2 .> 1 si son asociativos por la izquierda * 1 .< 2 y 2 .< 1 si son asociativos por la derecha Adicional * ( <. id, * <. (, . * (=), <. id, ( <. , ( <. (, id .> ), ) .> , ) .> ) 1 id .> .> )

* $ <. ,

$ <. (,

$ <. id,

.> $,

id .> $,

) .> $

$ sirve como marcador de los extremos izquierdo y derecho, lo cual hace que los mangos se encuentren entre los dos s mbolos $ siempre que sea posible Ejemplo E E+E | E-E | E*E | E/E | EE | (E) | -E | id a. tiene mayor precedencia y es asociativo por la derecha b. * y / tienen la siguiente mayor precedencia y son asociativos por la izquierda c. + y - tienen menor precedencia y son asociativos por la izquierda d. espacios en blanco: entradas de error + / id ( ) $ + .> .> .> .> .> .> <. .> <. .> .> .> .> .> .> <. .> <. * <. <. .> .> .> .> <. .> <. / <. <. .> .> .> .> <. .> <. <. <. <. <. <. .> <. .> <. id <. <. <. <. <. <. <. ( <. <. <. <. <. <. <. ) .> .> .> .> .> .> . = .> $ .> .> .> .> .> .> .>

Relaciones de Precedencia de Operadores Fig. 1 1.1.1 Operadores Unarios ()

Operador Unario que no es Binario * <. * .> si tiene mayor precedencia que * <. si tiene menor precedencia que Operador Unario que adems es Binario a * Mediante la tabla de precedencia no puede analizarse correctamente cadenas como: id*-id * Solucin: Utilizar el analizador lxico para devolver dos componentes o e lxico distintos, recordando el componente lxico anterior debe dise e tinguir uno de otro. * Por ejm: Es el menos unario si antes el componente lxico le e do era un operador, un parntesis izquierdo, una coma o un s e mbolo de asignacin o

Funciones de precedencia

Los compiladores que utilizan analizadores sintacticos por precedencia de operadores no necesitan alamacenar la tabla de relaciones de precedencia. En la mayoria de los casos, la tabla se puede codicar mediante funciones de precedencia f y g que transforman simbolos terminales en enteros. Se intenta seleccionar f y g de modo que a y b,

f (a) < g(b) siempre que a < .b, . f (a) = g(b) siempre que a = b f (a) > g(b) siempre que a. > b Por lo tanto determinamos las relaciones de precedencia entre a y b mediante una comparacion numerica. Ejemplo + 2 1 2 1 * 4 3 / 4 3 4 5 ( 0 5 ) 6 0 id 6 5 $ 0 0

f g

< .id y f () < g(id) Observe que f (id) > g(id) Pero en realidad no se cumple ninguna relacion de precedencia entre id e id

Algoritmo Construccin de funciones de precedencia o Entrada Una matriz de precedencia de operadores. Salida Las funciones de precedencia que representen a la matriz de entrada, o una indicacion de que no existen. Mtodo e 1. Creense los simbolos < fa > y ga para cada a que sea terminal o $. 2. Dividanse los simbolos creados en tantos grupos como sea posible, de . manera que si a = b entonces fa y gb estan en le mismo grupo. Observese que quizas haya que poner simbolos en el mismo grupo, aunque no esten . . . relacionados por = .Por ejemplo, si a = b y c = b entonces fa y fc deben estar en el mismo grupo, puesto que ambos estan en el mismo grupo que . gb . Si ademas c = d entonces fa y gd estan en el mismo grupo aunque . a = d pueda no cumplirse 3. Creese un grafo dirigido cuyos nodos sean los grupoes encontrados en [Link] todo a y b, si a< .b, coloquese una arista desde el grupo gb al grupo fa . Si a . >b, coloquese una arista desde el grupo de fa al de gb . Observese que una arista o camino desde fa a gb signica que f(a) debe sobrepasar a g(b); un camino desde gb a fa signica que g(b) debe sobrepasar a f(a).

4. Si el grafo construido en 3 tiene un ciclo, entonces no existen funciones de [Link] no hay ciclos, sea f(a) la longitud del camino mas largo que comienza en el grupo de fa ; sea g(a) la longitud del camino mas largo desde el grupo ga . Ejemplo Considere la matriz: id id + $ gid <. <. <. + .> .> .> <. * .> <. .> <. $ .> .> .>

fid

g+

f+

f{ }

g{ }

No hay ciclos asi que existen las funciones de precedencia. Como f{ } y g{ } no tiene aristas de salida,f () = g( ) = 0. El camino mas largo desde g+ tiene longitud 1, de modo que g(+) = 1 . Hay un camino desde gid a f a g af+ a f$ , de modo que g(id) =5. Las funciones de precedencia asi obtenidas son: f g + 2 1 * 4 3 id 4 5 $ 0 0

Recuperacion de errores en el Anlisis sintctico a a por Precedencia de Operadores

Existen dos puntos en los procesos de analisis sintacticos por precedencia de operadores en los que podemos descubrir errores: 1. Si no se cumple ninguna relacion de precedencia entre el terminal de la cima entre el terminal de la pila y la entrada en curso . 2. Si se ha encontrado un mango, pero no existe ninguna produccion con este mango como lado derecho. 4

3.1

Manejo de errores mediante las reduccin o

Se considera cuando tenemos un mango pero no existe ninguna produccion por la cual reducir, en este caso se imprime un mensaje de diagnstico. La forma o en cmo se presenta este diagnstico va de dado por la accin de decidir a que o o o produccin se asemeja mas al lado derecho que se est extrayendo. o a Una posibilidad es modicarlo, eliminando o insertando simbolos, hasta encontrar la produccion mas parecida. En general, la dicultad de determinar los diagnosticos mas adecuados en este caso depende de si hay un nmero nito o innito de posibles cadenas que se u puedan extraer de la pila. Si pueden extraerse una innidad de cadenas, los mensajes de error no se pueden tabular caso por caso. Se puede utilizar una rutina general para determinar si el lado derecho de una produccion est cerca a y emitir un diagnstico espec o co diciendo que se pretend dicha produccin. a o Si ninguna produccin est cerca de la cadena extra se emite un diagnostico o a da a efectos de que hay algo errneo en la l o nea en curso. Ejemplo: . . A aEc encontrando: aac . . . < .a = a = c. > . . . . modicar a aEc . . . < . a = c . > a ilegal en linea . . . falta E en l nea . . . Para casos sencillos pueden enumerarse todos los casos de cada produccin. o

3.2

Tratamiento de errores de desplazamiento/reduccin o

En este caso cuando consultamos la matriz de precedencias, se puede dar el caso de que no se cumpla ninguna relacin entre el s o mbolo de tope de la pila y el primer s mbolo de entrada. Para cada entrada en blanco de la matriz de precedencia se debe especicar una rutina de recuperacion de errores. Modicar la pila, la entrada o ambas preveniendo los bubles innitos. Cuando hablamos de modicar la pila, la entrada o ambos lo podemos hacer como en el metodo anterior cambiando, insertando o eliminado s mbolos de la pila o de la entrada aqu es donde debemos tener cuidado de no insertar o eliminar s mbolos indenidamente al inicio de la entrada sin poder reducir o desplazar ninguno de los s mbolos, ya que podr amos caer en un lazo innito. Para esto utlizamos un mtodo que nos asegure la inexistencia de esos lazos e innitos garantizandonos que despus de la recuperacion se puede desplazar el e simbolo en curso de la entrada Ejemplo: Consideremos de nuevo la gramatica anterior y su matriz de precedencia (Fig. 1). Ahora mostraremos las las y columnas de dicha matriz que tienen entradas en blanco llenando esas entradas con los nombres de las rutinas para el manejo de errores.

id ( ) $

id e3 <. e3 <.

( e3 <. e3 <.

) .> . = .> e2

$ .> e4 .> e1

e1: // falta expresin o insertar id en la entrada: mostrar falta operando. e2: //Las expresiones empiezan con parentesis de cierre eliminar ) de la entrada: mostrar parentesis derecho no equilibrado. e3: //Despus de id o ) aparece id o ( e insertar + en la entrada: mostrar falta operador e4: //Las expresiones terminan en parentesis de apertura extraer ( de la pila: mostrar falta de parntesis derecho e

Bibliograf a
[1] Alfred V. Aho