jueves, 15 de noviembre de 2007

Expresiones y declaraciones.

4.1 Sentencias Declarativas

En los lenguajes naturales hay cuatro principales clases de oración: imperativa, declarativa, interrogativa y exclamatoria. En una oración imperativa el sujeto de la oración es implícito. Una oración declarativa expresa un hecho y pude consistir de un sujeto y un verbo o sujeto, verbo y objeto. En algunos lenguajes de programación, los constructor básicos son oraciones imperativas por ejemplo una asignación x=5. Los lenguajes de programación también incluyen constructores declarativos como la declaración de una función que plantea un hecho: function f(int x) {return x+1}; una lectura como oración declarativa es que el sujeto es el nombre f y la oración acerca de f es una función que regresa un valor más al de su argumento. En programación la distinción entre un constructor imperativo y declarativo se encuentra en la distinción entre cambiar un valor existente y declarar un nuevo valor. Consideremos el siguiente fragmento de un programa:

{ int x=1; /* declara una nueva x */
x = x+1; /* asignación a una x existente */
{ int y = x+1; /* declara una nueva y */
{ int x = y+1; /* declara una nueva x */
}}}

De aquí la segunda línea es una oración imperativa, que cambia el estado de la máquina por almacenar el valor de 2 en la posición asociada con la variable x.

Una declaración es un constructor que será elaborado para producir ligaduras. Todas las declaraciones producen ligaduras, algunas con efectos como crear variables. Se usa el término definición para una declaración de quién solo el efecto es producir ligaduras.

Cada lenguaje de programación tiene varias formas de simples declaraciones cubriendo todas las entidades que están ligadas al lenguaje. Casi todos los lenguajes soportan las siguientes:

Declaraciones de tipo
Declaración de constantes
Declaración de variables
Definiciones de de procedimiento

Las declaraciones pueden estar compuestas de declaraciones más simples:

Declaraciones colaterales. Compone declaraciones que están para ser elaboradas independientemente una de otra. Estas subdeclaraciones pueden no utilizar ligaduras producidas por cada una. La declaración colateral fusiona las ligaduras producidas por sus subdeclaraciones. No son comunes en lenguajes imperativos y orientados a objetos, pero si lo son en lenguajes funcionales y lógicos.


Declaraciones secuenciales. Compone declaraciones que están para ser elaboradas una después de otra. Cada subdeclaración puede usar la ligadura previa producida por cualquier subdeclaración, pero no las producidas por cualquiera de las siguientes subdeclaraciones. La declaración secuencial fusiona las ligaduras producidas por sus subdeclaraciones. Las declaraciones secuenciales son soportadas por la mayoría de los lenguajes imperativos y orientados a objetos.


Declaraciones recursivas. Usa las ligaduras que produce por sí misma. Como un constructor es importante, porque nos permite tipos recursivos y procedimientos.

Las ligaduras pueden determinarse mediante una declaración ya sea de manera implícita o de manera explícita. La asignación anterior de x=5 establece explícitamente el tipo de datos utilizado en x, utilizando la palabra clave int, pero la localización exacta de x durante la ejecución está únicamente vinculada de manera implícita y de hecho podría ser estática o dinámica, dependiendo de la localización de esta declaración dentro del programa. De manera similar, el valor de x es implícitamente cero o no queda definido, dependiendo de la localización de la declaración.

Las ligaduras no solamente pueden ser implícitas en una declaración, sino que la declaración completa misma puede ser implícita. Por ejemplo, en algunos lenguajes, la simple utilización del nombre de la variable hace que se declare.

Una expresión de bloque, es una forma de expresión que contiene una declaración local (o grupo de declaraciones) seguidas por una secuencia de enunciados, y rodeado por marcadores sintácticos como son las llaves o pares de inicio-terminación.

Las declaraciones asociadas con un bloque específico también se conocen como locales, mientras que las que están afuera son globales.

Otros constructores del lenguaje, además de los bloques, son fuentes importantes de declaraciones: todos los tipos de datos estructurados se definen utilizando declaraciones locales asociados con el tipo.








4.2.1 SINTAXIS Y SEMANTICA.

1. INTRODUCCION.

Definición de Sintaxis.
La sintaxis de un lenguaje de programación es comparable con la gramática de un lenguaje natural. Es decir, que es la descripción de las maneras en que las diferentes partes de un lenguaje pueden ser combinadas para formar otras partes. Como por ejemplo; la sintaxis del enunciado if en C se puede describir en palabras como sigue:

Un enunciado if está formado de la palabra “if” seguida de una expresión entre paréntesis, de un enunciado, de una parte else opcional que consiste en la palabra “else” y de otro enunciado.

La descripción de sintaxis del lenguaje es una de las áreas donde las definiciones formales han tenido aceptación, y la sintaxis de casi todos los lenguajes está dada ahora utilizando gramáticas libres de contexto. Por ejemplo, una regla de gramática libre de contexto para el enunciado if de C se puede escribir de la siguiente forma:

::= if ()
[else ]

O utilizando caracteres y un formato especial):

Enunciado if ® if (expresión) enunciado
[else enunciado]

Un problema relacionado con la sintaxis de un lenguaje de programación es su “estructura léxica”, esto es similar a la ortografía en un lenguaje natural. L estructura léxica de un lenguaje de programación es la estructura de las palabras del lenguaje, que se conocen comúnmente como “tokens”. En el ejemplo anterior, las palabras “if” y “else” son tokens. Otros tokens incluyen identificadores (o nombres), símbolos para operaciones como “+” y “<=” y símbolos especiales de puntuación como el punto y como y el punto. Definición de Semántica. La sintaxis representa sólo la estructura superficial de un lenguaje y por lo tanto es una pequeña parte de la definición de un lenguaje. La semántica se refiere al significado de un lenguaje, es mucho mas compleja y difícil de describir con precisión que la sintaxis. Esta dificultad se presenta en que “significado” se puede definir de varias formas, normalmente al describir el significado de una fracción de código se involucra algún tipo de descripción de los efectos de su ejecución, y no existe una manera en especial de hacer esto. Tomando en cuenta el ejemplo del enunciado “if” que tomamos en la parte de sintaxis, describimos su semántica de la siguiente forma: Un enunciado if es ejecutado, primero, evaluando su expresión, misma que debe tener tipo aritmético o apuntador, incluyendo todos los efectos colaterales, y si se compara diferente de 0, el enunciado que sigue a la expresión es ejecutado. Si existe una parte else, y la expresión es 0, el enunciado que sigue al “else” es ejecutado. En esta descripción se ven algunas de las dificultades en la especificación de la semántica, incluso para un enunciado tan sencillo como un “if”. La descripción no menciona lo que ocurre si la condición se evalúa igual a 0, sin existir una parte else, tampoco se dice si el enunciado if es “seguro”, en el sentido de que no existen otros mecanismos del lenguaje que pudieran permitir la ejecución de los enunciados dentro de este enunciado sin la evaluación correspondiente. Para lo anterior pueden ser necesarios mecanismos adicionales de protección para evitar una división entre 0. Una alternativa es el uso de un método formal, pero aquí no hay un método generalmente aceptado análogo al uso de las gramáticas libres de contexto para la sintaxis. Para lo anterior, se han desarrollado varios sistemas de notación para definiciones formales y su uso va aumentando y por lo tanto van dividiendo el estudio de la semántica dividiéndolo en: Semántica operacional. Semántica denotacional. Semántica axiomática. SINTAXIS.

