Autómata finito

Una expresión regular es la forma de describir un lenguaje , la forma de construirlo es por medio de un diagrama que contenga la información necesaria para analizar la cadena, este diagrama tendrá forma de grafo dirigido.

La cadena será leida de izquierda a derecha, para dar a conocer que la cadena es aceptada, se debe establecer un estado de aceptación y también se deben establecer estados de no aceptación para determinar el análisis de las cadenas que no permanezcan al lenguaje.

Analizar una cadena es recorrer los caminos del grafo; dependiendo del carácter que esta siendo analizado se elige un camino a recorrer. Cuando se acepta una cadena como miembro del lenguaje se llega a un estado de aceptación (encerados en un circulo) por lo que, todos los caminos que lleven a un estado de aceptación constituyen palabras pertenecientes a el lenguaje.

Reconocimiento de los componentes léxicos

Todas las expresiones se consideran posibles tokens. El token manager consume el numero máximo de caracteres de la cadena de entrada que coincida con alguna de las expresiones regulares. Esto es, el token manager prefiereel match mas largo que sea posible. Si existieran múltiples matches (de la misma longitud), se elige la expresión regular que ocurre antes en el archivo de la gramática.

Luego de reconocer una expresión regular, se ejecuta la acción léxica asociada, si es que la hay. Todas las variables y métodos declarados en el token manager están disponibles para ser usadas, además de otras variables y métodos adicionales. Inmediatamente ejecutadas las acciones, el token manager cambia su estado al estado de la necesidades del usuario.

Especificaciones De Componentes Léxicos

Las especificaciones del componente léxico son:

El alfabeto; son representados por el conjunto finitos de símbolos.
o Cadena sobre un alfabeto, que es la secuencia finita de los símbolos de este alfabeto.
o Cadena vacía
o Operacionales con cadenas; concatenación y exponenciación
o Lenguaje; representado por el conjunto de cadenas sobre un alfabetoOperaciones de lenguaje; la unión, concatenación, cerradura de Kleene (cierre *)y cerradura positiva (Cierre +)

Manejo de buffer de entrada

Utiliza 2 buffer de entrada resultara útil cuando es necesario un pre-análisis en la entrada para identificar los componentes léxicos, después se introducen algunas técnicas básicas para encontrar la velocidad del analizador léxico, como es el uso de centinelas que sirven para marcar el final de buffer, hay tres métodos general de implantar un léxico:

· Utilizar un generador de analizadores léxicos, como el compilador LEX
· Escribir el analizador léxico en un lenguaje convencional de programación
· Escribir léxico en lenguaje ensamblador y manejarlo explícitamente lectura de entrada.

Parejas de buffer

1. Texto de lenguaje fuente
2. Traductor
3. Texto de lenguaje traductor
4. Programa objeto
5. Compilador
6. Programa fuente
7. Mensaje error
8. Programa fuente
9. Analizador léxico
10. Analizador sintáctico
11. Analizador semántico
12. Generación del código intermedio
13. Optimización de código
14. Generador del código
15. Programa objeto
16. Manejo de errores
17. Manejo de tabla de símbolos
18. Analizador léxico
19. Analizador sintáctico
20. Tabla de símbolos
21. Componente léxico

Funcionamiento

El analizador léxico es la primera fase de un compilador, su funcionamiento consiste en llevar las primeras caracteres de entrada y elaborar como salida una secuencia de caracteres léxicos que utilizan un analizador sintáctico pasar hacer el análisis.

Existen 4 funciones principales para un analizador léxico, grafico que va hallando cada token en forma consecutiva, esta pueden ser:

· Utilidades de caracteres y manejo de líneas
· Prueba de predicado
· Acciones
· Errores

ANÁLISIS LÉXICO

3.1 Definición

Se encarga de buscar los componentes léxicos o palabras que componen el programa fuente , según las reglas de entrada.

En la fase de análisis léxico se leen los caracteres del programa fuente y se agrupan en cadenas que representan los componentes léxicos, cada componente léxico es una secuencia lógicamente coherente de caracteres relativa a un identificador, una palabra reservada, un operador o un carácter de puntuación. A la secuencia de caracteres que representa el componente léxico se le llama lexema. En el caso de los identificadores creados por el programador no solo se genera un componente léxico, sino que se genera otro lexema en la tabla de símbolos.

