Download Teoría de lenguajes y compiladores

Teoría de lenguajes y compiladores
Unidad I
Analizador lexicográfico
Semana 1
Temas
Introducción a la teoría de lenguajes. Evolución de los lenguajes de
programación. Categorías de los lenguajes. Elementos de un lenguaje de
programación. Compiladores e intérpretes.
Objetivo General
El alumno al finalizar el curso podrá desarrollar
aplicaciones que le permitan determinar si una
estructura gramatical corresponde a una sentencia
valida en la definición de un lenguaje en particular,
teniendo en cuenta el contexto sintáctico y
semántico. Así mismo estará capacitado para
proponer nuevas formas estructurales en la
definición de lenguajes de programación.
2
Objetivos Específicos
• Diseñar e implementar un analizador
lexicográfico.
• Diseñar e implementar un analizador sintáctico.
• Diseñar e implementar un analizador semántico.
3
Objetivos Instruccionales
• Describir la evolución de los lenguajes de
programación y reconociendo las categorías
existentes, así como los elementos que la
conforman.
• Establecer las diferencias entre, compiladores e
interpretes.
4
Reflexión:
Si eres programador y no
logras hacer algo que
sirva…
…llámalo versión
Temas
Introducción
Evolución de los lenguajes de programación
Categorías de los lenguajes
Elementos de un lenguaje
Compiladores e interpretes
Introducción
Programación
“El arte de 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 arroje 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 progama.
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
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
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
Organización de la máquina de Von Neumann
Introducción
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
Elementos
del
lenguaje
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.
La Máquina de Von Neumann
Introducción
Código de Máquina
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
Tiempo de traducción
Programa fuente
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
Cinco 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
Categoria 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
Elementos de un lenguaje
Como se debe estructurar un programa
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
Elementos 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.
• Esta se ha utilizado para organizar descripciones de
lenguajes y traductores, así como reglas para
entender los programas escritos en un lenguaje.
Elementos de un lenguaje
Estructura 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
Elementos de un lenguaje
NOTACION BNF
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>
Elementos de un lenguaje
NOTACION BNF
Sean las 4 reglas siguientes parte de la gramática de un
lenguaje de programación.
<entero> ::= <digito> | <digito> <entero>
<identificador> ::= <letra> | <identificador> <digito> | <identificador> <letra>
<parametros> ::= ( <lista_id> )
<lista_id> ::= <identificador> | <identificador> , <lista_id>
Elementos de un lenguaje
NOTACION 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 como div.
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
Elementos de un lenguaje
NOTACIÓN EN ESQUEMA DE SINTAXIS
Se construye un subesquema para cada símbolo no terminal.
Expresión
Termino
+
Termino
-
Termino
Factor
*
Factor
div
Factor
(
Termino
Variable
Constante
)
Elementos 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.
Elementos de un lenguaje
Diagrama de Conway
Entero
Digito
Identificador
Letra
Letra
Digito
Elementos 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
compilador
fuente
programa
objeto
mensajes
de error
Compiladores e interpretes
HISTORIA
Computadora
Persona
Código
Máquina
Ensamblador
Código
Máquina
Ensamblador
Código
Máquina
Lenguaje
Ensamblador
Compilador
Lenguaje
Lenguaje de
Ensamblador
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 PARA PROCESAMIENTO DE UN LENGUAJE
estructura del programa fuente
preprocesador
programa fuente
compilador
programa objeto en lenguaje ensamblador
ensamblador
código de máquina relocalizable
editor de carga y enlace
biblioteca
archivos obj.relocal.
código de máquina absoluto
Compiladores e interpretes
PARTES DE LA COMPILACIÓN
• ANÁLISIS (Etapa Inicial):
Divide al PF 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 PO 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
Analizador lexicográfico
Semana 1
Temas
Introducción a la teoría de lenguajes. Evolución de los lenguajes de
programación. Categorías de los lenguajes. Elementos de un lenguaje de
programación. Compiladores e intérpretes.