Clase 6 - ALexicoyDT

Clase 6:

CONCEPTOS GENERALES SOBRE ANALISIS LEXICO

             

OBJETIVO

1.     Token 2.     Patrón 3.     Lexema 4.     Atributo 5.     Gramática 6.     Alfabeto 7.     Símbolo

9.     Diagrama y Tabla de Transición 10.  Autómata 11.  Autómata Finito 12.  Autómata Finito Determinista 13.  Autómata Finito No Determinista 14.  Autómata de Pila 15.  Autómata de Turing

8. Expresión Regular

¿QUÉ ENTENDEMOS POR LEXICO?

El léxico de un lenguaje natural 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.

En un lenguaje de programación el léxico lo constituyen todos los elementos individuales del lenguaje, denominados frecuentemente en inglés tokens. 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.

¿QUÉ ENTENDEMOS POR SINTAXIS?

En lingüística, sintaxis es el estudio de la función que desempeña cada palabra en el entorno de una frase. Mientras que semántica es el estudio del significado de una palabra tanto a nivel individual como en el contexto de una frase.

En los lenguajes de programación, sintaxis es un conjunto de reglas formales que especifican la composición de los programas a base de letras, dígitos y otros caracteres. Por ejemplo, las reglas de sintaxis especifican en C/C++ que cada sentencia o línea de programa debe terminar con un

Por: Ing. Marvin Parada, Compiladores Ciclo I-2016 Página 1

“;”, o que la declaración de tipos debe ir antes que la de variables. (int var;)

¿QUÉ ENTENDEMOS POR SEMANTICA?

Semántica en los lenguajes de programación es el conjunto de reglas que especifican el significado de cualquier sentencia, sintácticamente correcta y escrita en un determinado lenguaje. Por ejemplo en el lenguaje Pascal la sentencia: suma:= 27/lado Es sintácticamente correcta, ya que a la izquierda del símbolo de asignación hay un identificador, y a la derecha una expresión. 

Pero para que sea semánticamente correcta hay que comprobar:

a) Lado debe ser compatible con el operador “/” y con el operando 27.

b) Suma debe ser un tipo compatible con el resultado de la operación.

El ANALIZADOR LEXICO

Un programa fuente es una serie de símbolos (letras, símbolos, caracteres especiales: +, *, !). Con estos símbolos se representan las construcciones del lenguaje tales como variables, etiquetas, palabras reservadas, constantes, etc. Es necesario que el compilador o traductor identifique los distintos significados de estas construcciones, que los creadores de lenguajes dan en la definición del lenguaje.

El programa fuente se trata inicialmente con el analizador léxico (en inglés scanner), con el propósito de agrupar el texto en grupos de caracteres con significado propio llamados tokens o componentes léxicos, tales como variables, identificadores, palabras reservadas y operadores. Por razones de eficiencia a cada token se le asocia un atributo (o más de uno) que se representa internamente por un código numérico o por un tipo enumerado.

Por ejemplo considerar la siguiente sentencia es C/C++: 

if sueldo == 1000 sueldo * 0.25;

El analizador léxico la separa en la siguiente secuencia de tokens:

CONCEPTOS ANALIZADOR LEXICO

Token

Es el nombre que se le da a cada patrón definido, éste nombre debe usarse en todos los procesos del análisis en todos los lexemas encontrados.

Patrón

Es una representación lógica de una serie de agrupaciones de caracteres con características comunes.

Lexema

Es cada una de las combinaciones de caracteres que encajan en la definición de un patrón o token. Ej. Variable1, x, a, edad, y2, etc.

Atributo

Características propias de cada token, por tanto se les denomina atributos del token.

Gramática

Se define como un ente formal para especificar de una manera finita el conjunto de cadenas de símbolos que constituyen un lenguaje.

Alfabeto

Conjunto finito de símbolos no vacío que conforman una gramática, se representan por ∑ (sigma).

Símbolo

Entidad abstracta que no se va a definir pues se deja como axioma. Normalmente son letras de alfabetos, números o caracteres especiales como +, -, *, /, etc. No necesariamente serán uno solo, ya que un símbolo puede ser una combinación como palabras reservadas de un lenguaje de programación then, end, beging, else, while, etc.

Expresión Regular

Representan patrones de cadenas de caracteres. Se conocen más como metalenguajes que sirven para describir los lenguajes regulares.

Diagrama de Transición

Es el conjunto de secuencias de entrada que representan gráficamente los símbolos validos por la gramática, es una representación de los universales autómatas que aparecen en la matemática y otras ciencias.

Tabla de Transiciones

Es la manera más cercana de representar los autómatas, consta de filas que representan los estados y las columnas que representan los símbolos de entrada. Adicionalmente se agregan dos columnas para representar los tokens y para indicar retrocesos.

Cadena

Se define como una secuencia de símbolos de un lenguaje determinado. Por ejemplo 0001, abcd, a+4*b, 11000, etc. Una cadena siempre tiene una longitud que esta denotada por la cantidad de símbolos independientes que la conforman. 

|abcde| →5

|000111| →6

Cuando la cadena es vacía se representa como |λ|→0.

Lenguaje

Un lenguaje es un conjunto de palabras que se puede representar con un determinado alfabeto.

Autómata

Es una construcción lógica que recibe como entrada una cadena de símbolos y produce una salida indicando si la salida es una cadena que pertenece a un determinado lenguaje.

EJEMPLO DE ANALIZADOR LEXICO USANDO DEV C++

MiniUGB

             

OBJETIVOS

 Estudiar el código fuente de un programa prototipo de análisis léxico.

 Aplicar el análisis léxico utilizando código en lenguaje C++ creado con Dev C++

