BIENVENIDOS...

Si buscas información de este tema tan interesante como es compiladores, pues aquí puedes encontrarla, te invito a mi blog....

NOCIONES BÁSICAS GENERALES DEL COMPILADOR

-          Compilador: Es un programa que lee un programa escrito en un lenguaje, el lenguaje fuente, y lo traduce a un programa equivalente a otro lenguaje, el lenguaje objeto.

-          Intérprete: En lugar de producir un programa objeto como resultado de una traducción, un intérprete realiza las operaciones que implica el programa fuente.

-         Programa Fuente: hay miles de lenguajes fuente, desde los lenguajes de programación tradicionales, hasta los lenguajes especializados.

-          Programa Objeto: son igualmente variados, un lenguaje objeto puede ser otro lenguaje de programación o el lenguaje de máquina.

-          Lenguaje de Programación: es un conjunto de pautas o nociones que se utilizan para realizar un procedimiento o proceso.

FASES DEL COMPILADOR

-          Fase de Análisis: Tiene como finalidad almacenar la línea de código y verificarla con las pautas del lenguaje de programación.

-          Fase de Síntesis: Tiene como finalidad convertir la línea de código analizada en el lenguaje de bajo nivel enlazándola a un archivo objeto.

INTERPRETE

En ciencias de la computación, intérprete o interpretador es un programa informático capaz de analizar y ejecutar otros programas, escritos en un lenguaje de alto nivel. Los intérpretes se diferencian de los compiladores en que mientras estos traducen un programa desde su descripción en un lenguaje de programación al código de máquina del sistema, los intérpretes sólo realizan la traducción a medida que sea necesaria, típicamente, instrucción por instrucción, y normalmente no guardan el resultado de dicha traducción.

Usando un intérprete, un solo archivo fuente puede producir resultados iguales incluso en sistemas sumamente diferentes (ej. una PC y un PlayStation 3). Usando un compilador, un solo archivo fuente puede producir resultados iguales solo si es compilado a distintos ejecutables específicos a cada sistema.

Los programas interpretados suelen ser más lentos que los compilados debido a la necesidad de traducir el programa mientras se ejecuta, pero a cambio son más flexibles como entornos de programación y de puración (lo que se traduce, por ejemplo, en una mayor facilidad para reemplazar partes enteras del programa o añadir módulos completamente nuevos), y permiten ofrecer al programa interpretado un entorno no dependiente de la máquina donde se ejecuta el intérprete, sino del propio intérprete (lo que se conoce comúnmente como máquina virtual).

PROGRAMA OBJETO - PROGRAMA FUENTE

PROGRAMA OBJETO

-Es aquel programa que se encuentra en lenguaje máquina y que ya es ejecutable por esta.

-Es el resultado de traducir un programa fuente para obtener un lenguaje comprensible por la máquina.

Programación orientada a objetos (OOPS); es una técnica de programación que utiliza objetos como bloque esencial de construcción, es un tipo de programación mas cercana al razonamiento humano; surge como una solución a la programación de grandes programas, y para solventar el mantenimiento de dichas aplicaciones, ya que en la programación estructura el más mínimo cambio supone la modificación de muchas funciones relacionadas, en cambio con la OOPS solo es cuestión de añadir o modificar métodos de una clase o mejor, crear una nueva clase a partir de otra (Herencia). Dos lenguajes destacan sobre el resto para programar de esta forma, Smalltalk y C++.

*PROGRAMA FUENTE 

-Es el programa escrito en alguno de los lenguajes y que no ha sido traducido al lenguaje de la maquina, es decir el programa que no está en código de máquina y que por lo tanto no puede ser ejecutable.

-Es aquel que nos permite escribir un algoritmo mediante un lenguaje formal. Por eso al código desarrollado al programar se le llama código fuente.

FASES DE UN COMPILADOR

Las tres primeras fases de un compilador suelen agrupan en un sola fase llamada Análisis del programa a compilar y las tres ultimas en una sola fase llamada Síntesis de un programa en lenguaje maquina.

En la fase de análisis se encuentran:

Análisis Léxico: Esta fase se encarga de verificar si una cadena de entrada del código fuente pertenece o no al lenguaje, es decir se realiza un análisis símbolo a símbolo indicando el tóken para cada una de las cadenas reconocidas o un error en caso de no reconocer la cadena.

Análisis Sintáctico: En esta fase se analiza la estructura de las expresiones en base a gramáticas en base a reglas que determinar si una cadena de entrada del código fuente es valida. El  análisis que se realiza es jerárquico ya que se obtiene arboles de derivación de las mismas gramáticas especificadas en el lenguaje.

