Las partes de un Compilador

Vemos a grandes rasgos, que tenemos un programa fuente o source program, este se compila y se traduce a un programa objeto o target program. Lo que analizaremos en este post, será el cuadradito verde oscuro que dice "compilador".

He aquí las diferentes fases de un compilador:

1) Lexical Analyzer o Analizador Léxico

Este proceso se denomina "SCANNING". Se escanean los símbolos de entrada y se agrupan en unidades llamadas tokens o words. Por ejemplo, el siguiente código escrito en Java contiene 5 tokens: 

               temp = x + 1 

token 1 :  "temp" (identificador)

token 2:  " = " (símbolo de asignación)

token 3:  " x " (variable)

token 4:  " + " (símbolo de suma)

token 5:  " 1 " (número)

2)  Syntax Analysis o Análizador Sintáctico

Este proceso se denomina "PARSING". Los tokens son agrupados en unidades sintácticas (como ser expresiones, sentencias y declaraciones) que conforman las reglas gramaticales de los lenguajes de programación.  El objetivo del "parsing" es generar una estructura de datos ( parse tree) que represente la estructura sintáctica del programa para luego obtener una respuesta: programas sintacticamente correctos (continua el análisis) o programas sintácticamente incorrectos (produce un error y la compilación finaliza). 

Ahora bien, veamos un ejemplo: dada una secuencia de tokens y utilizando la gramática BNF.

                              

s: statement

v: variable

e: expression

b: boolean

Vamos definiendo una secuencia de pasos donde reemplazamos símbolos no terminales por otros símbolos no terminales hasta que finalmente resultan en un símbolo terminal ( x,y,z,0,1,2,3,4).

Este tipo de interpretación gráfica presenta una ambigüedad. Porque???

Porque depende del orden en el que leamos las sentencias. 

Sea 

                    s1 = "x := 1"

                    s2 = "y := 2"

                    s3 = "if x=y then y:=3"

Veamos que s1;s2;s3 es ambigüo. Es decir, que no resulta lo mismo si ejecutamos de la siguiente forma:

                a) ( s1 ; s2 ) ; s3

                b) s1 ; ( s2 ; s3 )

Como por ejemplo 

¿Qué sucedería si b1 es verdadera y b2 es falsa ? ¿Se ejecutará s2? Como se puede observar, esto depende en como la sentencia se "parsea" o analiza gramaticalmente. 

3) Semantic Analysis o Analizador Semántico (Estático)

Este tipo de análisis depende del contexto en el que se analiza una expresión.  Por ejemplo 

                                                                temp := x + 1

Opción 1: declaramos a los identificadores temp y x como números enteros; entonces el número 1 será un número entero y la suma (+) será una suma de enteros

Opción 2:  declaramos a x como un número decimal; el número 1 será marcado como un número decimal y la suma (+) será suma de decimales. Ahora bien, ¿qué valor obtiene temp? dependiendo de tipo de dato sea temp. Si temp fue declarado como un número entero, entonces la suma x+1 se redondeará a número entero. 

Se observa que el resultado de la suma depende del tipo de dato mediante los cuales fueron definidos tanto el identificador temp como el identificador x. 

El proceso de parsing anteriormente mencionado debe incluir información adicional, como ser los tipos de datos de los identificadores y el lugar en el programa donde cada identificador fue declarado.

4) Intermediate Code Generator o Generador de Código Intermedio 

Aunque es posible generar un programa destino o program target  con los análisis sintácticos y semánticos, resulta dificil generar un código eficiente en una fase. Aún así, muchos compiladores producen un código intermedio y luego optimizan este código para producir un programa destino más eficiente. La representación intermedia puede ser algún tipo de código genérico de bajo nivel que posee propiedades comunes a varias computadoras. ¿Cuál es la ventaja?

Permite la optimización generando código independiente de la máquina.

Existen varios tipos de código intermedio:

1. Específico al lenguaje (P-code para Pascal, Bytecodes para Java)
2. Código de 3 direcciones ( ej: x := y op z )
3. Código de 2 operaciones ( ej: x := op z  que es equivalente a x := x op z )
4. Representación gráfica

Para mayor información, puede leer las siguientes diapositivas.

5) Code Optimizer o Optimización del Código

Se describen una lista de algunos estándares de optimización para que el programa sea más corto o más rapido en tiempo de ejecución o ambos.