2.1 Estructura léxica de los lenguajes de programación.


La estructura léxica de un lenguaje de programación es la estructura de sus palabras “tokens”. Esta estructura puede estudiarse por separado de la sintáctica pero están muy relacionadas y a veces puede que no se pueda separar de dicha estructura sintáctica, esto depende del lenguaje.

Generalmente la fase de análisis léxico de un traductor reúne en forma de tokens secuencias de caracteres del programa de entrada, que después se procesan mediante una fase de análisis sintáctico, y esto es lo que determina la estructura sintáctica.

Clasificación de tokens.

Palabras reservadas (reserved words). Son también llamadas palabras clave (keywords).

Literales o constantes. Son de 2 tipos: Numericas (42, 36, etc) y de Cadena (“hello”)

Símbolos especiales. Como ejemplo “;”, “<=”, “+”, etc. Identificadores (identifiers). Como x24, monthly_balance, o bien, putchar. También existen “Identificadores predefinidos” que son aquellos a los que se les ha dado una interpretación inicial para todos los programas en el lenguaje, pero que también pueden ser redefinidos (a veces conocidos como palabras clave). Uso del principio de la subcadena de mayor longitud. Es una regla estándar en la determinación de los tokens (conocida también como principio de “trozo máximo”), esto es, en cada punto se reúne en un solo token la cadena mas larga posible de caracteres. Delimitadores de token o espacio en blanco. Estos nos ayudan a que ciertos tokens queden separados y se aplica principalmente en la subcadena mas larga. El final de una línea o renglón de texto puede tener un significado doble. Puede ser un espacio en blanco y también puede significar el fin de una identidad estructural. También se puede utilizar la sangría. Los lenguajes pueden ser de 2 tipos: Formato libre: En donde el formato no tiene efecto sobre la estructura del programa. La mayoría de los lenguajes modernos son de formato libre, pero algunos tienen restricciones de formato. Formato fijo. En este todos los tokens deben presentarse en localizaciones preespecificadas por página. En la actualidad ya casi no hay lenguajes de este tipo de formato. 2.2 Gramáticas libres de contexto y BNF.

(1) oración ® frase-sustancia frase-verbal.
(2) Frase sustantiva ® artículo sustantivo.
(3) Artículo ® a the
(4) Sustantivo ® girl dog
(5) Frase verbal ® verbo frase-sustantiva
(6) Verbo ® sees pets

En inglés, las oraciones simples están formadas por un sustantivo y un verbo seguidos por un punto. Los números encerrados en paréntesis indican el número de regla que se emplea, y son llamadas “Reglas gramaticales”. Estas describen la estructura de los sustantivos, de los verbos y de otras subestructuras que aparecen en reglas anteriores. Cada una de ellas tiene un nombre en letra cursiva, seguida por una flecha y seguida por una secuencia de otros nombres y símbolos. Estas letras sirven para distinguir los nombres de las estructuras de las palabras reales, es decir, de los tokens que pudieran aparecer en el lenguaje.

El símbolo ® es un “metasímbolo” que sirve para separar el lado izquierdo del lado derecho de una regla. La barra vertical “” es también un metasímbolo y significa “o”, es decir, selección (este “o” este).

A veces un metasímbolo es un símbolo real en un lenguaje, porque lo que es recomendable entrecomillar el símbolo para distinguirlo del metasímbolo o, de lo contrario éste puede escribirse en un tipo de letra diferente. Otro metasímbolo son los paréntesis angulares.

Con todo lo anterior, podemos dar algunas definiciones:
Gramática Libre de Contexto.
Consiste en una serie de reglas gramaticales como se describen a continuación: las reglas están formadas de un lado izquierdo que es un solo nombre de estructura y a continuación el metasímbolo “®”, seguido de un lado derecho formado por una secuencia de elementos que pueden ser símbolos u otros nombres de estructura. Los nombres de las estructuras se conocen como no terminales, porque se subdividen en estructuras adicionales.

Las reglas gramaticales también se llaman “producciones”, esto es porque producen las cadenas del lenguaje utilizando derivaciones. Estas producciones presentan la forma Backus-Naur y utilizan solo los metasímbolos “®” y “” y a veces también se permiten paréntesis.

Características de una gramática libre de contexto.

Tiene un símbolo inicial (que es un no terminal) y es el símbolo con el que se inician todas las derivaciones.

2.3 Árboles de análisis sintáctico y árboles de sintaxis abstracta.

La sintaxis establece una estructura, no un significado. El significado de una oración (en este caso nos referiremos a un programa) tiene que estar relacionado con su sintaxis. En la sintaxis de una oración en inglés, una frase sustantiva se coloca primero y después es asociada con un sujeto, esto mismo ocurre en la gramática para las expresiones cuando se escribe:

exp ® exp. + exp.

El proceso de asignar la semántica de una construcción a su estructura sintáctica se conoce como “semántica dirigida por la sintaxis”, por ello se debe construir la sintaxis de manera que refleje en su mayor porcentaje la semántica que eventualmente le daremos.

El método estándar para utilizar la estructura sintáctica es mediante “árboles de análisis sintáctico”, pues este describe de manera gráfica el proceso de reemplazo dentro de una derivación.

