1. No category

Control de Secuencia
Øyvind Mo
Edgar Acosta
Adrián López
1
Las Estructuras de Control de
Secuencia
• Proveen el marco de interacción para la
ejecución de operaciones y datos.
• Controlan el orden de ejecución de las
operaciones.
2
Categorias de ECS
• Expresiones
• Instrucciones o grupos
de instrucciones
• Programación
Declarativa
• Subprogramas
• Implícitas
• Explícitas
3
Categorías de ECS
•
•
•
•
Expresiones Aritméticas
Instrucciones o grupos de instrucciones
Programacion Declarativa
Subprogramas
4
Arboles para representar
expresiones
• Composición funcional
• Operaciones y sus respectivos operandos
• Resultados de operaciones forman nuevos
operandos
• Operaciones representadas por niveles
• No se define precedencia en operaciones en
el mismo nivel
5
Ejemplo: Raíz de 2do grado
-B+
B2
/
–4*A*C
*
+
2*A
_
SQRT
B
-
2
^
B
A
*
2
*
4
C
A
6
Representación Sintáctica
• Linealización de arboles.
•Notación Prefija (Polaca)
•Notación Polaca Cambridge
•Notación Postfija
•Notación Infija
7
Representación Sintáctica : Ejemplo
*
+
A
B
C
D
Prefija:
*+AB-CD
Prefija Cambridge:
(*(+AB)(-CD))
Infija:
(A+B)*(C-D)
Postfija:
AB+CD-*
8
Representación Semántica
• Evaluación de expresiones prefijas.
•Características
–Evaluación en una sola pasada
–Necesidad de saber el numero de argumentos por tipo de
operación
–No hay necesidad de paréntesis
–Similitud con llamadas a funciones
–Operaciones con cualquier número de operandos
–Decodificacion sencilla a secuencias de código
9
Representación Semántica
• Evaluación de expresiones infijas.
•Características
–Forma común de expresar las expresiones aritméticas
–Trabaja con operadores binarios
–Funciones y operadores unarios implementados a traves de
notación prefija o postfija
–Necesidad de uso de paréntesis para evitar ambigüedad
–Decodificación compleja a secuencias de código
10
Jerarquía de operaciones
• Orden de precedencia de operadores
•Asociatividad
• Lenguajes
–Izquierda sin Jerarquía de operaciones
a-b-c evaluado (a-b)-c
–Derecha
a^b^c evaluado a^(b^c)
11
Jerarquia de Operaciones : Ejemplo
• C
A= =B | C= = D evaluado (A= =B) | (C= = D)
Precedencia del operador = = sobre |
• Pascal
A=B | C=D evaluado A=(B | C)=D
Precedencia del operador | sobre =
12
Representación de
Expresiones en Tiempo de
Ejecución
13
Etapas de traducción
• Establecer estructura de árbol
• (opcional) decidir el órden óptimo
de evaluación
14
Formas en que se traducen
las expresiones en notación
infija
• Código máquina
• Estructura de árbol
• Prefija o postfija
15
Evaluación con las
representaciones de árbol
de expresiones
16
Problema 1. Reglas de
evaluación uniforme
17
Evaluación glotona
Ejemplo:
(a+b)*(c-a)
*
+
a
-
b
c
a
18
Ejemplo de evaluación
glotona que no hace lo que
se espera
Z+(Y=0?X:X/Y)
+
Z
IF
=
/
Y
X
0
Y
X
19
Evaluación apática
Es prohibitiva para los lenguajes aritméticos
20
Problema 2. Efectos
secundarios
a×fun(x)+a
Si a vale 1 inicialmente y fun(x) devuelve 3 y tiene el
efecto secundario de modificar el valor de a a 2 el
órden de evaluación es crítico:
• Evaluando en secuencia: 1 × 3 + 2 = 5
• Evaluando a solamente una vez: 1 × 3 + 1 = 4
• Evaluar fun(x) antes que a: 2 × 3 + 2 = 8
21
Problema 3. Condiciones de
error
22
Problema 4. Expresiones
Booleanas de corto circuito
if ( ( A == 0 ) || ( B / A > C ) ) { . . . }
while ( ( L <= UB ) && ( V[L] > C) ) { . . . }
Solución de Ada
if ( A = 0 ) or else ( B / A > C) then
23
Categorías de ECS
•
•
•
•
Expresiones Aritméticas
Instrucciones o grupos de instrucciones
Programacion Declarativa
Subprogramas
24
Control de secuencia entre
instrucciones
• Instrucciones básicas
• Tipos de control de secuencia a nivel de
instrucciones
• Control de secuencia explícita
• Diseño estructurado de programas
25
Instrucciones básicas
• Instrucciones de asignación
•
•
•
•
•
•
•
•
A:=B
A=B
MOVE A TO B
AB
(SETQ A B)
A += B
++A
A++
(PASCAL)
(C, Java)
(COBOL)
(APL)
(LISP)
(C, Java)
26
Instrucciones básicas
• Instrucciones de entrada y salida.
<STDIN>;
System.out.println(”Hola”);
• Otros instrucciones de asignación.
– NEWLINE = TRIM(INPUT)
– PadreDe(X,Juan), PadreDe(Y,Juan), not (X=Y).
27
Tipos de control de secuencia a
nivel de instrucciones
• Composición
• Alternación
• Iteración
28
Control de secuencia explicita
• GOTO incondicional
• GOTO condicional
• BREAK
• CONTINUE
29
Goto : Ejemplo
#include <iostream.h>
void main()
{
int n;
for(;;)
{
cout <<“Ingresa un número (0 para terminar): ";
cin >> n;
cout << n <<" al cubo es: " << n*n*n << "n";
if(n == 0) goto esc;
}
esc:
cout << endl;
}
30
Problemas con Goto en Basic
C64 BASIC:
750 ifnv(0)=0thenf=0:goto770
760 goto790
770 ifint(rnd(1)*100+1)<=nthen800
780 nextx:goto1640
790 ifn<>nv(1)andn<>0thennextx:goto1640
31
Break
#include <iostream.h>
void main()
{
int n, count = 0, sum = 0;
cout <<"Enter positive integers. Terminate input with 0:n";
for (;;) {
cout << "t" <<count + 1 << ": ";
cin >> n;
if(n ==0) break;
++count;
sum += n;
}
cout <<"The average of the " << count << " numbers is "
<< (float) sum / count << endl;
}
32
Continue
#include <iostream.h>
int main()
{
int n = 0;
for(;;)
{
n++;
if (n%7 == 0) continue;
cout << "n = " + n;
}
}
33
Diseño estructurado de programas
1. Diseño jerárquico
2. Representación del diseño en el código del
programa
3. La secuencia textual = la secuencia actual
4. Un grupo de instrucciones tiene solamente
una función
•
(No usar GOTO)
34
Control de Secuencia Estructurado
• Conjunto de instrucciones de control en un
lenguaje de alto nivel
– Composición o Agrupamiento
– Condicionales o de Alternación
– Iteración
35
Agrupamiento
• Contienen una o más instrucciones
• Actúan como un solo bloque
• Las instrucciones contenidas se ejecutan
secuencialmente
Ejemplos:
Begin
{
...
...
End
}
36
Condicionales
• Expresan la ejecucion alternada de dos
instrucciones o la ejecución condicional de
una instrucción
• La alternativa se controla por medio de una
condición.
37
Instrucción IF : Ejecución Opcional
...instrucciones antes del IF
Evalua S = condición (0=False, 1=True)
If condición then
instrucción
end if
Salta a L0 + S
L0: Salta a L2 (no hay instrucciones
para Condición = false)
L1: Instrucciones para Condición = True
L2: Instrucciones después del if ...
38
Instrucción IF : Ejecución Alternativa
...instrucciones antes del IF
If condición then
instrucción1
else
instrucción2
end if
Evalúa S = condición (0=False, 1=True)
Salta a L0 + S
L0: Salta a L1
Salta a L2
L1: Instrucciones para condición = False
Salta a L3
L2: Instrucciones para condición = True
L3 instrucciones después del if ...
39
Instrucción CASE
• Evalúa una condición y
compara varios valores
hasta encontrar una
equivalencia.
Evalua T de la variable Valor
Salta a L0 + T
L0: Salta a L1
Salta a L2
Case Valor
when 0 begin
instrucción1;
end
when 1 begin
instrucción2;
end
when others begin
instrucción3;
end
end case
...instrucciones antes del Case
Salta a L3
L1: Instrucción 1
Salta a L4
L2: Instrucción 2
Salta a L4
L3: Instrucción 3
L4: instrucciones después del
Case
40
Iteración
• Proveen capacidad de repetición de
ejecución de un mismo código
• Estructuras básicas contienen un
encabezado y un cuerpo
• El encabezado controla en número de veces
que se iterará
• El cuerpo es el conjunto de instrucciones a
repetirse
41
Iteración : Ejemplos
• Repetición Simple
(Cobol) Perform cuerpo K veces
• Repetición mientras se mantiene una condición
(C) While <cond> { cuerpo }
• Repetición mientras se incrementa un contador
(Algol) for I := 0 step 2 until 30 do cuerpo
• Repetición controlada por datos
(Perl) foreach $X(@Array) { cuerpo }
• Repetición indefinida
(Ada) Loop ... Exit when <cond> ... end Loop;
42
Problemas de ECS estructurada
• Discusión del Goto
Condiciones
Salidas
Do-While-Do
multiples
excepcionales
de loops
Utilizando go to
Utilizando go to
Utilizando go to
Instrucción 1
Loop
For I := 1 to K do
If error go to α
read(x)
if Vect[I] = 0 then go to α
Instrucción 2
if EOF then go to α
Loop
If error go to α
process(x)
...
End loop;
α: Manejo de errores
On Error en VB y Raise en
Exit
en Ada e If <cond>
Ada when
como
Exit
en
Adaopción
y Break en C
Break en C como opción
como opción
On error go to α
Loop
For I = 1 .. K loop
Instrucción 1
read(x)
exit when Vect[I] = 0 ;
Instrucción 2
If EOF break
End loop;
...
process(x)
α: Manejo de errores
End loop;
43
Programas Primos
44
Componentes de un diagrama
de flujo
Nodo de función
Nodo de decisión
Nodo de unión
45
Programa Primo
46
Programa compuesto
47
Programas Primos
De
un nodos
nodo
De
De
cuatro
tres
dos
nodos
while ... do ...
if ... then ...
do ... while ...
repeat ... until ...
if ... then ... else ...
do ... while ... do
48
Teorema de estructura
Nodos originales
Nodos transformados
49
Categorías de ECS
•
•
•
•
Expresiones Aritméticas
Instrucciones o grupos de instrucciones
Programacion Declarativa
Subprogramas
50
Secuenciación entre instrucciones
no aritméticas
• Lenguajes declarativos usan formas de
control de secuencia muy distintas a los que
usan los lenguajes imperativos.
• Prolog, ML, Haskell etc.
51
Reconocimiento de patrones
• Muy importante en:
– Trabajar con cadenas de texto
• PERL
• ML
• SNOBOL4
– Ejecución y control de programas declarativos
• Prolog
• ML
• Haskell
52
Ejemplos:
• Gramáticas en BNF
– A 0A0  1A1  0  1
• (lenguajes libres de contexto)
• Expresiones Regulares
– {a,b}*a
• (lenguajes regulares)
53
Un ejemplo de SNOBOL4
START GRAMMAR = 0 | 1 | 0 *GRAMMAR 0 | 1 *GRAMMAR 1
LOOP NEWLINE = TRIM(INPUT)
: F(END)
NEWLINE (POS(0) SPAN(“01”) RPOS(0))
: F(BAD)
SN = SIZE(NEWLINE)
NEXT NEWLINE POS(0) GRAMMAR.PALINDROME POS(SN)
:S(OK) F(NOTOK)
OK
OUTPUT = “MATCH: “ PALINDROME
:(LOOP)
NOTOK SN = SN – 1
:(NEXT)
BAD
OUTPUT = “IMPROPER INPUT:” NEWLINE :(LOOP)
END
54
Un ejemplo de PERL
while ( $line = <FILE> ) {
if ( $line =~ /http:/ ) {
print $line;
}
}
O bien:
while ( <FILE> ) {
print if /http:/ ;
}
55
Un ejemplo mas interesante
s/ (\S+)\s+(\S+) /$2 $1/
MADRE
PURA
56
Prolog
• Usa reconocimiento de patrones para buscar
y conectar información.
– Padre(Abraham, Isaac)
– Padre (Isaac, Jacob)
– Abuelo(X,Y) :- Padre(X,Z), Padre(Z,Y)
– :-Abuelo(X, Jacob)
57
Reescritura de términos
• Reescritura de términos es una forma
restringida de reconocimiento de patrones.
– Gramática BNF:
• A  0B1
• B  0A
– Ejemplo de ML:
• Fun factoral(1) =
 factorial(N:int) =