Forma de Backus-Naur

EL Backus-Naur form (BNF) también conocido como Backus-Naaur formalism,Backus normal form o Panini-Backus Form; es una meta sintaxis usada para expresar gramáticas libres de contexto: es decir, una manera formal de describir lenguajes formales. El BNF se utiliza extensamente como notación para las gramáticas de los lenguajes de programación de la computadora, de los sistemas de comando y de los protocolos de comunicación, así como una notación para representar partes de las gramáticas de la lengua natural.

Herramientas para la construcción de compiladores

Se muestran algunas herramientas disponibles que pueden utilizarse para la realización del proyecto de compiladores. Todas las herramientas aquí expuestas funcionan bajo Windows.


· BISON
· COCO/R
· FLEX
· LEX


· SDGLL1
· TS 2006
· TS
· TS-OO
· YACC

Agrupamiento de las fases

Un compilador opera en fases, de las cuales transforma el programa fuente de una representación en otra. Dentro de las tres primeras fases, que forman la mayor parte de análisis de un compilador se analiza la administración, el manejo de errores y la fase de análisis .
· Administración de tabla de símbolos es la función esencial de un compilador registrando los identificadores utilizados en el programa fuente y reunir información sobre los distintos atributos de cada identificador. Estos atributos pueden proporcionar información sobre la memoria asignada a un identificador. Es la estructura la tabla de símbolos de datos que contiene un registro por cada identificador, con los campos para los atributos de un identificador.

Las faces restantes introducen información sobre los identificadores en la tabla de símbolos y después la utilizan de varias formas.

· Detección e información de errores en cada una de las frases se puede encontrar errores, sin embargo ,después de detectar el error , se debe tratar de alguna forma ese error , para poder continuar con la compilación. Las fases de análisis sintáctico y semántico por lo general manejan una gran proporción de los errores detectables por el compilador. La fase léxica detecta los errores donde los caracteres restantes de la entrada no forman ningún componente léxico del lenguaje. Los errores donde la cadena de componentes léxicos violan las reglas de estructura del lenguaje son determinados por la fase del análisis sintáctico. Durante el análisis semántico el compilador intenta detectar construcciones que tengan la estructura sintáctica correcta, pero que no tenga significado para la operación implicada.

· La fase de análisis conforme avanza la traducción, la representación interna del programa fuente que tiene el compilador se modifica.

Fases de un compilador

Como hemos visto un compilador es un programa que lee un escrito, el cual el lenguaje fuente lo traduce a un programa equivalente en otro lenguaje, el lenguaje objeto. Como parte importante de este proceso de traducción, el compilador informa a su usuario de la presencia de errores en el programa fuente si es que las hubiera.

La diversidad de compiladores puede parecer abrumadora, ya que hay miles de lenguajes fuente, desde los lenguajes de programación tradicionales, como ejemplo el FROTRAN o PASCAL, y los lenguajes especializados. Los lenguajes objeto son igualmente variados; un lenguaje objeto puede ser otro lenguaje de programación o el lenguaje maquina de cualquier computador entre un microprocesador y un supercomputador. Al existir una complejidad por la clasificación de los compiladores, las tareas básicas que debe realizar cualquier compilador son esencialmente las mismas. Al comprender las tareas realizadas, se pueden construir compiladores para una gran diversidad de lenguajes fuentes y maquinas objeto utilizando las mismas técnicas básicas.

Análisis del programa fuente

El programa compilador traduce las instrucciones en un lenguaje de alto nivel a instrucciones que la computadora puede interpretar y ejecutar. Para cada lenguaje de programación se requiere un compilador separado. El compilador traduce todo el programa antes de ejecutarlo. Ya que los compiladores son programas de traducción insertados en la memoria por el sistema operativo para convertir programas de cómputo en pulsaciones electrónicas ejecutables.los compiladores pueden ser de:

· Una sola pasada
· Pasada múltiples
· Optimación
· Compiladores incrementales
· Ensamblador
· Compilador cruzado
· Compilador con montador
· Autocompilador
· Metacompilador
· Descompilador

Compiladores

Un traductor es cualquier programa que toma como entrada un texto escrito en un lenguaje, llamado fuente y da como salida otro texto en un lenguaje, denominado objeto.

Un compilador no es un programa que funciona de manera aislada, sino que necesita de otros programas para conseguir su objetivo: obtener un programa ejecutable a partir de un programa fuente en un lenguaje de alto nivel. Algunos de esos programas son el preprocesador, el linker, el depurador y el ensamblador. El preprocesador se ocupa (dependiendo del lenguaje) de incluir ficheros, expandir macros, eliminar comentarios, y otras tareas similares. El linker se encarga de construir el fichero ejecutable añadiendo al fichero objeto generado por el compilador las cabeceras necesarias y las funciones de librería utilizadas por el programa fuente. El depurador permite, si el compilador ha generado adecuadamente el programa objeto, seguir paso a paso la ejecución de un programa. Finalmente, muchos compiladores, en vez de generar código objeto, generan un programa en lenguaje ensamblador que debe después convertirse en un ejecutable mediante un programa ensamblador.

1.2 Traductores, ensambladores y compiladores

Traductores de programas
Los traductores son un tipo de programas cuya función es convertir el código de un lenguaje en otro. Por ejemplo un compilador, que traduce código fuente en código objeto. Existen distintos tipos de traductores, entre ellos destacan:

Ensambladores
Preprocesadores
Intérpretes
Compiladores

Ensambladores
Es un tipo de traductor que convierte programas escritos en lenguaje ensamblador en programas escritos en código máquina.

Preprocesadores
Traduce un lenguaje de alto nivel a otro, cuando el primero no puede pasar a lenguaje máquina directamente.

Intérpretes
Se trata de traductores-ejecutores ya que con cada instrucción realizan un proceso triple de lectura-traducción-ejecución. Son relativamente lentos, pero muy buenos para la depuración de programas.

CompiladoresEs el tipo de traductor más conocido. Se trata de un programa que traduce código fuente escrito en un lenguaje de alto nivel (Pascal) en código máquina (no siempre). Son más rápidos que los intérpretes pero presentan mayor dificultad a la hora de detectar errores.

1.1. Lenguaje de programación

Un lenguaje de programación es un lenguaje que puede ser utilizado para controlar el comportamiento de una máquina, particularmente una computadora. Consiste en un conjunto de símbolos y reglas sintácticas y semánticas que definen su estructura y el significado de sus elementos y expresiones.

Aunque muchas veces se usa lenguaje de programación y lenguaje informático como si fuesen sinónimos, no tiene por qué ser así, ya que los lenguajes informáticos engloban a los lenguajes de programación y a otros más, como, por ejemplo, el HTML (lenguaje para el marcado de páginas web).

Un lenguaje de programación permite a uno o más programadores especificar de manera precisa: sobre qué datos una computadora debe operar, cómo deben ser estos almacenados, transmitidos y qué acciones debe tomar bajo una variada gama de circunstancias. Todo esto, a través de un lenguaje que intenta estar relativamente próximo al lenguaje humano o natural, tal como sucede con el lenguaje Léxico. Una característica relevante de los lenguajes de programación es precisamente que más de un programador puedan tener un conjunto común de instrucciones que puedan ser comprendidas entre ellos para realizar la construcción del programa de forma colaborativa.

Los procesadores usados en las computadoras son capaces de entender y actuar según lo indican programas escritos en un lenguaje fijo llamado lenguaje de máquina. Todo programa escrito en otro lenguaje puede ser ejecutado de dos maneras:

Mediante un programa que va adaptando las instrucciones conforme son encontradas. A este proceso se lo llama interpretar y a los programas que lo hacen se los conoce como intérpretes. Traduciendo este programa al programa equivalente escrito en lenguaje de máquina. A ese proceso se lo llama compilar y al traductor se lo conoce como un malhecho compilador.

