1
1. INTRODUCCIÓN
2
Evolución de Conceptos
3
Evolución de conceptos
ABSTRACCIÓN DE DATOS
Tipos de datos
• Elementales (HW)
• Estructurados (LP)
• Abstractos (U)
4
Tipos de datos: Elementales
• Nivel de máquina
• Primitivos
• Proporcionados por el Hw
• Enteros• Reales• Booleanos• Caracteres
5
• Nivel de lenguaje de programación (LP)
• Con base en tipos elementales
• Se utilizan constructores de tipo que al LP
• Arreglos• Estructuras (registros)
Tipos de datos: Estructurados
6
• Nivel de usuario
• Con base en tipos elementales y estructurados
• Permiten extender un LP
• Stacks• Colas• Heaps, etc.
Tipos de datos: Abstractos
7
Evolución de conceptos
ABSTRACCIÓN DE CONTROL
Lógica del código
• Sentencias
• Unidades de Programas
8
Sentencias
• Asignación
• Decisión
• Iteración
Constructores de código que facilitan la programación estructurada
9
Unidades de programas
• Permiten programación modular
• Generalizan la noción de operador
• Permiten encapsular parte de un algoritmo
• Tienen una única definición
• Tienen múltiples activaciones
10
Clasificación de los Lenguajes
11
Lenguajes
Naturales
De Programación De Máquina Simbólicos
Bajo nivel Alto Nivel• Imperativos• Funcionales• Lógicos• OO
Clasificación
12
Niveles de abstracción
L ENSLM
LAN ForTran
CO
BO
L
Pascal C
C++ Delphi
Mayor grado de abstracción
13
Lenguajes Imperativos
Los primeros LP fueron creados en los 50's: Fortran, COBOL, Pascal, C, Ada
Se denominan también, procedurales Tienen como característica cambiar el
estado de las variables por asignación
Están influenciados por la máquina en la que deben "correr": Máquina de Von Neuman
CPU RAM
14
Lenguajes Funcionales
Los primeros aparecieron en los 60's: Lisp, Apl, Forth
Aplican funciones, ya sea, recursivamente o por composición
Se caracterizan por una programación basada en expresiones (sin asignaciones)
Los usuarios NO deben preocuparse de manejar el almacenamiento de datos
15
Lenguajes Funcionales
Ejemplo en Scheme:
Función f(x) = (x + 1)2 + (2x)2
(define cuad x) (* x x))
(define (sum x) (+ x x))
(define (mult x y) (* x y))
(define (f x) (sum (cuad (sum (x 1)) (cuad (mult (2 x))))
(f 2)
25
16
Aparecieron en los 70's : PROLOG Fueron pensados principalmente para
aplicaciones de inteligencia artificial (IA) Revisan la presencia de cierta condición, la
cual, si es verdadera se ejecuta una acción Establecen relaciones de inferencia entre
clases de objetos
Lenguajes Lógicos
17
Ejemplo en Prolog:
El cero es un número naturalSi X es un número natural, entonces s(X) (sucesor
de X) también es un número natural
natural(0).
natural(s(X)) :- natural(X).
0 + X = X Si X + Y = Z entonces s(X) + Y = s(Z)
suma(0, X, X).
suma(s(X), Y, s(Z)) :- suma(X, Y, Z).
Lenguajes Lógicos
18
Algunos de ellos son Smalltalk, Eiffel, C++, Java
Representan un modelo de interacción entre objetos, cada uno de los cuales actúa en función un estado y un comportamiento
Se construyen objetos complejos a partir de objetos simples, bajo el principio de la reutilización de código
Lenguajes OO
19
Sintaxis
20
Sintaxis
Conjunto de reglas que determinan si las sentencias de un programa están bien formadas o no
Su objetivo es proveer una notación que permita la comunicación entre el programador y el procesador del lenguaje
21
Criterios Sintácticos
Legibilidad:COBOL: Write sueldo after advancing 2 lines
Facilidad de escritura:APL: AA*-1 Invierte una matriz
Facilidad de traducción:El compilador debiera generar poco código
22
Criterios Sintácticos
Ausencia de ambigüedad:
Evitar que una estructura tenga más de un significado
Por ejemplo, en Fortran M(i) puede significar:
un elemento del arreglo M, óuna llamada a la función M con
parámetro i
23
Elementos Sintácticos
Set de Caracteres Identificadores Símbolos para operadores Palabras claves y reservadas Comentarios Abreviaciones Espacios
24
Elementos Sintácticos
Delimitadores Formatos Fijo y Libre Expresiones Sentencias Estructura de Unidades de pro
grama
25
Gramáticas
26
Representa la definición formal de la sintaxis de un lenguaje
Consta de un conjunto de reglas que especifican las NORMAS de escritura para formar estructuras en un lenguaje
Gramática
27
Gramática formal destinada a la descripción de un lenguaje
Existen tres metalenguajes de uso común• BNF (Backus-Naur-Form)
• Diagramas sintácticos
• CBL (COBOL-Like)
Metalenguaje
donde BNF es el referente base
28
Notación desarrollada por los especialistas Backus y Naur para definir lenguaje Algol 60
Metasímbolos:
• < >: indica símbolo NO-TERMINAL o meta variable
• ::= : "Se define como"
• |: "o"
• { }n: Repetición. Mínimo n veces
• identificador: Palabra reservada, constante o símbolo TERMINAL
BNF
29
Número real
<real> ::= <secuencia> . <secuencia>
<secuencia> ::= <dígito> {<dígito>}0
<dígito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Identificador
<id> ::= <letra>{<letra> |<dígito>}0
<letra> ::= A | B | C | … | Z | a | b | c | … | z
BNF
30
Sentencia if
<s-if> ::= if ( <expresión booleana> ) <sentencia> |
if ( <expresión booleana> ) <sentencia> else <sentencia>
Sentencia while
<s-while> ::= while ( <expresión booleana> ) <sentencia>
Sentencia do-while
<s-do-while> ::= do ( <> ) <sentencia>
BNF
31
Número entero
<entero> ::= <dígito> | <dígito> <entero>
<dígito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Número real
<real> ::= <secuencia> . <secuencia>
<secuencia> ::= <dígito> | <dígito> <secuencia>
<dígito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
BNF Recursiva
32
<identificador> ::= <letra> | <letra> <secuencia>
<secuencia> ::= <carácter> | <carácter> <secuencia>
<carácter> ::= <letra> | <dígito>
Multilista: (1 2 (3 4 (5) 6) 7 8)
<mlista> ::= () | (<lista>)
<lista> ::= <elemento> | <elemento> <lista>
<elemento> ::= <átomo> | <mlista>
BNF Recursiva
33
Sentencia
<sentencia> ::= <simple> | <compuesta>
<simple> ::= <asignación> | <invocación> | <selección> | <repetición>
<compuesta> ::= {<sentencias>}
<sentencias> ::= <simple>; | <simple>; <sentencias>
BNF Recursiva
34
x
término
término
término
a*b c/d a * bfactor
factor
Expresión aritmética
BNF Recursiva
<ea> ::= <término> | <st> <término> | <ea> <st> <término>
<término> ::= <factor> | <factor> <sf> <término>
<factor> ::= <id> | <constante> | (<ea>)
<st> ::= + |
<sf> ::= * | /
35
Expresión
Término Expresión +
(a +b) *c
Factor
Identificador
a
*
Factor
Identificador
c
Término
Factor Término
(Expresión)
Término
Factor
Identificador
b
BNF Recursiva
36
Constituyen un método de descripción de lenguajes, equivalente a la BNF, originalmente propuesto por N. Wirth. para definir sintáxis de Pascal
Equivalencias entre BNF y Diagramas sintácticos:
Diagramas Sintácticos
37
<S> ::= <v1> | <v2> ··· | <vn>
Cada ocurrencia de un símbolo terminal corresponde al diagrama
Vn
V1
V2
Cada ocurrencia de un símbolo no terminal corresponde al diagrama
X
Diagramas Sintácticos
38
Una producción de la forma: <S> ::= {<x>}0
corresponde al siguiente diagrama
X
(mientras)
Una producción de la forma:
<S> ::= <x>{<x>}0
corresponde al siguiente diagrama
X
(repetir)
Diagramas Sintácticos
39
Identificador Letra
A
B
z
Dígito 0
1
9
_
Letra
Dígito
Letra
Diagramas Sintácticos
40
Número entero
Dígito
Número real
DígitoDígito
Diagramas Sintácticos
41
Constituye una extensión de la BNF destinada a la descripción sintáctica del lenguaje Cobol.
CBL (COBOL – Like)
• Elementos opcionales se denotan entre paréntesis cuadrados x
• Elementos alternativos se listan verticalmente entre paréntesis llave { x }
• Elementos alternativos opcionales se listan verticalmente entre paréntesis cuadrados
• La repetición de los elementos se indica mediante tres puntos a continuación de una ocurrencia del elemento x …
42
<identificador> ::= <letra> ...
<digito><letra> -
<condición>::=
<identificador> IS NOTNUMERICALPHABETIC
<entero> ::= [ + ] <digito> ...
CBL (COBOL – Like)
43
Semántica
44
Sintaxis ¡Cómo se expresa un concepto!
Semántica ¡Qué significa ese concepto!
Se define como un conjunto de reglas que describen el comportamiento de un lenguaje en tiempo de ejecución
¿Qué ocurre con la ejecución de un programa ?
¿Qué sentencias se ejecutarán?
¿Qué valores se asignan a determinadas variables?
¿Qué salidas se obtienen?
Semántica
45
Una expresión sintáctica, mediante BNF, como
puede tener dos interpretaciones semánticas
Por ejemplo, 09/04/2002 se entiende como
• 9 de Abril de 2002 en Chile
• 4 de Septiembre de 2002 en EEUU
Semántica
<fecha> ::= <d><d>/<d><d>/<d><d><d><d>
46
La especificación de la semántica de una sentencia se hará mediante la notación usada por los diccionarios enciclopédicos
Métodos formales de especificación semántica:
Operacional : Máquina teórica
Axiomático : Cálculo del predicados (PROLOG)
Denotacional : Teoría de las funciones (Lisp)
Semántica
47
Procesadores de Lenguajes
48
DEFINICIÓN
Un procesador es una máquina capaz de ejecutar acciones expresadas en algún lenguaje concreto
Actualmente, el único lenguaje concreto que existe es el lenguaje de máquina
Procesador
49
Es un decodificador que acepta programas escritos en algún lenguaje fuente y genera programas, funcionalmente equivalentes, en algún lenguaje objeto
Programa en Lenguaje Fuente
Traductor Programa en Lenguaje Objeto
PreprocesadorCompilador
EnsambladorLigador
Cargador
Traductor
50
Programa en extensión de LAN
Preprocesador Programa en LAN estándar
Pre-procesador Compilador Ensamblador Cargador
C++ CLeng.Ensam.
CódigoReubicable
CódigoEjecutable
Pre-procesador
Es un traductor cuyo lenguaje fuente es una extensión de un lenguaje de alto nivel lenguaje objeto es el estándar del lenguaje de alto nivel
Por ejemplo, C y C++
51
Es un traductor cuyo lenguaje fuente es un lenguaje de alto nivel lenguaje objeto es un lenguaje intermedio orientado
a la máquina
Programa en Lenguaje de Alto
Nivel
Compilador Programa en L orientado a la
Máquina
código objeto
Compilador
Análisis lexicográfico
Análisis sintáctico
Generación de código
Optimización de código
52
Análisis lexicográficoReconocimiento y clasificación de tokens básicos:
Constantes Identificadores Palabras reservadas, etc
Construcción de la tabla de símbolosLista de todos los símbolos y sus atributos usados en un programa (variables, etiquetas, rutinas, etc)
Compilador
53
Análisis sintáctico
Generación de un árbol de reconocimiento usando una representación interna de la gramática del lenguaje
Expresión
Término Expresión +
Factor
Identificador
a
*
Identificador
b
Factor
Identificador c
Término
Factor
Término
a + b*c
Compilador
54
Generación de códigoEnlace entre la sintaxis y la semántica de un lenguaje
Convierte el árbol de reconocimiento en una lista equivalente de instrucciones en lenguaje de máquina
Compilador
55
Optimización de códigoRefinamiento del código generado para mejorar el rendimiento en tiempo de ejecución
Ubicación de
• Construcciones semánticas redundantes
• Uso ineficiente de registros
• Etc.
Compilador
56
Es un traductor cuyo Lenguaje fuente es un lenguaje ensamblador
(representación simbólica del lenguaje de máquina) Lenguaje objeto es el lenguaje de máquina del
computador
Programa en Leng. Ensam.
Ensamblador Programa en LM
Ensamblador
57
Es un traductor cuyo Lenguaje fuente es el lenguaje de máquina
Programa en lenguaje de
máquina
Linker Programa en leng. de máquinacódigo reubicable
Lenguaje objeto es el lenguaje máquina, pero en la versión denominada código reubicable
Integra, en un único módulo de carga, el código compilado de la aplicación con el código compilado preexistente correspondiente a las librerías utilizadas
Ligador
58
Programa como código reubicable
Loader Programa como código real
Lenguaje objeto es el código real (lenguaje de máquina con direcciones absolutas)
Carga el programa en la RAM, actualizando las tablas de datos, es decir, transformado direcciones relativa en absolutas
Programa Ejecutable
Cargador
Es un traductor cuyo Lenguaje fuente es el código reubicable (lenguaje de
máquina con direcciones relativas)
59
Es un procesador cuyo lenguaje concreto es un lenguaje de alto nivel
Hoy, ningún computador es capaz de ejecutar código distinto al de máquina
Se debe simular mediante software la existencia de un computador cuyo lenguaje de máquina es un lenguaje de alto nivel (máquina virtual)
Intérprete
60
Compilador Sólo traduce
Traduce sólo una vez cada sentencia
Acepta las instrucciones de acuerdo a su secuencialidad física
Diferencias
Compilador-Intérprete
Intérprete Decodifica y ejecuta
Puede procesar varias veces algunas e ignorar completamente otras instrucciones
Acepta las instrucciones según su secuencialidad lógica
Top Related