1
N * factorial(N-1);
58
Unificación
• El mecanismo básico de computación en
lenguajes declarativos.
• Usa substitución.
• Asigna valores a variables.
59
Términos
• Se componen de:
– Variables [x, y, ..]
– Funciones
• Constantes [a, b, c, ...]
• Otros
[ f(x), g(x, y) ... ]
– Paréntesis [( )]
– Coma [,]
• Ejemplo: g(f(x, y), f(x, y))
60
Sustituciones
• Una sustitución mapea variables a términos.
• Es la forma mas común de asignar valores a
variables en la programación lógica.
• Muchas veces es implícita en programas
lógicos.
• {x1/t1, ... , xn/tn}
– for i[1,n], xiti
61
Ejemplos de substitución
Consideramos la substitución ={x/w, y/z}, y
el termino s = f(a, y, z)
Tenemos que s = f(a, z, z)
Si tenemos otra substitución ={w/a, z/b} se
puede componer una substitución nueva:
 =  = {w/a, x/a, y/b, z/b}
Entonces: s = f(a, b, b)
62
Unificadores
• Un unificador es una substitución que
unifica dos términos.
• Dos términos son unificados si son
idénticos.
• Ejemplo:  = {x/a, y/b} es un unificador de
s=f(a, y, z) y u=f(x, b, z), porque
s = f(a, b, z) = u
63
Unificadores Más Generales
(Most General Unifiers)
• Dos términos pueden ser unificados por
varios unificadores, pero solo uno de ellos
es el UMG (MGU).
• Ejemplo: Tanto ={x/a, y/b} como
 ={x/a, y/b, z/a} unifican s=f(a, y, z) y