Ejemplo: El árbol de análisis gramatical para la oración “la niña ve un perro”, es el siguiente:
Entonces, de manera similar, el árbol de análisis sintáctico hará el número 234 en la gramática de expresión es:










Un árbol de análisis gramatical está identificado por no terminales en los nodos interiores y por terminales en las hojas, y la estructura de un árbol de análisis sintáctico está totalmente especificada por las reglas gramaticales del lenguaje y por una derivación de una secuencia de terminales: las reglas gramaticales especifican la estructura de cada nodo interior y a su vez la derivación especifica cuál de los nodos interiores se está construyendo.

2.4 Ambigüedad, asociatividad y precedencia.

En este tema veremos que dos derivaciones diferentes pueden conducir al mismo árbol de análisis sintáctico o árbol sintáctico: en la derivación del ejemplo anterior podíamos elegir cualquier camino y se obtendría el mismo árbol sintáctico, pero en otras derivaciones si se pueden conducir a diferentes árboles de análisis gramatical.

Ejemplo:
Para construir 3 + 4 * 5 se puede utilizar la siguiente derivación:

expr Þ expr + expr
Þ expr + expr * expr
(reemplaza el segundo expr con expr * exp.)
Þ número + exp. * exp.

O la siguiente derivación:

expr Þ expr * expr
Þ expr + expr * expr
(reemplaza el segundo expr con expr + exp.)
Þ número + exp. * exp.


Y estas conducen a 2 árboles de análisis sintáctico distintos:


Y también 2 árboles abstractos distintos como los dados a continuación:

Árbol 1 Árbol 2

Cuando una gramática permite que haya 2 árboles diferentes, se dice que es “ambigua”

Las gramáticas ambiguas presentan dificultades pues no expresan una estructura clara, para esto resulta útil eliminar las ambigüedades mediante una “Regla para eliminar ambigüedades” para establecer una estructura correcta.

2.5 Técnicas y herramientas de análisis sintáctico.

Una gramática escrita en BNF, EBNF o en forma de diagrama sintáctico describe las cadenas de tokens que sintácticamente son aceptados en un lenguaje de programación. Entonces la gramática de manera implícita describe las acciones que debe ejecutar un analizador sintáctico para analizar correctamente una cadena de tokens y construir una derivación o un árbol de análisis sintáctico para la cadena.

La forma mas sencilla de un analizador sintáctico es un “reconocedor”, esto es, un programa que acepta o rechaza cadenas con base en si se trata o no de cadenas aceptadas en el lenguaje.

Ejemplos de analizadores sintácticos:

De desplazamiento – reducción.
De arriba – abajo.
Compiladores.
De descenso – recursivo.
Predictivo.

SEMÁNTICA.

3.1 Atributos, ligaduras y funciones semánticas.


Mecanismos fundamentales de abstracción en un lenguaje de programación:

Nombres: Que son identificadores para denotar entidades o constructores del lenguaje. Las variables, los procedimientos y las constantes pueden tener nombres asignados por el programador.

Localización y valor: Los valores son cualquier cantidad almacenable (entero, reales e incluso valores matriciales) Las localizaciones son lugares donde se pueden almacenar estos valores, son como las direcciones en la memoria de la computadora.

De ser necesario, podemos tomar a las localizaciones como numeradas por enteros iniciados desde 0 y que van hasta cierto número máximo de localización.

Atributo: Propiedades que determinan el significado de un nombre y está asociado al mismo.

Pueden clasificarse de acuerdo con el tiempo en que se está calculando y vinculando con un nombre durante el proceso de traducción/ejecución, a esto lo conocemos como tiempo de ligadura del atributo y se clasifican en 2 clases:

Ligadura estática: Toma lugar antes de la ejecución.
Ligadura dinámica: Ocurre durante la ejecución.

De acuerdo a dicha clasificación tenemos:

Atributos estáticos: Está vinculado estáticamente.
Atributos dinámicos: Está vinculado dinámicamente.

Los lenguajes funcionales tienen más ligaduras dinámicas que los lenguajes imperativos. Los tiempos de ligadura también pueden depender del traductor. Por ejemplo los intérpretes traducen y ejecutan el código en forma simultánea y por lo tanto, llevarán a cabo la mayoría de las ligaduras dinámicamente, en tanto que los compiladores llevarán a cabo muchas ligaduras de manera estática.

Tiempos de ligadura para los atributos de nombres:

Tiempo de definición de lenguaje.
Tiempo de implementación de lenguaje.
Tiempo de traducción (“tiempo de compilación”).
Tiempo de ligado.
Tiempo de carga.
Tiempo de ejecución (“run time”).

Los tiempos anteriores, a excepción del último, representan ligaduras estáticas.

El traductor debe conservar las ligaduras de manera que se en significados apropiados a los nombres durante la traducción y la ejecución. Un traductor hace lo anterior creando una estructura de datos para mantener la información.

Tabla de símbolos.
Es una función que expresa la ligadura de los atributos a los nombres y es parte fundamental de la semántica del lenguaje. Matemáticamente es una función de nombres hacia atributos.

Tabla de símbolos.
Nombres Atributos

Esta función puede cambiar conforme avanza la traducción y/o ejecución para reflejar adiciones o eliminaciones de ligaduras dentro del programa que se está traduciendo y/o ejecutando.

Es diferente la forma en que se mantiene dicha tabla en un intérprete y en un compilador, ya que en este último puede procesar únicamente atributos estáticos pues el programa no será ejecutado sino hasta después de que se complete la compilación

La tabla de símbolos para un compilador será:

Tabla de símbolos.
Nombres Atributos estáticos

3.2 Declaraciones, bloques y alcance.

Declaraciones: Método primordial para establecer ligaduras. Las ligaduras pueden determinarse mediante una declaración ya sea implícitamente o explícitamente. Por ejemplo en lenguaje C:

int x;
se establece explícitamente el tipo de datos de x utilizando la palabra clave int, pero la localización exacta de x durante la ejecución está únicamente vinculada de manera implícita y podría ser estática o dinámica dependiendo de la localización de dicha declaración dentro del programa.

Implícitamente quedaría: int x = 0;