Análisis Semántico: Este análisis es mucho mas difícil de formalizar que el sintáctico ya que tiene que verificar que el árbol sintáctico tenga un significado valido dentro de las reglas  especificadas en el  lenguaje. El análisis semántico verifica que:

·         En una asignación, el tipo de la variable concuerde con el tipo de la expresión asignada.

·         Que las variables estén declaradas antes de ser usadas.

En la fase de Síntesis se encuentran las siguientes:

Generación de código intermedio: Esta fase se ocupa de generar instrucciones para la maquina virtual genéricaa partir del análisis de las primeras tres fases.

Ej.:

a=b+c
1: + b c T1
2: = a T1

Optimización: Se encarga de transformar el código intermedio en uno equivalente que tenga menos lineas de código de menor tamaño y menor tiempo de ejecución.

Ej,:

a=b+c
1: + b c a

Generación de  código objeto: Es la fase final en la que se genera el código objeto el cual utiliza el conjunto de instrucciones especifico del CPU que por lo general es código maquina o código en lenguaje ensamblador.

Ej.:

a:=b+c

LOAD B
ADD C
STORE A

SISTEMA PARA EL PROCESAMIENTO DE UN LENGUAJE

 El procesamiento de lenguajes naturales —abreviado PLN, o NLP del idioma inglés Natural Language Processing— es un campo de las ciencias de la computación, inteligencia artificial y lingüística que estudia las interacciones entre las computadoras y el lenguaje humano. El PLN se ocupa de la formulación e investigación de mecanismos eficaces computacionalmente para la comunicación entre personas y máquinas por medio de lenguajes naturales. El PLN no trata de la comunicación por medio de lenguajes naturales de una forma abstracta, sino de diseñar mecanismos para comunicarse que sean eficaces computacionalmente —que se puedan realizar por medio de programas que ejecuten o simulen la comunicación—. Los modelos aplicados se enfocan no solo a la comprensión del lenguaje de por sí, sino a aspectos generales cognitivos humanos y a la organización de la memoria. El lenguaje natural sirve solo de medio para estudiar estos fenómenos. Hasta la década de 1980, la mayoría de los sistemas de PLN se basaban en un complejo conjunto de reglas diseñadas a mano. A partir de finales de 1980, sin embargo, hubo una revolución en PLN con la introducción de algoritmos de aprendizaje automático para el procesamiento del lenguaje.

El esquema general de la mayoría de los sistemas y métodos que involucran el procesamiento de lenguaje es el siguiente:
·     Primero, el texto no se procesa directamente sino se transforma en una representación formal que preserva sus características relevantes para la tarea o el método específico (por ejemplo, un conjunto de cadenas de letras, una tabla de base de datos, un conjunto de predicados lógicos, etc.).
·     Luego, el programa principal manipula esta representación, transformándola según la tarea, buscando en ella las subestructuras necesarias, etc.
·     Finalmente, si es necesario, los cambios hechos a la representación formal (o la respuesta generada en esta forma) se transforman en el lenguaje natural.
Entre las tareas principales del procesamiento de lenguaje natural se puede mencionar:
·     Recuperación de información,
·     Interfaces en lenguaje natural,
·     Traducción automática.

TIPOS DE COMPILADORES

Compiladores cruzados: generan código para un sistema distinto del que están funcionando.

Compiladores optimizadores: realizan cambios en el código para mejorar su eficiencia, pero manteniendo la funcionalidad del programa original.

Compiladores de una sola pasada: generan el código máquina a partir de una única lectura del código fuente.

Compiladores de varias pasadas: necesitan leer el código fuente varias veces antes de poder producir el código máquina.

Compiladores JIT (Just In Time): forman parte de un intérprete y compilan partes del código según se necesitan.

Compiladores incrementales: Generan un código objeto, instrucción por instrucción cuando el usuario teclea cada orden individual.

Compilador con montador: Compila distintos módulos de forma independiente y después es capaz de aplazarlos.

Auto compilador: Compilador que está escrito en el mismo lenguaje que va a compilar.

Meta compilador: Es programa que recibe como entrada las especificaciones del lenguaje para el que se desea obtener un compilador y genera como salida el compilador para ese lenguaje.

Descompilador: Es un programa que acepta como entrada código maquina y la traduce a un lenguaje de alto nivel realizando el proceso inverso a la compilación.

Pauta de creación de un compilador: En las primeras épocas de la informática, el software de los compiladores era considerado como uno de los más complejos existentes.

Los primeros compiladores se realizaron programándolos directamente en lenguaje máquina o en ensamblador. Una vez que se dispone de un compilador, se pueden escribir nuevas versiones del compilador (u otros compiladores distintos) en el lenguaje que compila ese compilador.

