Clase 8 - Ejemplo de Analizador Lexixo-Sintantico

EJEMPLO DE ANALIZADOR LEXICO-SINTACTICO MINI-DEV

El analizador sintáctico (ASN) comprueba que el orden en que el analizador léxico le va entregando los tokens es válido. Si esto es así significará que la sucesión de símbolos que representan dichos tokens puede ser generada por la gramática correspondiente al lenguaje del código fuente.

La forma más habitual de representar la sintaxis de un programa es el árbol de análisis sintáctico, y lo que hacen los analizadores sintácticos es construir una derivación por la izquierda o por la derecha del programa fuente, que en realidad son dos recorridos determinados del árbol de análisis sintáctico. 

PROTOTIPO DE UN ANALIZADOR LEXICO

Analizador Léxico (Lexico.h)

Analizador Sintáctico (Sintactico.h)

Programa Principal (Lexico.cpp)

Programa Principal (Sintactico.cpp)

Clase 7 - Analisis Sintactico

Análisis Sintáctico

Analisis Sintactico: Determina  la  sintaxis,  o  estructura  de  un programa. Es un análisis a nivel de sentencias, y es mucho más complejo que el análisis léxico.

Su función es tomar  el  programa  fuente  en  forma  de  tokens,  que  recibe  del analizador  léxico,  y  determinar  la  estructura  de  las sentencias del programa.

Este proceso es similar a determinar la estructura de una frase

Análisis Sintáctico – Proceso

       

Código fuente

Analizador léxico o rasterador

Tokens

Analizador Sintáctico

Árbol sintáctico

Analizador Semántico

Árbol con anotaciones

Optimizador de código fuente

Código intermedio

 Generador de código

Código objetivo

Optimizador de código objetivo

Código Objetivo

La tarea del AS es determinar la estructura sintáctica  de  un  programa  a  partir  de  los tokens producidos por el AL.

En  resumen  una  función  que  toma  como entrada la secuencia de tokens y salida el AS.

Secuencia de tokens <> árbol sintáctico

El árbol se define como estructura de datos dinámica,  nodos,  atributos,  campos  del atributo.

Manejo  de  errores,  no  solo  mostrar mensaje  sino recuperarse (inferir  código corregido)  y  continuar  el  análisis,  para encontrar tantos errores como sea posible.

Al proceso de reconocer la estructura del lenguaje fuente se conoce  con  el  nombre  de  análisis  sintáctico  (parsing). 

Hay distintas clases de analizadores o reconocedores sintácticos, pero  en  general  se  clasifican  en  2  grandes  grupos: 

A.S. Ascendentes y A.S. Descendentes.

Tipos de Análisis Sintácticos

Análisis descendente:

Partimos de la raíz del árbol (donde estará situado el símbolo inicial de la gramática) y se van aplicando reglas por la izquierda de forma que se obtiene una derivación por la izquierda de la cadena de entrada.

Para decidir qué regla  aplicar, se lee un token de la entrada.

Análisis ascendente:

Partiendo de la cadena de entrada, se construye el árbol de análisis sintáctico empezando por las hojas (donde están los tokens) y se van creando nodos intermedios hasta llegar a la raíz (hasta el símbolo inicial), construyendo así el árbol de abajo a arriba.

El recorrido del árbol se hará desde las hojas hasta la raíz.

Función principal

Comprueba  que  el orden en que el analizador léxico le va entregando los tokens es  válido.  Si  esto  es  así  significará  que  la  sucesión  de símbolos que representan dichos tokens puede ser generada por la gramática correspondiente al lenguaje del código fuente.

Clase 6 - Analisis Lexico

Análisis Lexixo y Diagramas de Transición

Fases de un compilador:

Analisis Lexico: Está constituido por todas las palabras y símbolos que lo componen. Para un lenguaje de programación la definición también es válida.

Lo constituyen todos los elementos individuales del lenguaje, denominados frecuentemente en inglés tokens.

Token

Así son tokens: las palabras reservadas del lenguaje, los símbolos que denotan los distintos tipos de operadores, identificadores (de variables, de funciones, de procedimientos, de tipos, etc.), separadores de sentencias y otros.

Token 

◦ Elemento léxico del lenguaje 

◦ Símbolo No Terminal de las fases siguientes 

Patrón 

◦ Expresión regular que define el lenguaje 

◦ Letra (Letra | Digito)

Lexema 

◦ Secuencia de caracteres que concuerda con un patrón 

◦ Numero, caracter. 

Atributos 

◦ Estructura de datos de cada token para almacenarse en la TS 

◦ Depende del tipo de token ◦ [ID, Lexema, Tipo, Valor, línea]