1. Eliminación de subexpresiones comunes: si un programa calcula el mismo valor más de una vez y el compilador lo detecta, entonces puede ser posible transformar el programa de manera que el valor sea calculado una sola vez y almacenado para su posterior utilización.
2. Propagación de copia: si un programa contiene asignación como por ejemplo x := y, es posible modificar las sentencias posteriores para referirse a "y" en vez de a "x" y de esta forma eliminar la asignación.
3. Eliminación de código muerto: si existe alguna secuencia de instrucciones que nunca va a ser ejecutada, entonces se elimina del programa.
4. Optimización de bucles:  existen varias técnicas que pueden ser aplicadas para eliminar instrucciones de bucles. Por ejemplo, si una expresión aparece dentro de un bucle, pero tiene el mismo valor en cada entrada al bucle, entonces esta expresión se puede mover fuera del bucle.
5. Llamadas a funciones: si un programa llama a una función "f", es posible sustituir el código de la llamada a la función por la función completa.

6)  Code Generation o Generación de Código

La última fase implica convertir el código intermedio en código de máquina. Esto significa elegir las ubicaciones de memoria, un registo o ambos, para cada variable que aparezca en el programa. Existe una gran cantidad de algoritmos de asignación de registros con el propósito de reusar los registros eficientemente. Esto es importante porque varios diseños de máquinas contienen un número fijo de registros, y las operaciones con registros son más eficientes que la transferencia de datos dentro y fuera de memoria.

Bibliografía:

. Concepts in Programming Languages - John C. Mitchell 

Concepto sobre sintaxis y semántica de los lenguajes de programación

LENGUAJE, SINTAXIS, SEMÁNTICA, Y DEMÁS … CON UN POCO DE FILOSOFÍA

"That which can be said, can be said clearly" Wittgenstein

Antes de definir que son los lenguajes de programación junto con su sintaxis y su semántica, vamos a hacer una recorrida por los lenguajes mediante los cuales nos comunicamos día a día.

Si hacemos referencia al video "Mentira la verdad, el lenguaje" del programa de televisión Canal encuentro, podemos empezar con las siguientes preguntas:

“Todo es texto, lo que digo, lo que pienso, incluso lo que hago. Como dice Jacques Derrida no hay nada por fuera del texto. Todo es texto, nada hay por fuera del lenguaje. Pero, si todo es texto y nada hay por fuera, ¿a qué se refieren las palabras? , ¿de qué habla el lenguaje? ¿habla de las cosas o habla de sí mismo? ¿hay algo que podamos pensar sustraído al lenguaje? ¿qué es el lenguaje? ¿cómo lo fuimos pensando a lo largo de la historia? ¿es cierto que el hombre es y además camina, además respira o además duerme? ¿o es al revés, y el habla nos hace hombres? ¿el hombre habla o el lenguaje nos constituye como hombres? “

Estos  interrogantes se dan al inicio del video. En el mismo, se establece el debate desde el interrogante. 

Una vez que se plantea el interrogatorio para encontrarle una definición al lenguaje, nos seguimos preguntando sobre como lo adquirimos  …

¿cómo es el que hombre aprende su lenguaje ? ¿cuáles son las facultades de la mente?  ¿dicho lenguaje lo ha visto, leido o escuchado anteriomente? ¿está el lenguaje bien construido? ¿está mal construido? ¿qué conocimiento de su lengua tiene el hablante que le permite construir y entender oraciones que nunca antes ha leido?

La gramática tradicional divide  al estudio de todas las lenguas del mundo por convención, en dos secciones : morfología y sintaxis. 
 “la morfología explica la estructura interna de las palabras y el proceso de formación de las palabras,  mientras que la sintaxis describe como las palabras se combinan para formar sintagmas, oraciones y frases”

Noam Chomsky

Sin embargo, en el seno de la gramática generativa se ha sostenido que la morfología es insostenible como rama autónoma.  De esta forma surge la gramática generativa y transformacional. El iniciador de la teoría gramática generacional es Noam Chomsky, siendo uno de los campos de investigación más activos de la lingüística moderna. 