PROTOTIPO DE UN ANALIZADOR LEXICO

Suponga que se desea construir una mini simulación de un compilador, tomando en cuenta nada más el análisis léxico de un programa. El programa fuente será un código escrito en un lenguaje definido por el usuario (podemos llamarlo MiniUGB). En este caso el código ha sido escrito en lenguaje C++ y se debe trabajar con el programa Dev C++ v5.0

Generalmente un compilador toma el programa fuente, lo interpreta y crea un programa objeto (normalmente en lenguaje máquina). Por ahora nos limitaremos a comprender y analizar una de las formas, de cómo se llevaría a cabo un analizador léxico según las características de un lenguaje.

La definición de los componentes léxicos del lenguaje MiniUGB es la siguiente:

 Identificadores, que sólo son nombres de variables y están compuestos por una única letra minúscula de rango de a – z.

 Constantes: numéricas utilizando dígitos en el rango 0 – 9. 

 Operadores: +, -, *, / y %.

 Símbolo: asignación :=, paréntesis (  ), separador de sentencias punto y coma, indicadores de principio y fin de bloque {  }.

 Palabras reservadas que están formadas por una letra mayúscula, las cuales son: R (lectura), W (escritura) y M (programa principal).

Observe que en este lenguaje, todos los tokens son de un sólo carácter. Además se considera que se tiene un solo tipo de dato: entero, y que las variables están formadas por una única letra minúscula, y las constantes son de un dígito. Se asume que para identificar la sintaxis de cada sentencia, se conoce que reglas de programa se han de seguir, con solo conocer el token por el que comienza la sentencia.

Programa de ejemplo escrito con código fuente reconocido por el lenguaje MiniUGB.

Conociendo la gramática del lenguaje definido, realice la descripción de lo que realiza cada

una de las líneas escritas en el programa.

1.    _________________________________________

2.    _________________________________________

3.    _________________________________________

4.    _________________________________________

5.    _________________________________________

6.    _________________________________________

7.    _________________________________________

El análisis léxico debe separar el fichero fuente en componentes léxicos o tokens, y enviarlos al analizador sintáctico (en este guía no se detallara el analizador sintáctico).

Habitualmente se envían los componentes léxicos y sus atributos. En este caso solo se enviaran los tokens, ya que el atributo va implícito en el token (tan sólo se tiene el tipo de dato entero).

A continuación se muestra la definición de clase Léxico, la cual contiene las funciones necesarias para poder implementar un análisis léxico adecuado para el lenguaje DEVC.

#include<iostream>

#include<stdio.h>

#include<ctype.h>

#include<stdlib.h>

#include<string>

#define TAM_BUFFER 100

using namespace std;

class Lexico {     char *nombreFichero;     FILE* entrada;     int n1;     int traza;     char buffer[TAM_BUFFER];     int pBuffer;     public:

    Lexico(char *unNombreFichero, int una_traza=0);

    ~Lexico(void);     char siguienteToken(void);     void devuelveToken(char toke);     int lineaActual(void){return n1; };

    int existeTraza(void){if(traza)return 1; else return 0;}

};

Lexico::Lexico(char *unNombreFichero, int una_traza)

{

    entrada=fopen(unNombreFichero, "rt");     if((entrada==NULL))

    {

        cout<<"No se puede abrir el archivo"<<endl;         system("pause");         exit(-2);

    }

        if(una_traza) traza=1;         else traza = 0;         n1=1;         pBuffer=0;

}

Lexico::~Lexico()

{

    fclose(entrada);

    }

    char Lexico::siguienteToken(void)

    {     char car;

    while((car=((pBuffer>0) ? buffer[--pBuffer]:getc(entrada)))!=EOF)

    {

    if(car==' ') continue;     if(car=='\n'){++n1; continue;}     break;     }

    if(traza) cout<<"ANALIZADOR LEXICO: Lee el token : "<<car<<endl;     switch(car)     {     case'M':     case'R':     case'W':

    case'=':     case'(':     case')':     case';':     case'}':     case'{':     case'.':     case'+':     case'*':     case'-':     case'/':     case'%':     return(car);

    }

    if(islower(car))return(car);     else if(isdigit(car)) return(car);     else     {

    cout<<"Error Lexico: Token Desconocido"<<endl;     system("pause");     exit(-4);     }

    return(car);

} 

void Lexico::devuelveToken(char token)

{

    if(pBuffer>TAM_BUFFER)

    {

    cout<<"ERROR: Desbordamiento del buffer del analizador lexico"<<endl;     system("pause");     exit(-5);     }     else     {

    buffer[pBuffer++]=token;     if(existeTraza())

    cout<<"ANALIZADOR LEXICO: Recibe en buffer el token"<<token<<endl;     system("pause");

}

} 

Programa Principal

A continuación se muestra un pequeño programa para observar como es realizado el proceso de análisis léxico por la clase. (SI Ud. desea puede implementar otro tipo de proceso dentro de main).

int main()

{ int traza; char token;

Lexico obj("ejemplo_minidev.txt",1); if(obj.existeTraza()) cout<<"INICIO DE ANALISIS"<<endl; while((token=obj.siguienteToken() )!='}') cout<<token<<endl; system("pause"); return 0;

}  

Ejercicio 2

Describa lo que hace el programa anterior:

_________________________________________________


Análisis Léxico y diagramas de transición

Objetivos

• Conocer el funcionamiento del analizador léxico
• Comprender su relación con la tabla de símbolos.
• Entender como interviene la generación de errores a partir de ésta etapa.
• Aprender a especificar un analizador léxico.
• Realizar diagramas y tablas de transición.

Fases de un compilador

Análisis Léxico

• 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.