Tema 2 Lea Ip1

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

TEMA 2: Tipos y expresiones 2.1 LEXEMAS alfabeto = conjunto finito y no vacío de símbolos base para definir lenguajes. lexema = unidad (indivisible o mínima) con significado sucesión finita de símbolos del alfabeto (uno o más) ejemplo: lenguaje de los números enteros: Σ = {0,1,2,3,4,5,6,7,8,9,+,-} lexemas: 4, +4, -94, 50678 , etc. 96+0+-, combinacion incorrectas definir cúales son los lexemas considerados válidos expresiones regulares alfabeto del lenguaje algorítmico (L.E.A.): • Las letras del abecedario en mayúsculas: A .. Z • Las letras del abecedario en minúsculas: a .. z • Los dígitos: 0 .. 9 • Símbolos de puntuación y especiales. , ; : +- _ * ) ( < >etc. La composición de los lexemas dará lugar al texto final un lexema está sobrecargado si es utilizado para más de un cometido

CLASES DE LEXEMAS: Identificadores nombres dados a los elementos del algoritmo (para referenciarlos) empiezan por una letra seguida de un número arbitrario de letras, dígitos y el símbolo de subrayado: REGION, edad_media, IVA, contador1. es indiferente utilizar letras mayúsculas o minúsculas. PI y pi son el mismo identificador. La mayor parte escogidos por el programadador, “eligiendo identificadores que denoten bien aquello que representan”,con la finalidad de que sea fácil leer y entender los algoritmos. 1

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

Palabras reservadas identificadores utilizados para uso privado y exclusivo del lenguaje no pueden ser usadas como identificadores libres se utilizan, entre otros fines, para dividir y enmarcar el texto en secciones, para aumentar su legibilidad se escribirán con minúsculas: si, mientras, tipos Literales denotan valores concretos de elementos computables 0, -1, +287, -976 Símbolos de operación denotan operaciones sobre el dominio de valores deberán ser descritos al definir los tipos. pueden estar constituidos por diversos símbolos del alfabeto. *, + denotarán respectivamente producto y adición. Separadores lexemas constituidos por hileras de uno o varios símbolos de puntuación: paréntesis, coma, dos puntos, punto y coma, punto, barra vertical, etc. en su momento veremos cual es el uso y la utilidad de cada uno a destacar el espacio en blanco y el salto de linea 2.2 TIPOS DE DATOS mecanismo para representar computacionalmente los dominios podrán ser usados en el lenguaje de especificación y en el de implementación para definirlos utilizaremos como base la teoría de conjuntos. Definición.1 Se llama tipo de dato a una clase de valores. Definición.2 Un tipo de datos se define mediante un par (L,O) donde L es un conjunto de literales y O es un conjunto de símbolos de operaciones.

2

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

signatura de una operación: notación que indica el símbolo, el número (aridad) y tipo de los argumentos (dominio de los operandos) y el tipo de su resultado (rango): o: T1 X T2 … X Tn --> T donde o es el símbolo utilizado para identificar la operación. añadiremos información sobre la posición de sus argumentos notaciones: • • • •

Infija: Los (dos) argumentos rodean al operador _o_, Prefija: El operador precede a los argumentos o_ _, Postfija: El operador sucede a los argumentos _ _o, Mixfija: Las posiciónes de los argumentos y de los símbolos de operación están mezcladas. relación dominio rango = significado de la operación = correspondencia entre el dominio y el rango condiciones de definición de una operación: predicados que deben cumplir los elementos del dominio para tener imagen. operaciones totales y operaciones parciales declaración de tipo = enunciado que establece un vínculo entre un identificador y la definición de un tipo de datos tipo anónimo. • Tipos predeclarados: los podemos usar directamente sin necesidad de declaración. son los más básicos: enteros, reales, ... • Constructores de tipos: Formas de definir tipos a partir de otros tipos. declaración: tipos T1 : C1 T2 : C2 . . . Tn : Cn Los identificadores de tipo comenzarán por la letra T. 3

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

2.3 CONSTANTES Y VARIABLES constante (simbólica) = identificador que denota uno y sólo uno de los literales de un tipo, que no cambia durante la ejecución de un algoritmo. da mayor claridad a la lectura de los algoritmos, nos permitirá modificarlos con mayor facilidad, bastará sustituir el literal (valor) en su declaración, los literales que aparezcan en el texto del algoritmo son constantes. declaración de constante: establece un vínculo entre un identificador y un literal de un tipo, si el literal implica de manera no ambigua cual es el tipo al que pertenece podemos obviarlo en la declaración en los identificadores de constantes sólo utilizaremos letras mayúsculas, dígitos y subrayados. constantes (cons) C1:l1 C2:l2 . . . Cn:ln podemos declarar varias constantes en una misma línea separándolas por punto y coma. cons C1:l1; C2:l2; … ;Cn:ln Ej: cons PI: 3.14; IVA: 0.16 NUM_MESES: 12

4

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

variable = identificador que denota un literal de un tipo, que puede modificar su valor durante la ejecución del algoritmo. El valor contenido dependerá del estado actual variable ⇒ identificador, tipo y valor (literal) declaración de variable: establece un vínculo entre un identificador y un tipo inicialización de una variable = asociarle inicialmente un literal conocido en los identificadores de variables sólo utilizaremos letras minúsculas, dígitos y subrayados. variables (var) v1:T1 v2:T2 . . . vn:Tn varias variables en una misma línea, separadas por ‘;’ Ejemplo: var x:real; y:real b:logico; m:entero; n:entero varias variables del mismo tipo, separadas por ‘,’ Ejemplo: var x,y:real b:logico m,n:entero Restricciones estáticas de los lenguajes ley que obliga a que no podemos usar en la parte derecha de una declaración ningún identificador que no haya sido previamente declarado. mantendremos el siguiente orden: constantes, tipos y variables. 5

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

2.4 TIPOS ESCALARES su conjunto de literales se define por extensión, indicando uno a uno todos sus elementos = utilizar el constructor de tipos enumerado ⇒ se dota automáticamente de un orden total al conjunto ⇒ existirán un elemento mínimo, uno máximo, y el sucesor y predecesor de cada elemento.

Enumerado el constructor de tipos más simple utilidad: otorga legibilidad a la implementación sirve de base para declarar nuevos tipos, predeclarados: entero, lógico y carácter declaración: TE : (e1,e2, … ,en) donde ei serán identificadores exigiremos que: • Todos los literales sean distintos: ei ≠ ej para i ≠ j • Sólo e1, … ,en serán literales de TE ejemplos: tipos Tdias : (lunes,martes,miercoles,jueves, viernes,sabado,domingo) Tconexion : (encendido,apagado) var dia : Tdias posicion : Tconexion quiniela : (uno,equis,dos) sus conjuntos asociados serán: L={ e1, e2, … ,en } O={suc,pred,<} el orden total será el textual operaciones: Descripción

Perfil

Condiciones

Sucesor

suc(_):TE→TE

Def(suc(e)) ≡ e≠en

Predecesor

pred(_):TE→TE

Def(pred(e)) ≡ e≠e1

Orden

_<_ :TExTE→logico

Def(ei<ej) ≡ cierto 6

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

significados: suc calcula el siguiente a uno dado pred calcula el anterior formalmente: suc(ei) = ei+1 pred(ei) = ei-1 ei < ej = cierto para i < j Ejemplos: suc(lunes) es martes pred(jueves) es miercoles lunes < jueves es cierto

Entero modelado del conjunto de los números enteros, es infinito alternativas: • modelar un subconjunto finito, un intervalo: entero : (MIN_ENTERO,…,-1,0,1,…,MAX_ENTERO) inconveniente: desbordamiento • considerarlo un conjunto infinito de literales: entero : (-∞,…,-1,0,1,…,+∞) inconveniente: no realista elegimos la segunda lo usaremos como predeclarado: Ej: cons MESES : 12 var m,n: entero conjuntos asociados al tipo: L={...,-2,-1,0,1,2,... } O={ +, *, -, /, %, ^, -} 7

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

operaciones (suponiendo m,n:entero) Descripción

Perfil

Condiciones

Adición

_+_:entero x entero → entero

Def(m+n) ≡ cierto

Sustracción

_-_:entero x entero → entero

Def(m-n) ≡ cierto

Producto

_*_:entero x entero → entero

Def(m*n) ≡ cierto

División

_/_:entero x entero → entero

Def(m/n) ≡ n ≠ 0

Resto

_%_:entero x entero → entero

Def(m%n) ≡ n ≠ 0

Potencia

_^_:entero x entero → entero

Def(m^n) ≡ (n≥0) ∧ (m = 0 ⇒ n>0)

Opuesto

-_ :entero → entero

Def(-m) ≡ cierto

significados: los establecidas para el conjunto de los enteros. Lógico (booleano) nos permitirá establecer condiciones sobre los estados del programa, para actuar en consecuencia. logico : (falso,cierto) declarado por defecto: Ej: cons DEPURAR: falso var b1, b2: logico Los dos conjuntos asociados al tipo son: L = {falso,cierto} O = {no,y,o} operaciones (Suponiendo a,b:logico) Descripción

Perfil

Condiciones

Negación

no_:logico → logico

Def(no a) ≡ cierto

Conjunción

_y_:logico x logico → logico

Def(a y b) ≡ cierto

Disjunción

_o_:logico x logico → logico

Def(a o b) ≡ cierto

A

b

aob

ayb

falso

falso

falso

falso

falso

cierto

cierto

falso

cierto

falso

cierto

falso

cierto

cierto

cierto

cierto 8

I.P.1

curso 2005/2006 a

no a

falso

cierto

cierto

falso

Tema 2. Tipos y Expresiones

Carácter permitirá realizar computación no numérica y establecer una comunicación más natural grupos: • Alfabéticos mayúsculas: ´A´,....,´Z´ • Alfabéticos minúsculas: ´a´,....,´z´ • Dígitos: ´0´,....,´9´ • Especiales: ´+´,´:´, ‘(‘,’%’,’$’,.... • De control: Caracteres no imprimibles normativas (ASCII,EBCDIC) ⇒ carácter → número natural se diferencian principalmente en: • La variedad de caracteres especiales y de control • La ordenación total que se realiza sobre el conjunto ASCII (American Standard Code for Information Interchange) caracter : (null,....,´0´,...., ´A´,....,´a´,...., del) declarado por defecto: Ejemplo: cons BLANCO: ´ ´ var ch1, ch2: caracter conjuntos asociados L = { null,....,del }, O = {suc,pred} operaciones (ch : caracter): Descripción

Perfil

Condiciones

Sucesor

suc(_):caracter → caracter

Def(suc(ch))≡ch ≠ del

Predecesor

pred(_):caracter → caracter

Def(pred(ch))≡ch ≠ null

9

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

operaciones heredadas del constructor enumerado. significados (considerando que chi es el caracter de código i): pred(chi) = chi-1 suc(chi) = chi+1 Ejemplos: suc(´A´) es ´B´ y pred(´2´) es ´1´ ¡ojo! No confundir el literal entero 9 con el literal carácter ´9´

2.5 TIPO REAL representación del conjunto de los números reales además de que posee un número infinito de elementos (literales), no es numerable ⇒ en un intervalo de dos números reales existen a su vez infinitos números reales. representaciones de los literales reales: • Notación punto fija: e.d, con e = parte entera y d parte decimal • Notación punto flotante o científica: m E ±e ≡ mx10±e m= mantisa y e = exponente consecuencia: los literales del tipo real son una representación de un conjunto de ellos. Ejemplo: El literal real 2.45 representa a todos los reales comprendidos en el intervalo semiabierto [2.45,2.46) el tipo real modela los números reales mediante el constructor enumerado ⇒ perdida de precisión en los cálculos. no planteamos el problema del desbordamiento. declarado por defecto: Ej: cons PI : 3.1415 var x,y,z: real conjuntos asociados al tipo L={...,-2.2,...,0.0,...,45.9467,...} O={+,*,-,/,^,-} 10

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

Los literales serán representados mediante notación punto fija.

operaciones (dados x,y:real ; n:entero): Descripción

Perfil

Condiciones

Adición

_+_:real x real → real

Def(x + y) ≡ cierto

Sustracción

_-_:real x real → real

Def(x - y) ≡ cierto

Producto

_*_:real x real → real

Def(x * y) ≡ cierto

División

_/_:real x real → real

Def(x / y) ≡ y ≠ 0.0

Potencia

_^_:real x entero → real

Def(x ^ n) ≡ x = 0.0 ⇒ n>0

Opuesto

-_:real → real

Def(-x) ≡ cierto

2.6 Cadenas de caracteres. conjunto finito de caracteres al que trataremos como unidad, podrán asignarse, leerse y escribirse como un tipo básico Literal: un conjunto de caracteres encerrados entre comillas dobles. L ={ ... “1”,”11”,...“A”, “a” “aa”, “Hola”} dotado de orden total considerando su código ASCII. “1032” < “A” < “AA” <”Bbcd” <”b” cadena vacía = “” operaciones : O= { +, long(), [ ], [→] } siendo x,y : cadena ; n : entero ; ch : caracter Descripción

Perfil

Condiciones

Concatenar

_+_:cadena x cadena → cadena

Def(x + y) ≡ cierto

Longitud

long(_):cadena → entero

Def(long(x)) ≡ cierto

Acceso

_[_]:cadena x entero → caracter

Def(x[n]) ≡ (0
Modificación

_[_→_] : cadena x entero x caracter → cadena

Def(x[n→ch]) ≡ (0
11

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

2.7 EXPRESIONES expresión = composición bien formada de operandos (variables y constantes) y operadores (operaciones) de tipos ya conocidos definir nuevas operaciones a partir de otras, ganando en legibilidad y expresividad. estudiar: • Sintácticamente: cuales son válidas y cúales no. • Semánticamente: que significa = qué valor representa. Sintaxis Una expresión e de tipo TE, o sea e:TE, se define como: • Un literal o constante simbólica de tipo TE • Una variable de tipo TE • Un término de la forma o(e1,....,en) con : e1,…,en expresiones de tipos T1,....,Tn y o simbolo de una operación (n-aria) de perfil o: T1 x … x Tn → TE Ejemplos: Sean m,n:entero; b1,b2:logico entonces: 3 ^ 2 * m % 4 * 5 + n es una expresión de tipo entero b1 y no b2 o b1 es una expresión de tipo lógico Semántica calcular el valor asociado ≡ evaluación de una expresión. • El valor asociado a un literal es el propio literal. • El valor asociado a una variable es el que contiene en el estado correspondiente al momento de la evaluación • El valor de una operación o(e1,...,en) es el resultado de aplicar o a los resultados de la evaluación de e1,...,en si contiene variables ⇒ puede cambiar de valor según el estado del algoritmo. combinar operaciones + distintas notaciones ⇒ ambigüedades Ejemplos: 2+3*0 2^2^3 soluciones: • Utilizar paréntesis: si E :T ⇒ (E):T. dentro de una expresión las enmarcadas con paréntesis se evalúan en primer término Ejemplo: (2+3)*4 evalúa a 20. • Definir niveles de prioridad = establecer una jerarquía 12

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

del orden en que deben ser aplicadas las operaciones. Ejemplo: 2+3*0 evaluaría a 0 o a 2 • Definir el sentido de la asociatividad: establecer si la asociatividad es por la izquierda o por la derecha. Ejemplo: ^ izquierda 2^2^3 ≡ (2^2)^3 ≡ 4^3=64 ^ derecha 2^2^3 ≡ 2^(2^3) ≡ 2^8=256 convenio sobre las operaciones ya conocidas ordenadas de más prioridad a menos: Operaciones

Asociatividad

-(cambio) no

Derecha

^

Derecha

*/%

Izquierda

+ -

Izquierda

< ,<=, > ,>=

Izquierda

<>, =

Izquierda

Y

Izquierda

O

Izquierda

los operadores + y * que son conmutativos, da igual asociarlos por la izquierda o por la derecha expresión E bien definida ≡ se cumplen las condiciones de definición de todas sus operaciones

Expresiones aritméticas devuelven un valor de tipo numérico, real o entero las variables, constantes y operaciones involucradas son las de los tipos numéricos. conjunto de operaciones asociadas a las funciones 13

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

elementales más conocidas (x:real y n:entero) Descripcion

Perfil

Condiciones

Valor absoluto

abs(_):real → real

Def(abs(x)) ≡ cierto

Valor Absoluto

abs(_): entero → entero

Def(abs(n)) ≡ cierto

Arcoseno

arcsen(_):real → real

Def(arcsen(x))≡-1≤x≤1

Arcocoseno

arccos(_):real → real

Def(arccos(x))≡-1≤x≤1

Arcotangente

arctan(_):real → real

Def(arctan(x)) ≡ cierto

Seno

sen(_):real → real

Def(sen(x)) ≡ cierto

Coseno

cos(_):real → real

Def(cos(x)) ≡ cierto

Tangente

tan(_):real → real

Def(tan(x))≡ x<>π/2+kπ ∀k∈Z

Exponencial

exp(_):real → real

Def(exp(x)) ≡ cierto

Log. Neperiano

ln(_):real → real

Def(ln(x)) ≡ x > 0

Log. en base 10

log10(_):real → real

Def(log10(x)) ≡ x > 0

Raiz cuadrada

raiz2(_):real → real

Def(raiz2(x)) ≡ x ≥ 0

cuyos significados son los atribuídos a dichas operaciones.

Expresiones lógicas devuelven un valor de tipo lógico, intervienen el tipo lógico más un conjunto de expresiones sobre otros tipos combinados mediante operaciones relacionales: Estas operaciones se aplican a tipos en los que está establecida una relación de orden en el conjunto de sus literales: O= {<,>,>=,<=,=,<>} si T es un tipo con una relación de orden total con, a,b:T Descripción

Perfil

Condiciones

Mayor estricto

_>_:TxT → logico

Def(a>b) ≡ cierto

Menor estricto

_<_:TxT → logico

Def(a
Menor o igual

_<=_:TxT → logico

Def(a≤b) ≡ cierto

Mayor o igual

_>=_:TxT → logico

Def(a≥b) ≡ cierto

Desigualdad

_<>_:TxT → logico

Def(a≠b) ≡ cierto

Igualdad

_=_:TxT → logico

Def(a=b) ≡ cierto

14

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

Ejemplo: Descripción

Perfil

Condiciones

Menor

_<_:cadena x cadena → logico

Def(a < b) ≡ cierto

Mayor

_>_:cadena x cadena → logico

Def(a > b) ≡ cierto

Igual

_=_: cadena x cadena → logico

Def(a = b) ≡ cierto

Menor o igual

_<=_:cadena x cadena → logico

Def(a <=b) ≡ cierto

Mayor o igual

_>=_:cadena x cadena → logico

Def(a >=b) ≡ cierto

equivalencias: a <> b equivale a no(a=b) a > b equivale a (a>=b) y (a<>b) a < b equivale a (a<=b) y (a<>b) a <= b equivale a (a= b equivale a (a>b) o (a=b) Ejemplos: Suponemos Tsemaforo : (rojo,amarillo,verde) 4<5 ´a´ <=´z´ amarillo > rojo 4.6 <= 4.6 un literal caracter ch será mayúscula si evalúa a cierto la expresión: ´A´<=ch y ch<=´Z´ absorción: siendo E una expresión lógica falso y E equivale a falso cierto o E equivale cierto E tiene que estar bien definida: falso y ln(0) <> 4 es una expresión lógica incorrecta los lenguajes dan un sentido operacional a este tipo de expresiones (evaluación perezosa) de tal forma que en el momento que en una conjunción (resp. disyunción) encuentra una expresión que evalúa a falso (resp. cierto) no siguen evaluando las demás expresiones pues ya es conocido el valor total independientemente de la buena o mala formación de las expresiones que restan por evaluar. 15

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

2.8 OPERADORES DE EVALUACIÓN PEREZOSA Se dice que un operador tiene una evaluación perezosa, cuando sus argumentos se evaluan sólo en el caso de que sean necesitados. tabla de y y o con la evaluación perezosa. A

b

a op b

a yp b

Cierto

?

cierto

?

Falso

?

?

falso

?

Ciert o

cierto

?

?

Falso

?

falso

2.9 Sobrecarga de operadores. cuando se redefine asociado a un tipo de datos dado consiste en asociar una función al operador cuando el tipo de datos con el que se ha de operar es el adecuado - el compilador lo determina por el contexto - el operador referencia a la función asociada se gana legibilidad y se consigue un código más compacto. + : entero x entero → entero + : real x real → real

2.10 CONVERSIÓN DE TIPOS. existen tipos que pueden compartir algún literal, o que tienen algún modo de correspondencia claro entre sus literales. Ej.: los enteros se corresponden con los reales con parte decimal nula, así 3 se corresponde con 3.0. conversor = una función que establece una correspondencia entre literales de dos tipos distintos. 16

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

Dados: TE:(e1,...., en) ch:caracter; m:entero; x:real; e:TE Descrip

Perfil

Condiciones

Valor

val(_):entero → TE

Def(val(m)) ≡ 1≤ m ≤ n

Símbolo

caracter(_):entero → caracter

Def(caracter(m)) ≡ 0≤m≤127

Código

ascii(_):caracter → entero

Def(ascii(ch)) ≡ cierto

Redondeo

redondear(_):real → entero

Def(redondear(x)) ≡ cierto

Truncado

Def(truncar(x)) ≡ cierto

truncar(_):real → entero

Real

real(_):entero → real

Def(real(m)) ≡ cierto

Posición

pos(_): TE → entero

Def(pos(e)) ≡ cierto

val(m) nos devuelve el literal enumerado asociado a m operacion pos(e) nos dará la posición de e Ejemplo: val(i) será ei ; mientras que pos(ei) será i. caracter(65) devolverá ´A´ y ascii(´A´) devolverá 65 redondear(x) escoge el entero más proximo truncar(x) escoge la parte entera, Ejs.: redondear(3.7) = 4 ; redondear(3.4) = 3 truncar(3.7) = 3. real(m) devuelve el real asociado con la parte decimal a 0. Ejemplo: real(3) devuelve 3.0 para saber si la parte decimal es nula o no, utilizamos: x=real(truncar(x)) ejemplo x=4.5 evaluaría falso; x=3.0 sería cierto

17

I.P.1

curso 2005/2006

Tema 2. Tipos y Expresiones

en las expresiones los conversores pueden ser combinados con las operaciones de los tipos ⇒ definimos: • Tipificación fuerte: Una operación puede aplicarse sólo a valores de los tipos definidos en su perfil ⇒ no se puede escribir la expresion 3.0 + 4 utilizaremos funciones de conversión explícitas (coerción). Ej: redondear(3.0) + 4 • Tipificación débil: Una función puede aplicarse a valores de los tipos definidos en su perfil o tipos considerados compatibles con él ⇒ es posible escribir 3.0 + 4 el lenguaje debe indicarnos qué tipos son compatibles y cuales son las conversiones implícitas. En nuestro lenguaje permitiremos la tipificación débil en las expresiones numéricas con enteros y reales Ejemplo: 3.4 + 2 ≡ 3.4 + real(2) y devuelve 5.4 -2.0 < 2 ≡ -2.0 < real(2)

18