HERRAMIENTAS QUE MANIPULAN PROGRAMAS FUENTES

Muchas herramientas de software que manipulan programas fuente realizan primero algún tipo de análisis. Algunos ejemplos de tales herramientas son:

1. Editores de estructuras.

Un editor de estructuras toma como entrada una secuencia de órdenes para construir un programa fuente. El editor de estructuras no sólo realiza las funciones de creación y modificación de textos de un editor de textos ordinario, sino que también analiza el texto del programa, imponiendo al programa fuente una estructura jerárquica apropiada. De esa manera, el editor de estructuras puede realizar tareas adicionales útiles para la preparación de programas. Por ejemplo, puede comprobar si la entrada está formada correctamente, puede proporcionar palabras clave de manera automática (por ejemplo, cuando el usuario escribe while, el editor proporciona el correspondiente do y le recuerda al usuario que entre las dos palabras debe ir un condicional) y puede saltar desde un begin o un paréntesis izquierdo hasta su correspondiente end o paréntesis derecho. Además, la salida de tal editor suele ser similar a la salida de la fase de análisis de un compilador.

2. Impresoras estéticas.

Una impresora estética analiza un programa y lo imprime de forma que la estructura del programa resulte claramente visible. Por ejemplo, los comentarios pueden aparecer con un tipo de letra especial, y las proposiciones pueden aparecer con una indentación proporcional a la profundidad de su anidamiento en la organización jerárquica de las proposiciones.

3. Verificadores estáticos.

Un verificador estático lee un programa, lo analiza e intenta descubrir errores potenciales sin ejecutar el programa. La parte de análisis a menudo es similar a la que se encuentra en los compiladores de optimización. Así, un verificador estático puede detectar si hay partes de un programa que nunca se podrán ejecutar o si cierta variable se usa antes de ser definida. Además, puede detectar errores de lógica, como intentar utilizar una variable real como apuntador, empleando las técnicas de verificación de tipos.

4. Intérpretes.

En lugar de producir un programa objeto como resultado de una traducción, un intérprete realiza las operaciones que implica el programa fuente. Para una proposición de asignación, por ejemplo, un intérprete podría construir un árbol como el de la figura 1 y después efectuar las operaciones de los nodos conforme “recorre” el árbol. En la raíz descubriría que tiene que realizar una asignación, y llamaría a una rutina para evaluar la expresión de la derecha y después almacenaría el valor resultante en la localidad de memoria asociada con el identificador posición. En el hijo derecho de la raíz, la rutina descubriría que tiene que calcular la suma de dos expresiones. Se llamaría a sí misma de manera recursiva para calcular el valor de la expresión velocidad*60. Después sumaría ese valor de la variable inicial. Muchas veces los intérpretes se usan para ejecutar lenguajes de órdenes, pues cada operador que se ejecuta en un lenguaje de órdenes suele ser una invocación de una rutina compleja, como un editor o un compilador. Del mismo modo algunos lenguajes de “muy alto nivel”, normalmente son interpretados, porque hay muchas cosas sobre los datos, como el tamaño y la forma de las matrices, que no se pueden deducir en el momento de la compilación.

5. Compiladores.


Tradicionalmente, se concibe un compilador como un programa que traduce un programa fuente, como FORTRAN, al lenguaje ensamblador o de máquina de algún computador. Sin embargo, hay lugares, al parecer, no relacionados donde la tecnología de los compiladores se usa con regularidad. La parte de análisis de cada uno de los siguientes ejemplos es parecida a la de un compilador convencional.a) Formadores de textos. Un formador de textos toma como entrada una cadena de caracteres, la mayor parte de la cual es texto para componer, pero alguna incluye órdenes para indicar párrafos, figuras o estructuras matemáticas, como subíndices o superíndices.b) Compiladores de circuitos de silicio. Un compilador de circuitos de silicio tiene un lenguaje fuente similar o idéntico a un lenguaje de programación convencional. Sin embargo las variables del lenguaje no representan localidades de memoria, sino señales lógicas (0 o 1) o grupos de señales en un circuito de conmutación. La salida es el diseño de un circuito en un lenguaje apropiado.c) Intérpretes de consultas. Un intérprete de consultas traduce un predicado que contiene operadores relacionales y boléanos a órdenes para buscar en una base de datos registros que satisfagan ese predicado.

ANÁLISIS LÉXICO.

FUNCIÓN DEL ANALIZADOR LÉXICO.

El analizador léxico es la primera fase de un compilador. Su principal función consiste en leer los caracteres de entrada y elaborar como salida una secuencia de componentes léxicos que utiliza el analizador sintáctico para hacer el análisis.