Un programa fuente es una serie de símbolos que representan las construcciones del lenguaje tales como variables, etiquetas, palabras reservadas, constantes, operadores, entre otros. 

El programa fuente se trata inicialmente con el analizador léxico.

Pasos del Análisis Lexico:

Identificar la colección de tokens 

Estructurar la colección de tokens

Describir el lenguaje como expresiones regulares

Ejemplo:

El análisis léxico es un análisis a nivel de caracteres, su misión es reconocer los componentes léxicos o tokens, enviando al analizador sintáctico.

Funciones:

Tratar con la tabla de símbolos 

Generar tokens bajo demanda del analizador sintáctico

Manejar el fichero fuente

Ignorar comentarios 

Contabilizar posición de tokens

Preprocesar macros, constantes, includes…

Clase 5 - Test

A continuación se presenta un pequeño test acerca de los compiladores e interpretes, contestar de acuerdo a los conocimientos adquiridos.

Clase 4 - Tabla de Simbolos

Tabla de Símbolos

¿Qué es la tabla de simbolos?

Almacena todos los nombres declarados en el programa y sus atributos (tipo, valor, dirección, parámetros, etc.).

Se usa en las distintas fases del compilador.

Estructura de datos.

Almacena información sobre:

Los identificadores.

Las palabras reservadas.

Las constantes.

Contiene una entrada para cada uno de los símbolos definidos en el programa fuente.

Sobre los identificadores, y opcionalmente sobre las palabras reservadas y las constantes.

Información sobre el lexema, tipo de datos, ámbito y dirección en memoria.

Por cada entrada en la tabla de símbolos habrá que guardar:

Lexema correspondiente.

Tipo.(depende de la implementación).

Ámbito.(depende de la implementación).

Dirección de memoria asignada.

Forma.(depende de la implementación).

¿Utilidad de la tabla de símbolos?

·  Analizador Léxico: Pasa en el token y la entrada de la TS creada.

·    Analizador Sintáctico y Semántico: busca el token y si no la encuentra crea una nueva entrada.

Operaciones Principales.

Insertar: introduce un símbolo tras una declaración.

Buscar: recupera información asociada a un símbolo.

Eliminar: borra la información.

Ejemplo de Uso I.

Declaración previa al uso de variables:

·         En las declaraciones, inserción en la TS.

Aparición de una variable en una sentencia, búsqueda en la TS:

·         Si se encuentra Fue declarada.

·         Si no se encuentra Error de compilación.

Ejemplos de Uso II.

Acceso a una posición de un array:

·         Declaración > Inserción en la TS.

·         Acceso a un array > Búsqueda en la TS.

1. Comprobación de tipo array.
2. Comprobación acceso a una posición válida.

Ejemplo:

Estructuras usadas para implementar una tabla de símbolos.

Lista

1. Simple de implementar.
2. Lenta cuando se trabaja con muchos identificadores.

Árbol

1. Rápida.
2. Consume más memoria.
3. Es útil cuando hay muchas declaraciones.

Tabla de Hashing

1. Rápida.
2. Difícil de implementar.
3. Se debe definir una función de hashing apropiada para evitar colisiones.

Manejo de palabras claves

Si el scanner diferencia entre un identificador y una palabra reservada, entonces devuelve al parser el código correspondiente. Aquí no se requiere el ingreso de la palabra clave en la TS.

Entradas en la TS

Una primera desagregación de una entrada de la tabla de símbolos:

Parte Fija:

Parte Variante:

Procedimiento o Función:

Operaciones sobre TS: Lenguajes Estructurados a Bloques.

Cuando se busque un identificador en la TS se debe retornar el último identificador insertado, es decir, el identificador declarado en el bloque actual, si en tal bloque no existe el identificador buscarlo en el bloque que lo contenga, y así sigue hasta encontrarlo. Si el identificador no se encuentra en ninguno de los bloques anidados entonces no existe.

Ejemplo:

Clase 3

INTRODUCION, CONCEPTOS, CARACTERISTICAS Y COMPONENTES DE LOS COMPILADORES

CLASIFICACI

ON DE LOS LENGUAJES DE PROGRAMACION

La programación de computadoras se realiza en los llamados lenguajes de programación, éstos posibilitan la comunicación entre el programador y la computadora, a través de un conjunto de instrucciones u órdenes especificadas por el lenguaje. Un lenguaje de programación puede definirse como: “Notación formal para describir algoritmos o funciones que serán ejecutados por una computadora”, o bien, un lenguaje para comunicar instrucciones al computador. 

Diferentes puntos de vista para clasificar los lenguajes de programación: 

1. Su grado de independencia con la máquina.
a) Lenguaje máquina (representación binaria o hexadecimal.): El lenguaje de máquina de una computadora consta de cadenas de números binarios (ceros y unos) y es el único que "entienden" directamente los procesadores. 