Clasificación de los lenguajes de programación
Los lenguajes de programación se determinan según el nivel de abstracción, Según la forma de ejecución y Según el paradigma de programación que poseen cada uno de ellos y esos pueden ser:
Según su nivel de abstracción

Lenguajes de bajo nivel
Los lenguajes de bajo nivel son lenguajes de programación que se acercan al funcionamiento de una computadora. El lenguaje de más bajo nivel es, por excelencia, el código máquina. A éste le sigue el lenguaje ensamblador, ya que al programar en ensamblador se trabajan con los registros de memoria de la computadora de forma directa.

Lenguajes de medio nivel
Hay lenguajes de programación que son considerados por algunos expertos como lenguajes de medio nivel (como es el caso del lenguaje C) al tener ciertas características que los acercan a los lenguajes de bajo nivel pero teniendo, al mismo tiempo, ciertas cualidades que lo hacen un lenguaje más cercano al humano y, por tanto, de alto nivel.

Lenguajes de alto nivel
Los lenguajes de alto nivel son normalmente fáciles de aprender porque están formados por elementos de lenguajes naturales, como el inglés. En BASIC, el lenguaje de alto nivel más conocido, los comandos como "IF CONTADOR = 10 THEN STOP" pueden utilizarse para pedir a la computadora que pare si CONTADOR es igual a 10. Por desgracia para muchas personas esta forma de trabajar es un poco frustrante, dado que a pesar de que las computadoras parecen comprender un lenguaje natural, lo hacen en realidad de una forma rígida y sistemática.

Según la forma de ejecución

Lenguajes compilados
Naturalmente, un programa que se escribe en un lenguaje de alto nivel también tiene que traducirse a un código que pueda utilizar la máquina. Los programas traductores que pueden realizar esta operación se llaman compiladores. Éstos, como los programas ensambladores avanzados, pueden generar muchas líneas de código de máquina por cada proposición del programa fuente. Se requiere una corrida de compilación antes de procesar los datos de un problema.

Los compiladores son aquellos cuya función es traducir un programa escrito en un determinado lenguaje a un idioma que la computadora entienda (lenguaje máquina con código binario).
Al usar un lenguaje compilado (como lo son los lenguajes del popular Visual Studio de Microsoft), el programa desarrollado nunca se ejecuta mientras haya errores, sino hasta que luego de haber compilado el programa, ya no aparecen errores en el código


Lenguajes interpretados

Se puede también utilizar una alternativa diferente de los compiladores para traducir lenguajes de alto nivel. En vez de traducir el programa fuente y grabar en forma permanente el código objeto que se produce durante la corrida de compilación para utilizarlo en una corrida de producción futura, el programador sólo carga el programa fuente en la computadora junto con los datos que se van a procesar. A continuación, un programa intérprete, almacenado en el sistema operativo del disco, o incluido de manera permanente dentro de la máquina, convierte cada proposición del programa fuente en lenguaje de máquina conforme vaya siendo necesario durante el proceso de los datos. No se graba el código objeto para utilizarlo posteriormente.
La siguiente vez que se utilice una instrucción, se le debe interpretar otra vez y traducir a lenguaje máquina. Por ejemplo, durante el procesamiento repetitivo de los pasos de un ciclo, cada instrucción del ciclo tendrá que volver a ser interpretado cada vez que se ejecute el ciclo, lo cual hace que el programa sea más lento en tiempo de ejecución (porque se va revisando el código en tiempo de ejecución) pero más rápido en tiempo de diseño (porque no se tiene que estar compilando a cada momento el código completo). El intérprete elimina la necesidad de realizar una corrida de compilación después de cada modificación del programa cuando se quiere agregar funciones o corregir errores; pero es obvio que un programa objeto compilado con antelación deberá ejecutarse con mucha mayor rapidez que uno que se debe interpretar a cada paso durante una corrida de producción.

Según el paradigma de programación
Un paradigma de programación representa un enfoque particular o filosofía para la construcción del software. No es mejor uno que otro sino que cada uno tiene ventajas y desventajas. También hay situaciones donde un paradigma resulta más apropiado que otro.