Como el analizador léxico es la parte del compilador que lee el texto fuente, también puede realizar ciertas funciones secundarias en la interfaz del usuario, como eliminar del programa fuente comentarios y espacios en blanco en forma de caracteres de espacio en blanco, caracteres TAB y de línea nueva. Otra función es relacionar los mensajes de error del compilador con el programa fuente.

En algunas ocasiones, los analizadores léxicos se dividen en una cascada de dos fases; la primera, llamada "examen", y la segunda, "análisis léxico". El examinador se encarga de realizar tares sencillas, mientras que el analizador léxico es el que realiza las operaciones complejas.

ASPECTO DEL ANÁLISIS LÉXICO.

Hay varias razones para dividir la fase de análisis de la compilación en análisis léxico y análisis sintáctico.

1. Un diseño sencillo es quizá la consideración más importante. Separar el análisis léxico del análisis sintáctico a menudo permite simplificar una u otra de dichas fases.
2. Se mejora la eficiencia del compilador. Un analizador léxico independiente permite construir un procesador especializado y potencialmente más eficiente para esta función. Gran parte de tiempo se consume en leer el programa fuente y dividirlo en componentes léxicos. Con técnicas especializadas de manejo de buffer para la lectura de caracteres de entrada y procesamiento de componentes léxicos se puede mejorar significativamente el rendimiento de un compilador.
3. Se mejora la transportabilidad del compilador. Las peculiaridades del alfabeto de entrada y otras anomalías propias de los dispositivos pueden limitarse al analizador léxico. 

COMPONENTES LÉXICOS, PATRONES Y LEXEMAS.

Cuando se menciona el análisis sintáctico, los términos "componente léxico"(token), "patrón" y "lexema" se emplean con significados específicos. En general, hay un conjunto de cadenas en la entrada para el cual se produce como salida el mismo componente léxico. Este conjunto de cadenas se describe mediante una regla llamada patrón asociado al componente léxico. Se dice que el patrón concuerda con cada cadena del conjunto. Un lexema es una secuencia de caracteres en el programa fuente con la que concuerda el patrón para un componente léxico.

Los componentes léxicos se tratan como símbolos terminales de la gramática del lenguaje fuente, con nombres en negritas para representarlos. Los lexemas para el componente léxico que concuerda con el patrón representan cadenas de caracteres en el programa fuente que se pueden tratar juntos como una unidad léxica.

En la mayoría de los lenguajes de programación, se consideran componentes léxicos las siguientes construcciones: palabra clave, operadores, identificadores, constante, cadenas literales y signos de puntuación, como paréntesis, coma y punto y coma.

ATRIBUTOS DE LOS COMPONENTES LÉXICOS.

Cuando concuerda con un lexema más de un patrón, el analizador léxico debe proporcionar información adicional sobre el lexema concreto que concordó con las fases del compilador.

El analizador léxico recoge información sobre los componentes léxicos en sus atributos asociados. Los componentes léxicos influyen en las decisiones del análisis sintáctico, y los atributos, en la traducción de los componentes léxicos. En la practica, los componentes léxicos suelen tener un solo atributo – un apuntador a la entrada de la tabla de símbolos donde se guarda la información sobre el componente léxico; el apuntador se convierte en el atributo del componente léxico. A efectos de diagnóstico, puede considerarse tanto el lexema para un identificador como el número de línea en el éste se encontró por primera vez. Estos dos elementos de información se pueden almacenar en la entrada de la tabla de símbolos para el identificador.

PARTES DE UN PROGRAMA FUENTE.

Las partes de un programa fuente son: Cabecera, Declaraciones, y partes de sentencias.

CABECERA: La cabecera de un programa consiste en el nombre del programa que se realiza.

La cabecera de un subprograma incluye, como mínimo; el tipo de subprograma (procedimiento o función) y su nombre, las funciones requieren o necesitan que se rectifique el tipo que devuelven.

DECLARACIONES: La sección de declaraciones incluye las definiciones de variables y constantes, etiquetas, tipos y subprogramas.

SENTENCIAS: Es la parte donde se realizan todas las operaciones que el programa debe de ejecutar.

ANÁLISIS SINTACTICO

FUNCIÓN DEL ANÁLISIS SINTÁCTICO

El analizador sintáctico obtiene una cadena de componentes léxicos del analizador léxico, y comprueba si la cadena puede ser generada por la gramática del programa fuente.