b) Lenguaje ensamblador o de bajo nivel (versión simbólica de un lenguaje máquina): La comunicación en lenguaje de máquina es particular de cada procesador que se usa, y programar en este lenguaje es muy difícil y tedioso, por lo que se empezó a buscar mejores medios de comunicación con ésta. 

c) Lenguaje de medio nivel (lenguaje C).
  
d) Lenguaje de alto nivel (FORTRAN, COBOL, Pascal): Los primeros programas ensambladores producían sólo una instrucción en lenguaje de máquina por cada instrucción del programa fuente. Para agilizar la codificación, se desarrollaron programas ensambladores que podían producir una cantidad variable de instrucciones en lenguaje de máquina por cada instrucción del programa fuente. Dicho de otra manera, una sola macroinstrucción podía producir varias líneas de código en lenguaje de máquina.

2. La forma de sus instrucciones y la forma de procesar el código fuente:

A) Lenguajes imperativos o procedimentales.
B)Lenguajes declarativos, funcionales o aplicativos.
C)Lenguajes orientados a objetos.

3. Por generaciones:

 Traductores (translators): Un traductor es un programa que procesa un texto fuente destino. 

 Compiladores (compilers): Un traductor que transforma textos fuente de lenguajes de alto nivel a lenguajes de bajo nivel se le denomina compilador. 

 Ensambladores (assemblers). 

 Interpretes (interpreters): Los intérpretes son programasque simplemente ejecutan las instrucciones que encuentran en el texto fuente. En muchos casos coexisten en memoria el programa fuente y el programa intérprete.

 Editores (editors).

               ARQUITECTURA DE LA COMPUTADORA 

En la disciplina de los procesadores de lenguajes, los compiladores son los más utilizados por los programadores para el desarrollo de aplicaciones. En el caso particular del desarrollo de compiladores, hay que tener bien definida la arquitectura de la computadora. 

¿Cómo se pueden ejecutar las aplicaciones desarrolladas para otras arquitecturas de computadoras en la nueva arquitectura? 

El problema planteado anteriormente no sólo es aplicable a la construcción de nuevas arquitecturas, sino también cuando es necesaria la compatibilidad de aplicaciones entre diferentes sistemas operativos y arquitecturas de computadoras.

Un intérprete software o emulador de software es un programa en código binario que lee una a una las instrucciones binarias de la arquitectura antigua de las computadoras, que se encuentran en un fichero ejecutable, y las interpreta. Los intérpretes no son muy rápidos, pero pueden construir y adaptar a distintas arquitecturas sin excesivos costos de desarrollo. 

Un emulador hardware trabaja de forma similar a un intérprete de software, pero está implementado en HW de forma que decodifica las instrucciones de la arquitectura antigua y las traduce a la nueva arquitectura.

Un traductor entre códigos binarios o ensambladores son conjuntos de instrucciones de la nueva arquitectura que reproducen el comportamiento de un programa en la arquitectura antigua (la información de la máquina antigua se almacena en registros de la nueva máquina).

Un compilador nativo es aquél que toma un programa fuente antiguo y lo vuelve a compilar (recompilar) con compiladores desarrollados para la nueva arquitectura.

GRAMATICAS DE LOS LENGUAJES DE PROGRAMACION 

FASES DE LOS COMPILADORES 

Fase de Análisis: 

En el llamado análisis lexicográfico o léxico, el compilador revisa y controla que las "palabras" estén bien escritas y pertenezcan a algún tipo de token (cadena) definido dentro del lenguaje, como por ejemplo que sea algún tipo de palabra reservada, o si es el nombre de una variable que este escrita de acuerdo a las pautas de definición del lenguaje.

En el análisis sintáctico como su nombre lo indica se encarga de revisar que los tokens estén ubicados y agrupados de acuerdo a la definición del lenguaje. Dicho de otra manera, que los tokens pertenezcan a frases gramaticales validas, que el compilador utiliza para sintetizar la salida.

El análisis semántico se encarga de revisar que cada agrupación o conjunto de token tenga sentido, y no sea un absurdo. 

Fase de Síntesis: 

Etapa de generación de código intermedio, aunque algunos compiladores no la tienen, es bueno saber de su existencia, en esta etapa se lleva el código del programa fuente a un código interno para poder trabajar más fácilmente sobre él.

En la etapa de optimización de código, se busca obtener el código más corto y rápido posible, utilizando distintos algoritmos de optimización. 

Etapa de generación de código, se lleva el código intermedio final a código maquina o código objeto, que por lo general consiste en un código maquina re localizable o código ensamblador.

La tabla de símbolos no es una etapa del proceso de compilación, sino que una tarea, una función que debe realizar el proceso de compilación.