Download compilador - Biblioteca de la UNS

Teoría de lenguajes y compiladores
Unidad I
Analizadores lexicográficos
Semana 1
Introducción
Objetivo General
El alumno al finalizar el curso desarrollará
aplicaciones que le permitan determinar si
una sentencia corresponde a la estructura
gramatical
de
un
lenguaje
de
programación.
Así
mismo
estará
capacitado para proponer nuevas formas
estructurales en la definición de lenguajes
de programación.
Objetivo Específico
Desarrollar un analizador
lexicográfico
Objetivo Instruccional
Analizar la evolución de los lenguajes de
programación;
estableciendo
las
diferencias entre ellos, así como los
elementos que los conforman.
Reflexión:
Si eres programador y
desarrollas algo, pero no
logras hacer que sirva …
… llámalo versión
Contenidos
Introducción
Evolución de los lenguajes de
programación
Categorías de los lenguajes
Organización de un programa
Notación gramatical de los lenguajes
Compiladores e interpretes
Introducción
Programación
“La programación, es
el arte de organizar la
complejidad”.
“Organizar los cálculos
de manera que nuestros
sentidos sean suficientes
para garantizar que el
cómputo arrojado, sean
los resultados esperados”.
Introducción
Requisitos mínimos para
desarrollar un lenguaje
•Ayudar a escribir buenos
programas.
•Fácil de leer.
•Fácil de entender.
•Fácil de modificar.
Introducción
Programación vs Mantenimiento
Creación inicial
y verificación
de un programa.
Se refiere a las
correcciones
y los cambios
que se realizan en un
programa después
de su desarrollo.
Introducción
Estructura y Organización de
los Programas
“Son claves para
manejar programas
muy grandes”
La legibilidad de un programa puede
mejorarse organizándolo de tal manera
que cada parte pueda entenderse en
forma relativamente independiente del
resto.
Introducción
Von Neumann
Introduce el concepto de programa
almacenado.
Propuso que los programas se
almacenaran de forma digital en la
memoria de la computadora junto
con los datos
Por otro lado, se dio cuenta que la aritmética
decimal usada por la ENIAC podía ser reemplazada
usando aritmética binaria. Este diseño conocido
como ARQUITECTURA de VON NEUMANN, ha sido la
base para casi todas las computadoras digitales.
Introducción
Organización de la Máquina
de Von Neumann
Unidad de
control
Unidad
Aritmética
Acumulador A
Unidad de
entrada y
salida
Registro R
Memoria para instrucciones y
datos
Introducción
Elementos de la máquina de Von
Neumann
Determina el
orden de
ejecución de las
instrucciones.
Flujo de
control
A una localidad de
memoria podía
asignársele el valor
contenido en el
acumulador
Datos
Comprende…
Asignaciones
a localidades
de memoria
Los enteros eran la
única forma de datos
Operaciones
aritméticas
Podía sumar,
restar, multiplicar,
dividir y tomar el
valor absoluto de
un numero.
Introducción
Codificación
Lenguaje de máquina: 00000010101111001010
00000010101111101010
00000011001100100110
Lenguaje Ensamblador: Load I
Add J
Store K
Lenguaje alto nivel:
K=I+J
Introducción
Primera experiencia
En los años 50, se creía que los programas eficientes
solo podían escribirse manualmente, usando algunas
variantes de lenguajes de máquina. (Fortran)
¡ Surge preocupación por la eficiencia de
ejecución !
•El alto costo de creación de código ensamblador o
de máquina fue la principal motivación para el
desarrollo de Fortran (FORmula TRANslation).
•Ninguna notación diferente del lenguaje de
máquina puede ejecutarse directamente en un
computador.
…Primera experiencia
Programa fuente
Tiempo de traducción
Introducción
Compilador
Tiempo de ejecución
Entrada
Código destino
Salida
…Primera experiencia
Introducción
Beneficios de los lenguajes de alto nivel
•Surgimiento de usuarios y programas
nuevos.
•Proporciona notaciones fáciles de leer.
•Proporciona portabilidad (Usuarios pueden
intercambiar programas)
…Primera experiencia
Introducción
Estructura y legibilidad vs Eficiencia
•La legibilidad y la capacidad de modificar los
programas pueden contribuir también a la
eficiencia.
•La eficiencia de un programa depende de las
decisiones tomados en los niveles de diseño, desde
la concepción hasta la elección de estructuras de
datos y algoritmos para el código final.
•El refinamiento de código se realiza con la mejora
de puntos críticos, que son las pequeñas partes muy
utilizadas en donde el programa la mayor parte de
su tiempo de ejecución.
Evolución de los lenguajes
Generaciones de los lenguajes
de programación
Generación
Nombre
Particularidad
Primera
De maquina
Especifico para cada microprocesador,
uso de código binario
Segunda
Ensamblador
Uso de nemotécnicas que abstraen al
lenguaje de maquina
Tercera
De alto nivel
Lenguajes estructurados con comandos
cercanos al lenguaje natural
Cuarta
Propósito
especial
Programas orientados a programas
específicos
Quinta
Naturales
Incluye inteligencia artificial y sistemas
expertos
Categoría de los lenguajes
Clasificación de los lenguajes
de programación
Lenguaje
de
máquina
• Orientado al
microprocesador
(Sistema binario)
Lenguaje
de bajo
nivel
• Ensamblador (Usa
código nemónico y
también esta orientado
a un microprocesador)
Lenguajes
de alto
nivel
• Orientado
a que las
personas
entiendan
y escriban
los
programas
Organización de un programa
Formas de organización
Existe más de una forma para solucionar un
problema, así que hay mas de una forma
para estructurar un programa. La estructura
tiene
que
establecerse
para
cada
programa.
Formas:
• Descendente
• Modular
•Objetos
Notación gramatical de un lenguaje
Estructura sintáctica
•La sintaxis de un lenguaje especifica como
están construidos los programas en dicho
lenguaje.
•La estructura sintáctica, es decir la estructura
impuesta por la sintaxis del lenguaje,
constituye la herramienta para trabajar con el
lenguaje.
•Se utiliza para organizar descripciones de
lenguajes y traductores, así como reglas para
entender los programas escritos en un
lenguaje.
Notación gramatical de un lenguaje
Notación sintáctica
La sintaxis de un lenguaje programación casi
siempre se especifica usando alguna variante de
una notación conocida como GRAMATICA
INDEPENDIENTE DEL CONTEXTO o simplemente
GRAMATICA.
Las variantes de notación son:
• BNF (Forma de Backus-Naurs)
•
BNFE (BNF extendida)
•
ESQUEMAS DE SINTAXIS
Notación gramatical de un lenguaje
BNF (Forma de Backus-Naurs)
La siguiente notación describe la sintaxis de los
números reales.
<numero-real> ::= <secuencia-digitos> . <secuencia-digitos>
<secuencia-digitos> ::= <digito> | <digito><secuencia-digitos>
<digito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Otro ejemplo:
<expresion> ::= <expresion> + <termino> | <expresion> - <termino> | <termino>
<termino> ::= <termino> * < factor> | <termino> div <factor> | <factor>
<factor> ::= <expresion> |<termino> | <constante>
Notación gramatical de un lenguaje
BNFE (BNF Extendida)
Los símbolos no terminales comienzan con letras
mayúsculas, los terminales que consisten en símbolos
como + , - se colocan entre comillas sencillas y los
símbolos terminales en negrita.
Además:
• Una barra vertical |, representa una opción
• Los paréntesis, ( y ), se usan para agrupar
• Las llaves, { y }, representan cero o mas repeticiones
• Los corchetes, [ y ], representan una construcción opcional
Ejemplo:
Expresion ::= Termino { ( ´+´ | ´-´ ) Termino }
Termino ::= Factor { ( ´*´ | div ) Factor }
Factor ::= ´(´ Expresion ´)´ | Variable | Constante
Notación gramatical de un lenguaje
ESQUEMA DE SINTAXIS
Se construye un sub-esquema para cada símbolo no
terminal.
Expresión
Termino
+
Termino
-
Termino
Factor
*
Factor
div
Factor
(
Termino
Variable
Constante
)
Notación grafica de un lenguaje
Diagrama de Conway
Un diagrama de conway es un grafo dirigido que tiene dos
componentes esenciales, además de las líneas de flechas que
sirven de conectivas.
• El “rectángulo” para indicar que en ese punto hay una
metanoción del vocabulario no terminal N ( y por tanto tendrá
otro diagrama de conway para definirle).
• El “circulo” para indicar que en ese punto hay un símbolo
terminal, que por lo tanto será un elemento del vocabulario
terminal T.
En estos diagramas se acostumbrará a comenzar el recorrido por
la izquierda, por la rama que suele llevar muy cercano a ella el
nombre de la metanoción a definir, se sigue el recorrido en el
sentido de las flechas y cada elemento que se va encontrando
se toma y se concatena a lo que ya se tuviera.
Notación grafica de un lenguaje
Diagrama de Conway
Entero
Digito
Identificador
Letra
Letra
Digito
Notación grafica de un lenguaje
Diagrama de Conway
Parametros
(
Lista_id
Lista_id
Identificador
,
)
Compiladores e interpretes
Conceptos relacionados
Arquitectura de
Computadoras
Teoría de
Lenguajes
Lenguajes de
Programación
Compiladores
Ingeniería de
Software
Teoría de
Algoritmos
Con algunas técnicas básicas de escritura de compiladores se
pueden construir traductores para una gran variedad de
lenguajes y máquinas
Compiladores e interpretes
Compiladores
Un compilador es un programa que lee un
programa en un lenguaje y lo traduce a un
programa equivalente en otro lenguaje, y
además informa al usuario sobre la presencia
de errores en el programa de entrada
programa
fuente
compilador
mensajes
de error
programa
objeto
Compiladores e interpretes
HISTORIA
Computadora
Persona
Código
Máquina
Ensamblador
Código
Máquina
Ensamblador
Código
Máquina
Lenguaje
Ensamblador
Lenguaje
Ensamblador
Compilador
Lenguaje de
Alto Nivel
Compiladores e interpretes
Tipos de sistemas de compilación
• ENSAMBLADOR
Traducen programas escritos en lenguaje ensamblador a
código máquina
• COMPILADOR
Traducen programas escritos en lenguaje de alto nivel a
código intermedio o a código máquina
• INTERPRETE
No genera código objeto, analiza y ejecuta
directamente cada proposición del Programa Fuente
(PF)
• PREPROCESADOR
Sustituyen macros, incluyen archivos o extensión del
lenguaje.
Compiladores e interpretes
Sistema de procesamiento de un
lenguaje
estructura del programa fuente
preprocesador
programa fuente
compilador
programa objeto en lenguaje ensamblador
ensamblador
código de máquina relocalizable
biblioteca
editor de carga y enlace
código de máquina absoluto
archivos obj.relocal.
Compiladores e interpretes
PARTES DE LA COMPILACIÓN
• Análisis (Etapa Inicial):
Divide al Programa Fuente en sus elementos
componentes y crea una representación
intermedia. Se determinan las operaciones y
se registran en una estructura de árbol (ej.
árbol sintáctico)
• Síntesis (Etapa Final):
Construye el Programa Objeto deseado a
partir de la representación Intermedia
(requiere técnicas más especializadas)
Compiladores e interpretes
UN AMBIENTE GENERAL DE COMPILACIÓN
Fuente
Análisis léxico
Análisis sintáctico
Análisis semántico
Intermedio
Generador de código
Código relocalizable
Enlazador
Objeto
Más:
Sistemas de
edición y
depuración
Compiladores e interpretes
FASES DE UN COMPILADOR
PROGRAMA FUENTE
analizador léxico
administrador
de la tabla
de símbolos
analizador sintáctico
analizador semántico
generador de código intermedio
optimizador de código
generador de código
manejador
de errores
PROGRAMA OBJETO
Cada fase transforma al PF de una representación
a otra
Compiladores e interpretes
ESQUEMA DE BLOQUES DE UN
COMPILADOR
FUENTE
Compilador
ANALISIS
Scanner
Parser
SINTESIS
Prep. para la Gen.
del código
OBJETO
Gener. del código
Tabla
de
símbolos
Compiladores e interpretes
ESTRUCTURA FUNCIONAL DE UN
COMPILADOR
(de una pasada)
SENTENCIA
Fuente
Explorador
Reconocedor
Generador
de código
Tabla de
símbolos
Objeto
Compiladores e interpretes
HERRAMIENTAS PARA CONSTRUCCIÓN DE
COMPILADORES
Lex
y
YACC
• Herramientas que nos permiten desarrollar
componentes o la mayor parte de un
compilador
• Son un recurso invaluable para el profesional
y el investigador
• Existen paquetes freeware
Teoría de lenguajes y compiladores
Unidad I
Analizadores lexicográficos
Semana 1
Introducción