Analizadores ascendentes

ANALIZADORES ASCENDENTES

RELACIONES LOGICAS
• Ejemplos: 8>5 es verdadera 5>8 es falso DEFINICION DE RELACION Dado un conjunto A={a, b, c, …,z} y hacemos el producto cartesiano AxA, entonces decimos que la relación R esta definida en el conjunto A cuando se tienen pares de valores AxA que la cumplen. Si dos elementos a, b satisfacen R se indica: a aRb ò (a,b)Є R R {(x,y) R={(x y) / siendox>y}

REPRESENTACION DE UNA RELACION LOGICA
Sea A={8,10,40,100,104} { , , , , } R “es mayor que” A. Matriz cuadrada
> 8 10 40 100 104 8 0 1 1 1 1 10 0 0 1 1 1 40 0 0 0 1 1 100 0 0 0 0 1 104 0 0 0 0 1

B. Grafo dirigido

PROPIEDADES DE LAS RELACIONES LOGICAS
• REFLEXIVIDAD – S cumple l relación d un elemento cualquiera d l Se l la l ió de l t l i del conjunto consigo mismo. Ejm: “es mayor oigual” • SIMETRIA – Si para todo par a,b se cumple aRb también se cumple bRa. Ejm: “es diferente” • TRANSITIVIDAD – Si se cumplen: aRb bRc entonces se cumple aRc Ejm: “es paralela , “ser hermano de”, “ser semejante a”, es paralela” ser de ser a “ser de la misma ciudad”, “ser mas alto que”, “comenzar por la misma letra”

RELACIONES DE EQUIVALENCIA
• Una relación aplicada a un conjunto quecumpla las tres propiedades: reflexiva simétrica y reflexiva, transitiva es una relación de equivalencia:
– Para todo x, xRx – Si xRy entonces tambien yRx – Si xRy, ademas yRz entonces xRz Ejemplos: Igualdad aplicada a números Ser paralela aplicada a líneas rectas Comenzar con la misma letra aplicada a palabras

lo

• Dividen su conjunto de aplicación en clases de equivalencia solo los elementosequivalencia, se relacionan con los de su subconjunto o clase de equivalencia Ejm: “ser lo la equivalencia. ser de

• Las clases de equivalencia de una relación R definida sobre un conjunto A tienen las siguientes propiedades:
– Todo elemento de una clase de equivalencia es equivalente a cualquiera de los elementos de esa clase, pero no con ningún otro elemento de A. – Todo elemento de A estáen una clase de equivalencia y solo en una

RELACIONES DERIVADAS DE UNA DADA
a. Relación Universal: U AxA {(x,y)/(x,y) U=AxA={(x y)/(x y) Є AxA} ={(x,y)/ x Є A, y Є A} b. Relación Vacía Relación que no se cumple para ningun par de elementos c. c Relación transpuesta R={(x,y)/ xRy} entonces R {(y,x)/ R`={(y,x)/ yRx} Ejm: R “es mayor que” R` “es menor que” R “es el doble de” R` “es la mitad de”d. Complemento d una relación d C l de l ió ~R={(x,y)/ ~ (xRy)}= U-R Ejm: R: es igual que ~R: no es igual que e. Suma y Productos absolutos R+S={(x,y)/(xRy) v (xSy)} “mayor que”+”igual que”=“mayor o igual que” RxS={(x,y)/(xRy) Λ (xSy)} y g que” x ”menor o igual q g que” “mayor o igual q “igual que”

f. Producto relativo R.S {(x,y)/эz R S={(x y)/эz ((xRz) Λ (zSy)} “x es el asesino delhermano de y” R “ el asesino d ” “es l i de” S “es el hermano de”

PRECEDENCIA SIMPLE
• Observación de ciertas relaciones de precedencia que existen entre los símbolos de entrada o terminales de la gramática. • L b La base f d fundamental es l l l la localización d una li ió de subcadena de la tira a analizar y para la cual existe una reducción al menos: PIVOTE • PIVOTE: subárbol sintáctico situadomas hacia la izquierda. Al comienzo se parte de la sentencia y los sucesivos pivotes ya serán formas sentenciales

• Supongamos la tira a analizar: abcdef • Si el pivote es “bcd” porque existe una regla A→bcd, entonces decimos que: – d →e, “d posee precedencia sobre e” – a ←b, “ posee menor precedencia que b” b “a d i • Para los símbolos que forman el pivote: – b‡c – c‡d • Sea la gramática: S→ aAa A → bB A→c B → Acd las relaciones de precedencia simple Acd, son:

• Se puede mostrar las relaciones de p precedencia a través de una matriz, donde en las filas y columnas van tanto símbolos terminales como no terminales. • Si son disjuntas las tres relaciones de precedencia de una gramática se dice es de precedencia simple • El pivote a ser reducido en cualquier instante debe ser la...