Podemos decir que el lenguaje es  creativo porque se pueden producir y entender una cantidad infinita de nuevas expresiones que no nos fueron enseñadas. No nos limitamos a repetir frases que ya hemos escuchado, si no que las creamos en función de las necesidades cambiantes de cada momento. Entendemos las oraciones que los otros pronuncian, o escriben a pesar de no haberlas leido o escuchado antes. 
La gramática generativa presenta de forma explícita las reglas gramaticales que aplica implicitamente el hablante/oyente para construir/entender las oraciones. 
Para comprender la diferencia de significado entre las oraciones no es suficiente conocer el significado de las palabras que las componen, si no que es necesario ver también la información sintáctica que contienen. Esto es la información no lexical que es transmitida por medio de la estructura de la oración misma. 
Cuando conocemos un lenguaje sabemos que es un conjunto de palabras y reglas con  las cuales generamos cadenas de esas palabras.

Ahora bien, escribamos la definicipón etimológica de sintaxis: del griego “syn” con y “taxis” orden. La sintaxis describe como las palabras se combinan para formar sintagmas, oraciones y frases. La sintaxis no se ocupa del estudio de las palabras, sino de las agrupaciones que éstas forman (tanto las de primer nivel o sintagmas, como las de segundo nivel u oraciones) y de las funciones que desempeñan. De esta forma, podemos decir que existen enunciados sintacticamente correctos como enunciados sintácticamente incorrectos. Los enunciados sintácticamente correctos son aquellos en los que los diferentes sintogmas estén bien construidos, bien posicionados y correctamente relacionados los unos a los otros. 


Y me gustaría continuarlo para adentrarlo a los lenguajes de programación...
¿Qué es lo que hace que un lenguaje sea diferente de otro? ¿Qué es lo que hace que un lenguaje sea parecido a otro? 

Un lenguaje de programación  es un lenguaje formal para la formulación de algoritmos y estructuras de datos, eso quiere decir, para formular reglas de cálculo que pueden ser ejecutados por una computadora. Cuando observamos un código escrito en un determinado lenguaje de programación, nos podemos preguntar ….
cómo sabemos si está bien escrito, cómo sabemos qué es lo que hace el programa, cómo sabemos si resuelve correctamente el problema planteado, cómo sabemos que significa, y cómo un compilador sabe como traducir el programa ???
Todo lenguaje de programación debe ser definido con suficiente detalle para que permita resolver casi cualquier tipo de problema. Entonces, la definición de un lenguaje de programación debe permitir determinar 

(1) si un supuesto programa es un hecho válido

(2) si el programa es válido, cuál es su significado o su efecto


Según el libro CONCEPTS IN PROGRAMMING LANGUAGES de John C. Mitchell, parte 4.1 ...
Un programa es una descripción de un proceso dinámico. El texto mismo de un programa es llamado SINTAXIS; las cosas que un programa realiza comprende la SEMÁNTICA. La función de la implementación de un lenguaje de programación es transformar la sintaxis de un programa en instrucciones de máquina que puedan ser ejecutadas.

El estudio de los lenguajes de programación, como así el estudio de las lenguas nativas, se pueden examinar desde la sintaxis y semántica. La sintaxis de los lenguajes de programación se refieren a sus expresiones, sentencias y unidades del programa. Su semántica se refiere al significado de aquellas expresiones, sentencias y unidades de programa. Por ejemplo, en Java la sentencia while  se describe como la siguiente:
  
        while (expr_booleana) sentencia

              
La semántica de esta expresión sintáctica, es ejecutar la sentencia cuando el actual valor de expr_booleana sea verdadero, y repetir el proceso. Si el valor actual de expr_booleana es falso, la linea de ejecución continua por debajo del bloque de sentencias while.


El siguiente post contiene la definición de sintaxis, junto con sus características, sus elementos, los tipos de sintaxis existentes, la estructura sintáctica y las diferentes formas de expresar la sintaxis (EBNF, árboles de derivación y árboles sintácticos, diagramas sintácticos)

Bibliografía:
. Programming language concepts - Carlo Ghezzi, Mehdi Jazayeri
. Concepts in programming languages - John C. Mitchell
. Sintaxis - definiciones y su evolución

. Definición de sintaxis

. Etimología de la palabra sintaxis

.  Morfología Lingüística

. Video canal encuentro, programa: "Mentira la verdad, el lenguaje"

. Video  Gramática Generativa - Noam Chomsky

Tiempo de Ejecución - de código JAVA a expresión matemática

