lunes, 29 de mayo de 2017

Tabla de Símbolos

DEFINICIÓN DE LAS TABLA DE SÍMBOLOS.
Una tabla de símbolos es una estructura de datos usada en el proceso de traducción de un lenguaje de programación (por un compilador o un intérprete), dónde cada símbolo en el código fuente de un programa está asociado con información tal como la ubicación, el tipo de datos y el ámbito de cada variable, constante o procedimiento.
Esta estructura de datos contiene una entrada o registro para cada identificador. Cada registro incluye los campos para los atributos del identificador. El administrador de la tabla de símbolos se encarga de manejar los accesos a la tabla de símbolos, en cada una de las etapas de compilación de un programa.
Se examina la tabla de símbolos cada vez que se encuentra un nombre en el texto fuente. Si dicho nombre ya existiese, se realizan cambios sobre la tabla existente. Un mecanismo de tabla de símbolos debe permitir añadir entradas nuevas y encontrar entradas existentes de manera eficaz.
La tabla de símbolos se construye durante el proceso de análisis. La información en la tabla de símbolos se utiliza tanto en el análisis (para especificar restricciones contextuales) como en la síntesis/traducción (para interpretar/traducir el significado de los tokens).
La información se reúne en las fases de análisis del compilador y la emplea la fase de síntesis para generar el código objeto. Por ejemplo, durante el análisis léxico, la cadena de caracteres, o lexema, que forma un identificador se guarda en una entrada de la tabla de símbolos. Las fases posteriores del compilador pueden añadir a esta entrada información, como el tipo del identificador, su uso (por ejemplo, procedimiento, variable o etiqueta) y su posición en la memoria. La fase de generación de código usaría después esta información para generar el código apropiado para almacenar y acceder a esta variable.
 ESTRUCTURA
Cada entrada de la tabla de símbolos corresponde a al declaración de un nombre. El formato de las entradas no tiene que ser uniforme porque la información de un nombre depende del uso de dicho nombre. Cada entrada en principio puede considerarse:
( Nombre, descriptor )
LEXEMA ATRIBUTOS
· LEXEMA: distintas políticas de almacenamiento.
· ATRIBUTOS: cuanta información contiene dicho campo depende del objeto que denota el lexema.
La estructura inicial de la tabla de símbolos suele constar de dos partes:
· PARTE FIJA: formada por las palabras clave del lenguaje (suelen ser de uso reservado y del orden de unas decenas de palabras en un lenguaje programación típico)
· PARTE VARIABLE: definida por el programador: con el significado de los identificadores utilizados en cada frase (programa).
La información se introduce en la tabla de símbolos a la vez. Las palabras claves se introducen al inicio, o bien también podrían iniciarse en una tabla separada. El analizador léxico busca secuencia de letras y dígitos en la tabla de símbolos para determinar si se ha encontrado una palabra clave reservada o un nombre, este es el motivo por el que las palabras reservadas deben estar en la tabla de símbolos antes de que comience el análisis.
Si se da el caso que el analizador léxico reconoce las palabras clave reservadas, entonces no necesitan aparecer en la tabla de símbolos puede tratarse como una estructura transitoria o volátil, que sea utilizada únicamente en el proceso de traducción de un lenguaje de programación, para luego ser descartada, o integrada en la salida del proceso de compilación para una explotación posterior, como puede ser por ejemplo, durante una sesión de depuración, o como recurso para obtener un informe de diagnóstico durante o después la ejecución de un programa.
La construcción de la tabla de símbolos debe seguirse de una correcta especificación de la misma. Como la definición de la parte dinámica de la tabla de símbolos está basada en las restricciones del lenguaje de programación, la especificación de la construcción de la tabla de símbolos está dirigida por la sintaxis de este sub-lenguaje de declaración y utiliza las mismas técnicas utilizadas para especificar y construir otros elementos del procesador de lenguaje (La construcción de la tabla de símbolos es una tarea del módulo de análisis sintáctico en la que coopera inicialmente el módulo de análisis léxico).

ANALIZADOR LÉXICO

            El ANALIZADOR LÉXICO

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;


Conceptos Analizador Léxico

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. 

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.

lunes, 8 de mayo de 2017

DIFERENCIA ENTRE ATRIBUTOS HEREDADOS Y ATRIBUTOS SINTETIZADOS

Atributos Sintetizados


 Se puede decir que un atributo es sintetizado si su valor en un nodo del árbol de análisis sintáctico se determina a partir de los valores de atributos de los hijos de ese nodo (como decir de abajo hacia arriba). Se pueden calcular mediante un solo recorrido ascendente del árbol de análisis sintáctico, lo que es muy deseable.



  • Los atributos sintetizados se utilizan ampliamente.
  • Si una definición dirigida por sintaxis tiene únicamente atributos sintetizados se dice que es S-atribuida.
  • El árbol de análisis sintáctico de una gramática S-atribuida puede decorarse mediante un recorrido en post orden.


Atributos Heredados

  • Sirven para expresar la dependencia que hay entre una construcción del lenguaje de programación y su contexto.
  • Siempre es posible reescribir una definición dirigida por sintaxis para que sea S-atribuida.
  • En ocasiones es más natural utilizar atributos heredados