Algunas veces un lenguaje tendrá nombres diferentes para declaraciones que vinculan ciertos atributos, pero no otros, tomando como ejemplo C o C++ donde las declaraciones que vinculan a todos los atributos potenciales s e conocen como “definiciones”, mientras que declaraciones que especifican sólo parcialmente atributos se conocen simplemente como declaraciones.

Las declaraciones están asociadas con constructores específicos del lenguaje y están agregadas sintáctica y semánticamente con dichos constructores.

Bloque: Es un constructor estándar del lenguaje. Y consiste en una secuencia de declaraciones seguidas por una secuencia de enunciados, y rodeado por marcadores sintácticos como son llaves o pares de inicio – terminación.

Alcance: Alcance de un vínculo es la región del programa sobre la cual se conserva el vínculo, también se puede referir al alcance de una declaración si todas las ligaduras establecidas por la misma tienen alcances idénticos.

Alcance léxico: Sigue la estructura de los bloques conforme aparecen en el código escrito. Se trata de la regla estándar de alcance en la mayoría de los lenguajes.

3.3 La tabla de símbolos.

La tabla de símbolos es como un diccionario variable, esto es: debe darle apoyo a la inserción, búsqueda y cancelación de nombres con sus atributos asociados, representando las vinculaciones en declaraciones. Un símbolo puede mantenerse con cualquier cantidad de estructuras de datos para permitir un acceso y mantenimiento eficientes. Las tablas de Hash, los árboles y las listas son algunas de las estructuras de datos que han sido utilizadas, pero el mantenimiento de información de alcance en un lenguaje con alcance léxico y estructura de bloques requiere que las declaraciones sean procesadas en forma de pila; esto es, a la entrada de un bloque, todas las declaraciones de dicho bloque se procesan y se agregan las vinculaciones correspondientes a la tabla de símbolos; entonces, a la salida del bloque, se eliminan las ligaduras proporcionadas por las declaraciones, restaurando cualquier vínculo anterior que pudiera haber existido. Por distintas razones, no podemos considerar como tabla de símbolos a ninguna de las estructuras anteriores, pero podemos considerar esquemáticamente la tabla de símbolos como un conjunto de nombres, cada uno de los cuales tiene una pila de declaraciones asociadas con ellos, de manera que la declaración en la parte superior de l pila es aquella en que su alcance actualmente está activo. Como ejemplo tenemos una tabla de símbolos implementada en lenguaje C:

(1) int x;
(2) char y;
(3) void p(void)
(4) { double x;
(5) …
(6) {int y[10];
(7) …
(8) }
(9) …
(10) }
(11) void q(void)
(12) { int y;
(13) …
(14) }
(15) main( )
(16) { char x;
(17) …
(18) }

Los nombres dentro de este programa son x, y, p, q y main, pero x y “y” están cada uno de ellos asociados con 3 declaraciones diferentes y con alcances distintos.

Una posible organización para la tabla de símbolos de este programa, después de la entrada en el bloque A dentro de p, es como la que se muestra a continuación.
TABLA DE SÍMBOLOS GLOBAL.
y
character
p
Procedure
tabsim

X
float
A
Block
tabsim
nombre ligaduras
y
Array (1..10) of
integer
Nombre ligaduras
x
integer
Nombre ligaduras
ex
Procedure
tabsim
Nombre ligaduras
3.4 Asignación, tiempo de vida y el entorno.

Ya que hemos considerado la tabla de símbolos, también se necesita estudiar el entorno que mantiene las ligaduras de los nombres con las localizaciones.

Dependiendo del lenguaje, el entorno se puede construir:
Estáticamente, esto quiere decir en “tiempo de carga” (Fortran)
Dinámicamente, que es en “tiempo de ejecución” (Lisp)
Ambos, una mezcla de ambos. (C, C++, Ada, Java, etc)

No todos los nombres en un programa están vinculados con localizaciones. En un lenguaje compilado, los nombres de las constantes y de los tipos de datos pueden representar puramente cantidades en tiempo de compilación que no tienen existencia en el tiempo de carga o en el tiempo de ejecución.

3.5 Variables y constantes.

Variable: Objeto cuyo valor almacenado puede cambiar durante la ejecución. También se puede considerar una variable como que está completamente especificada por sus atributos incluyen nombre, localización, valor y otros atributos como tipos de datos y tamaños.

Representación esquemática de una variable.
valor
Localización
Otros
atributos
Nombre

Esta imagen subraya el nombre, la localización y el valor de una variable como sus atributos principales. En general nos referiremos solamente en lo siguiente:
valor
Localización
Nombre

A esta nueva representación le llamaremos diagrama de cuadro y círculo. La línea trazada entre el nombre y el cuadro de localización se puede pensar que representa el vínculo del nombre con la localización mediante el entorno, y el círculo en el interior del recuadro representa el valor delimitado por la memoria, es decir, el valor almacenado en dicha localización.

Constante: Es una identidad del lenguaje que tiene un valor fijo durante la duración de su existencia dentro de un programa. Una constante es igual que una variable, excepto que no tiene un atributo de localización, sino solamente un valor:

valor
Otros
atributos
Nombre

Se dice que una constante tiene semántica de valor en vez de la semántica de almacenamiento de una variable. Es posible que una constante tenga un valor conocido únicamente durante el tiempo de ejecución., en este caso, su valor debe ser almacenado en la memoria, pero a diferencia de una variable, una vez computado su valor, no puede modificarse, y la localización de la constante no se puede referir de manera explícita a través de un programa.

Una constante simbólica esencialmente es el nombre de un valor.

Tipos de constantes:

Constante estática: Aquella cuyo valor se puede calcular antes de la ejecución.
Tiempo de traducción (o compilación): Solo pueden ser calculadas en este tiempo. Puede utilizarse por un compilador para mejorar la eficiencia de un programa y no necesita realmente ocupar memoria. (Constantes en tiempo de compilación).
Tiempo de carga: Debe ser computada ya sea al arranque o conforme avanza la ejecución y debe ser almacenada en la memoria. (Constante estática)

Constante dinámica: Tiene un valor que se puede computar únicamente durante la ejecución.

Constante de manifiesto: Es el nombre de una literal, en tanto que una constante puede ser mas general.

En el código siguiente (en C) podemos identificar varios tipos de constantes:

#include
#include
a y b son constantes en tiempo de compilación.
a es una constante de manifiesto.
const int a = 2;
const int b = 27+2*2;