Objetivo: descubrir que dos algoritmos diferentes tienen el mismo orden de ejecución, es decir, que comparten el mismo comportamiento asintótico.


LES PRESENTO A LOS DOS ALGORITMOS:

 


Cuando analizamos el tiempo de ejecución de un algoritmo,se toma en cuenta las estructuras de control (while, for, if-then-else, do). En este caso, en ambos códigos, prestamos atención a la sentencia "while". Las demás sentencias se consideran constantes. ¿Por qué? Por ejemplo las sentencias "int c=N" o "c=c/2" contienen: alocación de memoria y utilización de la ALU para calcular "c/2". Esto se resuelve en tiempo constante.


VOLVIENDO A ALGUNAS CLASES DE MATEMÁTICA ...

Primero definamos el concepto de función matemática.

DEFINICIÓN DE FUNCIÓN [1]

Sean A y B dos conjuntos no vacíos, que llamaremos dominio y codominio respectivamente. Entenderemos por función de A en B toda regla que hace corresponder a cada elemento del dominio un único elemento del codominio. Más precisamente, una función es un conjunto de pares ordenados tales que la primera componente pertenece a A y la segunda componente pertenece a B, es decir, un subconjunto de A X B, de modo que todo elemento de A sea primera componente de un par y sólo de uno. Esto nos dice que toda función de A en B es una relación especial entre A y B. 
Se escribe de la siguiente forma:

"f es una función con dominio en A y codominio en B"

En particular, 

y f es la relación definida por 

entonces se tiene 

ya que la segunda componente es el cuadrado de la primera. 

EL diagrama de Venn correspondiente es 

Tanto en la definición de f por extensión como en el diagrama de Venn es fácil advertir que todo elemento del dominio tiene un correspondiente o imagen en el codominio y; además tal correspondiente es único. 

Observemos la siguiente situación: elementos distintos de A pueden tener la misma imágen en B. Es decir, f(-1)=1 y f(1)=1. 

Ahora bien, pero que tiene que ver esto con el análisis de tiempo de ejecución de los dos algoritmos arriba mencionados?

Debemos de ser capaces de identificar quien es f, A, y B respecto al código arriba mencionado. Es la misma analogía.

SI ANALIZAMOS EL PRIMER CÓDIGO....

                    

Sea N=32, entonces entramos al bloque while cuando c=32, c=16, c=8, c=4, c=2. Pero cuando c=1, ya no entra al while. Entonces nos preguntamos, ¿Cuántas veces entre al bloque while? ¿Cuántas veces se ejecuta el while para N=32? 5 veces. ¿Que tuvimos en cuenta para concluir que se ejecuta 5 veces? Es decir, de que depende que el bloque while se ejecute 5 veces? Depende del valor de "N" y del cálculo "c = c / 2". 

Ahora debemos relacionar N con la cantidad de veces que se ejecuta el algoritmo. En este caso, relacionamos N=32 con 5, y esto nos lleva a pensar que

Si  entonces

                   el "while" se va a ejecutar 5 veces. 

Si  entonces

                   el "while" se va a ejecutar 6 veces. 

       

Observen que existe un intervalo donde el bloque while se ejecuta  la misma cantidad de veces. Esos intervalos son los siguientes:

  

Podemos concluir que N se ejecuta la misma cantidad de veces para  un determinado intervalo, y que dicho intervalo varía en potencias de 2 para el ejemplo del "código 1".

¿Y para que me servía la definición de función?

Sea  f:N->M , N y M naturales / f(N)=log2(N)  

¿Qué significa N, M y f(N)?

N: Es el valor de entrada que recibe el código. Dependiendo del valor de N, el algorítmo se va a ejecutar más o menos veces.

M: Es el valor aproximado que determina la cantidad de veces que se ejecuta el algoritmo. M depende del valor que tenga N. M no es un número entero cualquiera. M es una unidad de tiempo.

f(N): Es lo que tenemos que descubrir nosotros mismos. Pudimos encontrar que f es de la forma f(N)=log2(N).

Sea f(N)=M=20, siginifica que el algorítmo tarda en ejecutarse 20 unidades de tiempo. ¿Porque la imagen de f son unidades de tiempo y no horas, minutos y segundos? La unidad de tiempo sirve para comparar algoritmos sin depender de la arquitectura subyacente (un algoritmo "tarda" más que otro en ejecutarse). Si uno desea en la práctica estimar el tiempo real, es necesario definir a la unidad de tiempo en horas minutos y segundos.  