Atendiendo al paradigma de programación, se pueden clasificar los lenguajes en :
Lenguajes imperativos
BASIC
C
C++
Java
C#
Perl


Lenguajes Funcionales

Puros:
§ Haskell
§ Miranda
Híbridos:
§ Lisp
§ Scheme
§ Ocaml
§ Standard ML
§ ML
§ Scala


Lenguajes Lógicos

Prolog


Lenguajes orientados a objetos

Action
Script
Ada
C++
C#
VB.NETjuio
Visual
FoxPro
Clarion
Delphi
Harbour
Eiffel
Java
JavaScript
Lexico (en
castellano)
Objective-C
Ocaml
Oz
Perl
(soporta herencia múltiple)
PHP (en su versión 5)
Python
Ruby
Smalltalk
Magik
(SmallWorld)
Algunos lenguajes de programación
ABAP
ABC
ActionScript
Ada
Afnix
ALGOL
APL
ASP
ASP.NET
AWK
B
BASIC
Batch
BCPL
Befunge
Boo
C
C++
C#
Caml
Clipper
CLIPS
CLU
COBOL
CORAL
D
Delphi
DIV
Dylan
Eiffel
Erlang
Ensamblador
Extended
ML
Euphoria
Fénix
Flow-Matic
Forth
FORTRAN
FP
Gambas
GML
GRAFCET
Haskell
Icon
Inform
INTERCAL
ISWIM
J
Java
JavaScript
Joy
KWC
Ladder
Letra
Lexico
Lingo
Lisp
Logo
Lua
MAGIC
Mainsail
Mesa
Miranda
ML
Modula
Modula-2
Modula-3
Natural
NetREXX
Oberon
Object REXX
Objective-C
Ocaml
Occam
Oz
Pascal
Parlog
Perl
PHP
PL/1
Plankalkül
PostScript
PowerBuilder
Prolog
Python
R
Rapid
REXX
RPN
RPG
Ruby
Sail
Sather
Scheme
Scriptol
Seed7
Self
Sh
Simula
Smalltalk
Snobol
SPARK
Squeak
SR
Standard
ML
TI-Basic
TCL
VBA
Visual
Basic
Visual C++
Visual DialogScript
Visual Foxpro
XBase++
Yurix

Compiladores

1. Elementos de programación de sistemas
1.1 Lenguajes de programación
1.2 Traductores, ensambladores, interpretes y compiladores

2. Introducción a los compiladores
2.1 Compiladores
2.2 Análisis del programa fuente
2.3 Fases del compilador
2.4 Agrupamiento de la fases
2.5 Herramientas para la construcción de compiladores
2.6 Forma de Backus-naur

3. Análisis léxico
3.1 Definición
3.2 Funcionamiento
3.3 Manejo de Buffers de entrada
3.4 Especificación de componentes léxicos
3.5 Reconocimiento de componentes léxicos
3.6 Autómatas finitos
3.7 Paso de una expansión regular a un AF
3.8 Lenguajes para la especificación de analizador léxico
3.9 Diseño de un generador de analizador léxico

4. Análisis sintáctico
4.1 Función del analizador sintáctico
4.2 Gramática libre de contexto
4.3 Escritura de una gramática
4.5 Análisis sintáctico descendente (Top-Down)
4.6 Análisis sintáctico ascendente (Bottom-up)
4.7 Analizador L-R
4.8 Construcción de gráficas y tablas de sintaxis
4.9 Manejo de errores sintácticos
4.10 Generadores de analizadores sintácticos

5. Análisis semántico
5.1 Definición semántica
5.2 Gramáticas ambiguas y reglas de desambieguedad
5.3 Detección de errores
5.4 Definición y uso de estructura de datos
5.5 Tabla de símbolos
5.6 Sistemas y conversiones de tipos
5.7 Estrategias para asignación de memoria

6. Generación de código intermedio
6.1 Función de la generación de código intermedio
6.2 traducción dirigida por la sintaxis
6.2.1 Arboles sintácticos
6.2.2 Notación postfija
6.2.3 Código de tres direcciones
6.3 Asociatividad izquierda y derecha
6.4 Notación polaca
6.4.1 Expresiones aritméticas