c es una constante estática (en tiempo de carga)
/* ¡advertencia, código de C ilegal! */
const int c = (int) time(0);

d es una constante dinámicaint f(int x)
{ const int d = x+1;
return b+c;
}


En C, el atributo “const” se puede aplicar a cualquier variable en un programa que indique simplemente que el valor de una variable no puede ser cambiado una vez establecido; otros criterios determinan si una variable es o no estática.

3.6 Alias, referencias pendientes y basura.

Alias: Un alias ocurre cuando el mismo objeto está vinculado a dos nombres diferentes al mismo tiempo.

Tipos de aliasado:

Durante la llamada de procedimiento.

A través del uso de variables de apuntador. Es difícil de controlar y es una de las razones por las que la programación con apuntadores es tan difícil.

Asignación por compartición: Utiliza apuntadores implícitamente.

Efectos colaterales: Es cualquier cambio en el valor de una variable que persiste mas allá de la ejecución de un enunciado.

No todos son dañinos, puesto que una asignación se pretende explícitamente que cause uno. Pero el efecto colateral en sí, no se puede determinar a partir del código escrito.

Referencias pendientes: Es una localización que ha sido desasignada del entorno, pero a la que el programa puede tener acceso todavía. Son un segundo problema que se puede presentar del uso de apuntadores.

Java no permite referencias pendientes de ninguna manera, puesto que no existen apuntadores explícitos del lenguaje, ni operador “dirección de”, ni operadores de desasignación de memoria como free o delete.

Basura: La basura es memoria que ha sido asignada en el entorno pero que se ha convertido en inaccesible para el programa. Es el tercer problema que se nos puede presentar.

La basura es un problema en la ejecución de un programa dado que se trata de memoria desperdiciada. Sin embargo, se puede pensar que los programas que producen basura tienen menos errores serios que los programas que contienen referencias pendientes. Un programa que produce basura puede dejar de ejecutarse porque se queda sin memoria, pero internamente es correcto, esto quiere decir que si no excede la memoria disponible, produciría resultados correctos. En cambio un programa que tiene acceso a referencias pendientes puede ejecutarse pero producir resultados incorrectos, puede corromper otros programas en la memoria o causar errores en tiempo de ejecución difíciles de determinar.

Recolección de basura: Es cuando los sistemas de lenguajes recuperan automáticamente la basura.

4.2.2 Representación en tiempo de ejecución.

Para la representación de una expresión aritmética en tiempo de ejecución el compilador o interprete arma el árbol en base a las reglas implícitas de precedencia y asociatividad.
Existen alternativas de las formas ejecutables y son:

1) Secuencias de código de máquina: La expresión se transforma a código maquina y de allí directamente se hacen los 2 pasos de la traducción en uno. Permite el uso del intérprete de hardware directamente.
2) Estructuras de árbol: Se maneja directamente con las estructura de árbol, recorriéndola directamente como en LISP.
3) Transformar a postfijo: se pasa la expresión a postfija y se evalúa usando una pila.
No siempre es fácil determinar el orden de evaluación de un árbol al pasarlo a sus operaciones primitivas. Los problemas que se pueden dar son: Reglas de evaluación uniforme, efectos colaterales y condiciones de error, expresiones booleanas en corto circuito.

4.2.3 Expresiones no aritméticas.
Además del orden de ejecución en la evaluación de expresiones aritméticas, en los lenguajes están presentes otros formatos de expresiones.
Este tipo de operaciones son muy utilizadas en lenguajes lógicos:

Concordancia de patrones.
Una operación crucial en lenguajes como SNOBOL4, Prolog y ML es el pattern matching. En SNOBOL4 la operación tiene éxito cuando un patrón predefinido parea con un substring en una variable, el cual es substituido por otro string. Por ejemplo:
La gramática siguiente reconoce palíndromos de longitud impar sobre el alfabeto 0 y 1:
A -> 0A0 1A1 0 1
El reconocimiento de la cadena válida 00100 tiene lugar así:
A1 coincide o parea con el centro 1A2 coincide o parea con 0A10A3 coincide o parea con 0A20
De esta forma se crea el árbol de derivación de 00100:
En este ejemplo los patrones serán los lados derechos de las producciones de la gramática. La operación de pattern matching consiste entonces en parear un patrón con un substring del string que se está analizando y substituirlo por ai.
Mientras que SNOBOL4 emplea el reemplazo de substrings en su pattern matching, Prolog utiliza el concepto de una relación como un conjunto de n-tuplas como mecanismo de concordancia. Mediante la especificación de casos conocidos de estas relaciones (instancias o hechos), es posible deducir otros casos. Por ejemplo, se puede considerar la relación Padre de con las siguientes instancias:
Padre de (Juan,María)Padre de (Susana,María)Padre de (Carlos,Juan)Padre de (Ana,Juan)
Para encontrar al padre de María se escribe la relación Padre de (X,María) y Prolog tratará de asignar un valor a X a partir del contenido del conjunto conocido de hechos de su base de datos e inferirá que X puede ser Juan o Susana.





El poder de Prolog está en la construcción de relaciones que se pueden inferir de manera lógica a partir de un conjunto conocido de hechos. Por ejemplo, de nuestro conjunto conocido:





Abuelo de (X,Y) <- Padre de (X,Z), Padre de (Z,Y) luego Abuelo de (X,María) entregará Carlos o Ana. Reescritura de Términos
La reescritura de términos es una forma restringida de concordancia que tiene numerosas aplicaciones. Dada la cadena a1 a2...an y la regla se reescribe
!
, si
=a i, se dice que a1... a i-1
... an.
La concordancia de una consulta a una base de datos es una forma de reescritura.
La generación de una derivación de una cadena en un lenguaje, es simplemente una forma de proceso de Reescritura, por ej:
A!0B ø1
B!0A
Se puede generar la cadena 001 con la derivación siguiente:
A!0B usando la regla A! 0B
0B!00A usando la regla B! 0A
00A!001 usando la regla A! 1
el ML emplea el termino Reescritura como una forma de definición de funciones, por ej la función factorial se puede especificar de manera sencilla en ML:
fun factorial(n:int)= if n=1 else n * factorial (n-1);
el dominio para factorial se compone de 2 conjuntos para n=1 el valor devuelto es 1, para los demás enteros positivos, el valor devuelto es la expresión n, factorial (n-1).
El enunciado if divide los dos casos , estos se puede ver como 2 funciones separadas, una constante 1 para el conjunto {1} y el valor n* factorial (n-1), para los enteros restantes (es decir {n øn>1}).
En vez de usar el if par separar los subdominios se puede emplear Reescritura de términos para indicar cada caso por separado.