Tipos generales de analizadores sintácticos para gramáticas:
a) Análisis sintáctico descendente. Construye árboles de análisis sintáctico desde arriba (raíz) hacia abajo (hojas). El análisis se realiza de lo general a lo particular.
b) Análisis sintáctico ascendente. Construyen árboles de análisis sintáctico comenzando en las hojas y suben hacia la raíz. El análisis se realiza de lo particular a lo general.
En ambos casos, se examina la entrada al analizador léxico de izquierda a derecha, un símbolo a la vez.

GRAMÁTICAS INDEPENDIENTES DE CONTEXTO

Una gramática describe de forma natural la estructura jerárquica de muchas construcciones de los lenguajes de programación. Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la síntaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada determinen como puede ser generada desde la gramática
Consta de: 
• TERMINALES. Símbolos básicos con que se forman las cadenas. Para un lenguaje de programación, cada palabra clave/reservada es un terminal.

• NO TERMINALES. Son variables sintácticas que denotan conjuntos de cadenas (identificadotes o variables). Los no terminales definen conjuntos de cadenas que ayudan a definir el lenguaje generado por la gramática. Imponen una estructura jerárquica sobre el lenguaje que es útil tanto para el análisis sintáctico como para la traducción.

• UN SÍMBOLO INICIAL. En una gramática, es un no terminal que representa un conjunto de cadenas.

• PRODUCCIONES. Especifican cómo se pueden combinar los terminales y no terminales para formar cadenas. Cada producción consta de un No terminal (símbolo inicial), seguido por una flecha o símbolo de asignación, seguida por una cadena de no terminales y terminales. 

ESCRITURA DE UNA GRAMÁTICA

Las gramáticas describen la mayoría de las sintaxis de los lenguajes de programación.Toda construcción que se pueda describir mediante una expresión regular también se puede describir por medio de una gramática.
Por ejemplo, para la expresión regular (a|b)* abb
Y la gramática: A0 → a A0 | b A0| b A1 
A1 → b A2
A2 → bA3 
A3 → є

ANÁLISIS SINTÁCTICO DESCENDENTE

Se considera un intento de encontrar una derivación por la izquierda para una cadena de entrada.También se puede considerar como un intento de construir un árbol de análisis sintáctico para la entrada comenzando desde la raíz y creando nodos del árbol en orden previo.

ANÁLISIS SINTÁCTICO ASCENDENTE

El análisis sintáctico ascendente intenta construir un árbol para la cadena de entrada que comienza por las hojas (el fondo) y avanza hacia la raíz (la cima).

ANÁLISIS SINTÁCTICO POR PRECEDENCIA DE OPERADORES

Para una pequeña clase de gramáticas se puede construir con facilidad a mano eficientes analizadores sintácticos ascendentes.Estas gramáticas, por precedencia de operadores, tienen la propiedad de que ningún lado derecho de la producción es є ni tiene 2 terminales adyacentes.
Una gramática con esta última propiedad de denomina gramática de operadores.

ANALIZADORES SINTÁCTICOS IZQUIERDA-DERECHA

Es una técnica eficiente de análisis sintáctico ascendente que se puede utilizar para analizar una amplia clase de gramáticas independientes de contexto, denominada Análisis sintáctico LR(k)
L es por el examen de la entrada de izquierda a derecha (left to right)
R por construir una derivación por la derecha (right most derivation) en orden inverso.
K por el número de símbolos de entrada de examen por anticipado utilizados para tomar decisiones del análisis sintáctico. Cuando se omite, se asume que k es 1.
Este análisis es atractivo por varias razones:
• Reconocen prácticamente todas las construcciones de los lenguajes de programación para los que se pueden escribir gramáticas independientes del contexto.
• Puede detectar un error sintáctico tan pronto como sea posible hacerlo en un examen de izquierda a derecha de la entrada.

USO DE GRAMÁTICAS AMBIGUAS

Gramática ambigua es aquella que produce más de un árbol de análisis sintáctico para alguna frase, es decir, una gramática ambigua es la que produce más de una derivación por la izquierda o por la derecha para la misma frase.Algunos tipos de gramáticas ambiguas son útiles en la especificación e implementación de lenguajes. Se utiliza para el aislamiento de construcciones sintácticas habituales para optimación en casos especiales.
Una Sentencia es ambigua si hay más de una derivación distinta. Si una sentencia es ambigua, el árbol de análisis sintáctico no es único; podemos crear más de un árbol de análisis sintáctico para la misma sentencia.Con una gramática ambigua se pueden especificar las construcciones de casos especiales añadiendo cuidadosamente nuevas producciones a la gramática. Las construcciones ambiguas se deben usar raramente y de una manera estrictamente controlada, pues de lo contrario no se puede reconocer con seguridad el lenguaje que reconoce el analizador.