u=f(x, b, z). Sin embargo solo  es el UMG
64
Unificación
1.
2.
3.
4.
Buscar un par de desacuerdo F:Salir con Exito
Unificarlo F:Salir con Fracaso
Calcular los términos nuevos
Volver a 1.
65
P(María, Juan) <el padre de María es Juan>
P(Pedro, José)
P(Luis, Pedro)
A(x,y):- P(x,z), P(z,y) <el abuelo de x es y>
:-A(Luis,w)
:- P(Luis,z) , P(z,w)
{z | Pedro}
:-A(Luis,w) :- P(Luis,Pedro) , P(Pedro,w)
{w | José}
:-A(Luis,José) :- P(Luis,Pedro) , P(Pedro,José)
66
Backtracking
67
P(María, Juan) (el padre de María es Juan)
P(Pedro, José)
P(Luis,Susana)
P(Luis, Pedro)
A(x,y):- P(x,z), P(z,y)
:-A(Luis,w)
:- P(Luis,z) , P(z,w)
{z | Pedro}
Susana}
:-A(Luis,w) :- P(Luis,Pedro)
P(Luis,Susana), ,P(Pedro,w)
P(Susana,w)
{w | José}
:-A(Luis,José) :- P(Luis,Pedro) , P(Pedro,José)
68
P(Juan, María) (el padre de María es Juan)
P(Pedro, José)
P(Luis,Susana)
P(Luis, Pedro)
A(x,y):- P(x,z), !, P(z,y)
:-A(Luis,w)
:- P(Luis,z) , P(z,w)
{z | Susana}
:-A(Luis,w) :- P(Luis,Susana) , P(Susana,w)
:-A(Luis,w) :- fail
69
Bibliografía
• From Logic Programing to Prolog (Cap II)
Krzyztof R. Apt
Prentice Hall
• Programming Languages (Cap 8)
Desing and Implementation 4a edición
Terrence W. Pratt
Marvin V. Zelkowitz
Prentice Hall
70