Fun longitud(nada) = o
ø Longitud(a::y)= 1+longitud(y);
cada subdominio separado porø. El ML reemplazara la llamada de función por la definición apropiada.





Unificación.
Consiste, ante una consulta (predicado conteniendo variables), en la sustitución de variables para concordar patrones congruentes con las reglas y hechos de la base de datos.
En la implementación de la unificación en PROLOG las pilas desempeñan un papel importante. Además, para el recorrido del árbol de búsqueda se emplea el RETROCESO, salvo que se encuentre la función ! (corte), que hace que se produzca siempre fracaso al retroceder a la última solución plausible.





Retroceso.
Al describir el comportamiento de ejecución de prolog para add, todas las submetas concordaron en el proceso del cómputo. sin embargo, ¿qué ocurre si esto no es cierto?, ¿Qué pasa si alguna submeta no se puede unificar con una regla de datos?. En este caso, se dice que regla fracasa.
En todo momento se hace concordar una submeta , si la concordancia ha de tener éxito , entonces una de las metas posibles tendrá éxito, solo que no se sabe necesariamente cuál. Si se intenta primero la meta incorrecta , entonces esa meta fracasará. En esta caso, simplemente se intenta otra meta posible.
Para poder describir el algoritmo general de retroceso se debe hacer:
1.- Para la submeta fijar k=1 como una nueva meta.
2.- Intentar concordar en forma sucesiva goal, para k=1..M y devolverse ya sea éxito o fracaso, según si alguna meta tiene éxito o todas fracasan.
3.- Si la meta tiene éxito, la submeta también tiene éxito.
4.- Si la meta fracasa para todas las k, entonces . Se tendría que devolver a la submeta e intentar la meta siguiente posible k+1 para esa submeta.
5.- Si la meta tiene éxito, entonces devolver éxito como resultado de la meta padre que se estaba buscando.
6.- Si la submeta fracasa , entonces la meta fracasa; se deberá devolver el fracaso como resultado de la búsqueda de la meta por el padre.
Lo que intenta hacer el algoritmo es tratar de concordar en forma exitosa, apilando y desapilando sucesivamente resultados parciales.





4.3 CONTROL DE ENUNCIADOS

4.3.1 ENUNCIADOS BÁSICOS

Los resultados de cualquier programa están determinados por sus enunciados básicos que aplican operaciones a objetos de datos. Son ejemplo de estos enunciados básicos los enunciados de asignación, llamadas de subprograma, y enunciados de entrada y salida. Cada enunciado básico se puede considerar como una unidad que representa un solo paso en el cómputo.

A. ENUNCIADO DE ASIGNACIÓN

Es una acción ó proceso por el cual se le asigna un valor ( constante ó variable) ó el resultado de una operación ( expresión ) a una variable. Los enunciados de asignación se utilizan generalmente para cambiarle de valor a una variable ó definirla. Definir una variable consiste en asignarle ó darle por primera vez un valor, y puede hacerse de dos maneras: Por medio de una lectura de datos ó utilizando un enunciado de asignación.

COMPOSICIÓN
EJEMPLO
VARIABLE = VARIABLE
VARIABLE = EXPRESION
VARIABLE = CONSTANTE
PAGO = SALARIO BRUTO
RESULTADO = ( A + B + C ) / 68
BONIFICACION = 7890

Debe tenerse en cuenta que la parte de la izquierda de un enunciado de asignación siempre va y debe de ir una variable. La flecha izquierda significa asignación e indica que el valor de la parte derecha de un enunciado ( variable, expresión ó constante) se le asigna a la parte de la izquierda ( variable). Sin embargo también se utiliza el signo igual para indicar asignación.

Composiciones Posibles de un Enunciado de Asignación

1. Toda variable que aparezca al lado derecho de un enunciado de asignación debe estar definida.
· B = 25
C = B+30

· T=89
Q=34 + T
2. En un enunciado de asignación la variable de la izquierda es la única que cambia de valor cuando con anterioridad tiene un valor asignado.
· PAGO = 2000
DEUDA = 500
PAGO = DEUDA + 3500
· T = 90
Q = 78
T =Q + 67
3. Las variables que aparecen en la parte derecha de un enunciado de asignación conservan su valor después de ejecutarse el enunciado.
· A = 60
B = A + 70
· Q = 78
L = 45
RESULTADO = Q + L
4. Si la variable de la parte izquierda del enunciado se encuentra también al lado derecho esta variable cambia de valor por aparecer en la izquierda.
· A = 20
B = 2
A = A+B


· CONT = 0
CONT = CONT +1

B. LLAMADAS DE SUBPROGRAMA.

La resolución de problemas se facilita considerablemente si se dividen en problemas más pequeños (subprogramas) y a continuación dividir estos subproblemas en otros más simples hasta que los problemas más pequeños sean fáciles de denominar “divide y vencerás” (divide and conquer). La solución de estos subprogramas se realiza con subalgoritmos. El uso de subalgoritmos permite al programador desarrollar programas de problemas complejos utilizando el método descendente (top-down). Se denomina descendente ya que se inicia en la parte superior con un problema general y el diseño específico de las soluciones de los subproblemas. Normalmente las partes en que se divide un programa deben poder desarrollarse independientemente entre sí. Los subalgoritmos (subprogramas) pueden ser de dos tipos : funciones y procedimientos o subrutinas. Los subalgoritmos son unidades de programa o módulos que están diseñados para ejecutar alguna tarea específica. El subprograma puede realizar las mismas acciones que un programa :

1. Aceptar datos .
2. Realizar algunos cálculos .
3. Devolver resultados .

Estas funciones y procedimientos se escriben solamente una vez, pero pueden ser referenciados en diferentes puntos de un programa de modo que se puede evitar la duplicación innecesaria del código.
PROBLEMA
PRINCIPAL
PROGRAMA
PRINCIPAL
SUBPROBLEMA
1

SUBPROBLEMA
2