OBSERVACIÓN: Valores distintos de N pueden tener la misma imagen.

SI ANALIZAMOS EL SEGUNDO CÓDIGO ....

                                                   

Si N=47, entonces entramos al while cuando c=2, c=4, c=8, c=16, c=32 y cuando c=64 ya no entra al while. Entonces, nos preguntamos, ¿Cuántas veces se ejecuta el while teniendo en cuenta a N y el cálculo c*2? Se ejecuta 5 veces. Ahora debemos relacionar N con la cantidad de veces que se ejecuta el algoritmo. En este caso relacionamos N=45 con 5, y esto nos lleva a pensar que

 Tomamos la parte entera de 

CONCLUSIÓN

Pudimos analizar que ambos algoritmos tienen el mismo comportamiento asintótico. Es decir, que ambos tardan aproximadamente el mismo tiempo de ejecución para un valor de N dado. Observen que no es de interés obtener un resultado exacto de tiempo de ejecución, ya que es una estimación del mismo. 

Bibliografía:

[1] Algebra I, Armando Rojo ( Funciones: Capítulo 4 Página 102 )

Para que estudiar los Conceptos de los Lenguajes de Programación

"The limits of my language are the limits of my word" Wittgenstein

Un Lenguaje de Programación es ....

un lenguaje formal para la formulación de algoritmos y estructuras de datos, eso quiere decir, para formular reglas de cálculos que pueden ser ejecutados por una computadora.[1]

Los lenguajes de programación son una herramienta para escribir software.   Pueden ser utilizados para crear programas que controlen el comportamiento de una máquina o para expresar un algoritmo.

Los primeros lenguajes de programación estaban orientados a las propiedades de determinadas computadoras. Hoy en día se utilizan mayormente lenguajes orientados a problemas, los así llamados lenguajes de alto nivel, los cuales  son más abstractos y permiten una expresión más entendible del mundo real. [2]

Estudiamos los conceptos de los lenguajes de programación con el propósito de ...

tener la habilidad de elegir, diseñar, implementar o utilizar un lenguaje. 

Podremos identificar sus alcances y sus limitaciones  para:

1) Aumentar la capacidad para producir software

Conociendo las características de los lenguajes permite minimizar su esfuerzo, evitar errores y aprovechar su potencia. Por ejemplo, no es lo mismo C que Smalltalk. El primero es un lenguaje estructurado mientras que el segundo es orientado a objetos

2) Mejorar el uso del lenguaje

Si se comprende como se implementa cada característica, se mejora la capacidad de escribir programas más eficientes. Por ejemplo, entender la diferencia entre List y Set en Java. List es una secuencia ordenada de elementos mientras que Set es una lista de elemento sin ningún orden.

3) Incrementar el vocabulario 

A veces es necesario expresar un concepto que el lenguaje no lo provee. Por ejemplo, Assembler no posee estructuras de control, por lo tanto debemos simularla.

4) Elegir adecuadamente un lenguaje

Si conocemos las características de los lenguajes, tenemos la posibilidad de elegir el adecuado de acuerdo al área del problema, y de esta forma reducimos el esfuerzo de codificación. Por ejemplo, si queremos programar artefáctos electrónicos utilizaremos PROLOG, en cambio si queremos programar cálculo numérico utilizaremos FORTRAN.

5) Facilitar el aprendizaje de nuevos lenguajes

Un lingüista que conoce profundamente la estructura subyacente del lenguaje natural aprende muchísimo más rápido un nuevo lenguaje o idioma que aquella persona que desconoce la estructura lingüística

6) Escoger el diseño e implementación de lenguajes 

Conocer el conjunto de símbolos que lo conforman, sus reglas sintácticas y semánticas, el significado de sus elementos y de sus expresiones  facilitará la escritura, la depuración, la compilación y el mantenimiento de un programa informático.

Bibliografía:

[1] Duden Informatik, ISBN 3-411-024-21-6

[2] Programmiersprache - Wikipedia 

otras: 

. Apuntes de la Cátedra "Conceptos y Paradigmas de los Lenguajes de Programación" de la Facultad de Informática, UNLP (Universidad Nacional de La Plata)

. Programing language concepts - Third Edition -  Carlo Ghezzi.

.Lenguaje de Programación - Wikipedia