SUBPROGRAMA
3

SUBPROBLEMA
3

SUBPROGRAMA
1

SUBPROGRAMA
2

Se dice que el programa principal llama o invoca al subprograma. El subprograma ejecuta una tarea, a continuación devuelve el control al programa. Esto se puede suceder en diferentes lugares del programa. Cada vez que el subprograma es llamado, el control retorna al lugar de donde fue hecha la llamada. Un subprograma puede llamar a su vez sus propios subprogramas.

PROGRAMA

SUBPROGRAMA 1

SUBPROGRAMA 2
SUBPROGRAMA 1.1





C. ENUNCIADO DE LECTURA (ENTRADA).

El enunciado de lectura se utiliza simplemente para introducir datos que van a utilizar en la solución del algoritmo. Consta de la palabra LEA y a continuación se relacionan en forma de lista las variables a leer separadas por comas así:

LEA VAR1, VAR2, VAR3,…………VARN




D. ENUNCIADO DE ESCRITURA (SALIDA)

Se utiliza para informar resultados que se esperaban obtener al ejecutarse el algoritmo. Consta de la palabra imprima seguida de las listas de variables separadas por comas, así :


IMPRIMA VAR1, VAR2, VAR3,…VARN

4.3.2 ENUNCIADOS COMPUESTOS

Un enunciado compuesto es una serie de enunciados que se puede tratar como un solo enunciado en la construcción de enunciados más grandes. Un enunciado compuesto se suele escribir así:

begin
… -> serie de enunciados (uno o más)
end

Dentro de un enunciado compuesto, los enunciados se escriben en el orden en que se ejecutan. Así pues, el enunciado compuesto es la estructura básica para representar la composición de enunciados. Puesto que en un enunciado compuesto es el mismo enunciado, los grupos de enunciados que representan unidades conceptuales de cómputo individuales se pueden conservar juntos como una unidad encerrándolos entre los corchetes begin … end, y se pueden construir jerarquías de estos grupos.
Un enunciado compuesto se implementa en una computadora convencional colocando los bloques de código ejecutable que representan cada enunciado consecutivo en serie en la memoria. El orden en que aparecen en la memoria determina el orden en que se ejecutan.

Los enunciados pueden ser bloques de sentencias entre llaves:

* Secuencial
* Condicional, if...then...else...;
* Condicinal múltiple, switch...{case....case...default...;}
* Iterativos: while, do , for.
* Transferencia del control: brak, continue, goto, return.
* De preprocesador: #define, #include, #ifdef, #if...#undef...#else

A. ENUNCIADO SECUENCIAL




B.ENUNCIADOS CONDICIONALES

Un enunciado condicional es uno que expresa alternancia de dos o más enunciados, o ejecución opcional de un solo enunciado; donde enunciado significa ya sea el enunciado básico individual, un enunciado compuesto u otro enunciado de control. La elección de la alternativa es controlada por una prueba sobre cierta condición, la cual se escribe ordinariamente como una expresión en la que intervienen operaciones relacionales y booleanas. Las formas mas comunes de enunciado condicional son los enunciados if(si) y case(en caso de).

Enunciados if

* La ejecución opcional de un enunciado se expresa como un if de una bifurcación:

if condición then enunciado endif

condición
NO
SI
enunciado

* Una opción entre dos alternativas emplea un if de dos bifurcaciones:

if condición then enunciado1 else enunciado2 endif

condición
NO
SI
enunciado 1
enunciado 1

* Una opción entre varias alternativas se puede expresar anidando enunciados if adicionales dentro de los enunciados alternativos de un solo if, o por medio de un if de ramificaciones múltiples:

if condición1 then enunciado1
else
if condición2 then enunciado2

else
if condiciónn then enunciadon
else enunciadon+1
endif

Enunciados case

En un if de ramificaciones múltiples las condiciones suelen adoptar la forma de prueba repetida del valor de una variable, por ejemplo:

if Marca = 0 then enunciado0
else
if Marca =1 then enunciado1
else
if Marca =1 then enunciado2
else enunciado3
endif

La variable Marca se puede sustituir por cualquier expresión cuya evaluación sea un solo valor, y entonces las acciones para cada uno de los valores posibles se representan mediante un enunciado compuesto precedido por el valor de la expresión que causaría la ejecución de ese enunciado compuesto.

Esta estructura común se expresa de manera más concisa como un enunciado case:

case of
condición1:
begin



end
condición2:
condiciónp:
else
enunciadon;
end;

C. ENUNCIADOS DE ITERACIÓN.

La iteración suministra el mecanismo básico para los cálculos repetidos en casi todos los programas. La estructura básica de un enunciado de iteración consiste en una cabeza y un cuerpo. La cabeza controla el número de veces que el cuerpo se va a ejecutar, en tanto el cuerpo es ordinariamente un enunciado (compuesto) que proporciona la acción del enunciado.

Repetición simple

Especifica que el cuerpo se debe de ejecutar cierto número fijo de veces. Como ejemplo tenemos Perform de Cobol:

Perform cuerpo k times

que hace que se evalúe k y luego se ejecute el cuerpo del enunciado ese número de veces.

Repetición mientras se cumple la condición

Usamos la cabeza de repetir mientras para construir una iteración más compleja:

while do acción;

while do begin
acción1;

acción n;
end;

Mientras se cumpla la condición, se realiza la iteración.

En esta forma de enunciado de iteración, la expresión se reevalúa después de cada vaz que se ha ejecutado el cuerpo. Adviértase que la ejecución del cuerpo cambia algunos de los valores de las variables que aparecen en la expresión de prueba, de lo contrarario la iteración, una vez iniciada, nunca terminaría.

Repetición y cumplimiento de condición

Mientras la condición sea falsa se realiza la iteración, al contrario de while.

repeat
acción;
until ;

repeat
acción1;

acción n;
until ;

Repetición mientras se incrementa un contador

La cabeza de este enunciado especifica una variable que sirve como un contador o índice durante la iteración. En la cabeza especifica un valor inicial, un valor final y un incremento, y el cuerpo se ejecuta repetidamente usando primero el valor inicial como valor de la variable índice, luego el valor inicial más el incremento, después el valor inicial mas dos veces el incremento y así sucesivamente, hasta que se alcanza el valor final.

variableinicial=x
for variableíndice=variableinicial step incremento do cuerpo

Repetición indefinida

Cuando las condiciones para la salida de la iteración son complejas y no fácilmente expresables en la cabeza de la iteración usual, suele emplearse una iteración sin una prueba explícita de terminación en la cabeza, como por ejemplo:

* En lenguaje Ada:
loop

exit when condición;

end loop;

* En Pascal, usando una iteración while conuna condición que siempre es
cierta:
while cierta do begin … end

* En C, el enunciado for permite todos estos conceptos en una sola
construcción:
for(expresión1;expresión2;expresión3)
{ cuerpo}

donde expresión1 es el valor inicial, expresión2 es la condición de repetición y
expresión3 es el incremento. Todas estas expresiones son opcionales, lo cual
permite mucha flexibilidad en la iteraciones en C. Algunas iteraciones de
muestra en C se pueden especificar como:

- Contador simple de 1 a 10 for(i=1;i<=10;i++) { cuerpo} - Iteración finito for(;;) { cuerpo} - Contador con condición de salida for(i=1;i=<=100 && NoFinArchivo;i++) { cuerpo}

REFERENCIAS:
*LOUDEN, Kenneth C.Lenguajes de Programación2a. ediciónMéxicoThompson Learning, 2004.

*Programming Language Designing ConceptsWatt A. David, Finlay William.Cap 2.6 pag 43-46John Wiley & Sons. England. 2004.





10 comentarios:

Liliana Gonzalez dijo...

La información me parece muy concreta y sencilla de entender, creo que desarrollaron muy bien los temas y añadieron imagenes para entender mejor el tema

S@POP¡OJO dijo...

el EQUIPO 2 opina:

* Que a simple vista se confunde uno puesto que presentar primero las imagenes, talvez no fue lo mejor, a nuestro parecer hubiera quedado mejor 1ro. la informacion y despues las imagenes, o intercalarlas.
*otro punto es que apesar de que su tema es muy largo supieron tratarlo, tal vez el manejo de letras mas grandes y todo ese juego de letras le daria una mejor presentacion.
*tambien nos gustaria saber su fuente, nosotros pensamos que el el libro que el profesor recomendo.
*que nos gusto que pusieran ejemplos, eso consideramos que es muy bueno ya que hay cosas que luego no se comprenden bien, pero ya con el ejemplo es mas facil

y para concluir opinamos que en algunos puntos tal vez si pudieran hacer un resumen.

EQUIPO2 LENGUAJES DE PROGRAMACION
ºGONZALEZ JIMENEZ LILIANA
ºJASSO GUADIANA NATALI
ºLOPEZ GARFIAS MARYCARMEN
ºLOPEZ MELO ROSA A.
ºMIGUEL HERNANDEZ GUILLERMO
ºORDAZ JIMENEZ ANTONIO

Equipo 1 Lenguajes de Programación Grupo: 04 dijo...

A nuestro parecer, se nos hizo bastante extenso el resumen que realizaron del tema que les tocó, pero realmente todo lo que pusieron es muy importante e interesante.
Las imàgenes que agregan al igual que los ejemplos son muy atractivos y entendibles, aunque hubiera sido mejor poner primero su texto y luego las imágenes.

EQUIPO 1 LENGUAJES DE PROGRAMACIÒN

1. Arellano Quintero José Omar
2. Bautista Salazar Eduardo
3. Cárdenas Feria Nancy
4. Gómez Mares Cristian Rodolfo
5. Juárez Vásquez Mayra
6. Pérez Cruz Juan Carlos

Servin Pichardo Luz Tavata dijo...

Equipo 7 Lenguajes de programación grupo 04 sugiere que el hecho de poner primero todas las imágenes es algo confuso, puesto que ciertos usuarios no sabrán muy bien de que trata el tema; por otra parte creemos que sería mejor intercalr información e imagen o imagen e información. Es bueno que su tema se prestara para que pudieran presentar ejemplos, ya que hace se comprenda mejor la información presentada. Conocer la fuente siempre es útil para saber a donde podemos recurrir si deseamos hacer una consulta.
Integrantes:
Lozano Aguilar César Iván
Servin Pichardo Luz Tavata
Toledo Flores Miguel Angel

Equipo de Tipos de Datos dijo...
Este comentario ha sido eliminado por el autor.
Equipo de Tipos de Datos dijo...

Que tal equipo, somos el equipo 3.
Estuvimos leyendo lo que pusieron en su blog y nos parece que la información está muy completa, aunque demasiado extensa. Y una cosa que también nos sacó un poco de onda fue el que hayan puesto primero las imágenes. Creemos que éstas deben de ir en el lugar mas acorde al contexto. Pero en general nos parecen muy buenos sus ejemplos y su información.

* Nakamura Orozco Roberto Yasuhiro
* Ortega Tapia Edgar
* Sarabia Bautista Juan Alberto
* Villaseñor Gallegos Carlos Alberto

VISITEN NUESTRO BLOG EN...
http://lengtiposdedatos.blogspot.com

Javier Solana dijo...

Hola equipo 4, somos el equipo 6 nos agrado mucho la presentacion de su blog, sin embargo nos parecio que estaba un poco extensa su informacion y tambien que sus imagenes las colocaran ya sea en los temas a los que pertenecen o hasta el ultimo, buen detalle lo de los ejemplos.

Saludos

Lenguajes de Programación Grupo 4 dijo...

La informacion es buena y entendible ademas de que las imagenes les fueron de gran ayuda para el entendimiento de los temas posteriores ; si pudieran cambiar el color del texto ya que es cansado para la vista

Lenguajes de Programación
Grupo 4
Chavéz Ramos Andrés
Hernández González María Adriana
Piña Navarro Tania Paola
Sánchez González Sonia Mariana
Santos Medina Alejandro
Trejo Martínez Elizabeth

Unknown dijo...

La informacion que contiene este blog nos parece sencilla y directa, muy facil de comprender, esto tambien se debe a que pusieron imagenes.
Aunque seria mejor que apareciera la informacion en lugar de las imagenes.
ATTE:
Blanco Colin
Miranda Pineda
Tlahuel

circe dijo...

Me parece un tema un tanto complicado pero creo q desarrollaron muy bien los temas asi q si facilitan la comprension de ellos ademas es de gran utilidad que tengan imagenes

cecilia blanco