Requisitos: saber sobre Autómatas, un lenguaje de programacion como java, o c# o el que gustes y tener mucha paciencia.
Manual básico para desarrollar un compilador.
En esta primera versión explicare de manera básica, la forma más sencilla para comenzar con tu compi
Comenzando por su primer etapa.
«El Analizador Léxico» —>»AL»
-.Esta es la primer etapa que tendrás que resolver al lidiar con el desarrollo del compi el «AL» es el que se encarga de reconocer las palabras, comandos y todas esas líneas de código que podrá reconocer tu compilador, así como cualquier lenguaje de programación reconoce sus comandos, pues lo mismo pasa con tu compi, y es en esta etapa donde se definirá tu programa.
-.ejemplo: tal vez tu compi reconocerá palabras como gato o perro, o palabras con una estructura definida como asd234_24f; que conste de 3 letras,3 números, 1 guion bajo, 2 numeros y 1 letra al final, pues tu debes definir eso, definir que palabras(comandos) reconocerá tu compi,
-.para comenzar a definir lo que será reconocido por tu compi, existen algunas herramientas que son de mucha ayuda, los Autómatas, en si son la manera grafica de la estructura del lenguaje que reconocerá tu compi, (si no sabes de autómatas no continúes leyendo puesto que primero debes saber usarlos)
-.ejemplo:(st= estado, S= símbolo o carácter) Aquí será un autómata que reconozca una palabra(con palabra me refiero en dado caso a un identificador, palabra reservada, numero, o cualquier comando que tu compi reconocerá en este caso será un identificador que obligatoriamente comience con «a», después una «b» después 1 o mas números(representare con la letra d=digito), y termine con una o mas letras «a» esto seria una estructura del tipo: «ab124a» o «ab1aaaa»,algo asi : )
En el autómata de arriba dice que inicia en el estado st0, si se recibe una letra «a» entonces pasa al st1, si no obviamente será un error el cual representaremos con el numero 200(numero que se me pego la gana poner 🙂 puede ser cualquier numero en este caso el 200 para mí significa carácter no valido en la estructura que se está leyendo), estando en el st1, si se recibe una letra «b» pasa al st2, si no igual marca error 200, en el st2 si se recibe un digito, pasa al st3(ojo aquí hay un ciclo estando en el st3, si se recive otro digito, se que en el mismo st3, si se recibe una letra «a» pasa al st4 y si no, pues marca error 200, o si pasa al st4 pasa lo mismo que antes, hay otro ciclo, estando en el estado st4 mientras en carácter leído sea la letra «a» entonces permanecerá en el st4, si es otro carácter que no sea «a» ósea OC=otro carácter entonces pasa al st5 que en este autómata será nuestro estado final, que indicara que hasta ese punto, se termina la estructura de nuestro identificador de manera correcta.
—————————————————————————————————-
Otra herramienta es la matriz de transición del autómata, esta representa en forma de tabla los estados del autómata, para cada carácter o símbolo reconocido por tu lenguaje.
-.ejemplo:(en el siguiente ejemplo de matriz de transición interpretamos que mi autómata de mi analizador léxico del compi solo reconocerá los caracteres(a,b,D(de digito) y OC=cualquier otro carácter provocara un error), con eso tenemos la siguiente tabla.
| |
A |
B |
Dig |
OC |
| St0 |
St1 |
200 |
200 |
200 |
| St1 |
200 |
St2 |
200 |
200 |
| St2 |
200 |
200 |
St3 |
200 |
| St3 |
St4 |
200 |
St3 |
200 |
| St4 |
St4 |
-1 |
-1 |
-1 |
Bien la siguiente tabla se lee así : igual que el autómata, ósea si estoy en st0 y recibo «a» pues pasa al “st1” por eso lo pongo abajo de «a», si estoy en st0 y recibo una «b» pues como dije antes el primer carácter tiene que ser una «a» y como es una «b» pues es error, como dije arriba para mi pondré 200 para representar mi error(en autómatas mas grandes ocuparas mas tipo de errores posiblemente^^), y así sucesivamente con todos los demás, solo revisa el autómata y ve llenando la tabla en el caso de estar en st4 si recibo una «a» se queda en st4 de nuevo pero si recibo cualquier otra cosa que no sea «a» entonces terminara de leer la cadena de texto y marcara estado final o de acepta con en este caso representado con un «-1», (normalmente cuando es un autómata chico como ese tipo seria, que cuando este en st4 y se recibe una «a» en ves de pasar de nuevo a st4, seria pasar a st4 y al mismo tiempo ser estado final, algo como st4 a=st4 y -1, entonces b.d,oc serian error 200. por qué?, simple cuando es un autómata chico solo se analiza una palabra regularmente disiento de mientras lea una «a» está bien pero si lee otra cosa entonces estaría mal toda la cadena, en el ejemplo que puse lo manejo como si no es «a» entonces se termina y está bien porque está pensado para un texto largo compuesto de muchas palabras con eso da para analizar una parte de la cadena y si detecta estado terminal en una parte pues, el texto que resta lo toma como una nueva cadena y la comienza a analizar para saber qué es lo que sigue, claro eso sería con un autómata mas complejo, esto es solo una idea, sin embargo mas
adelante pondré un autómata de un analizador léxico grande para vean a que me refiero, en el autómata grande después de el inicio dependiendo que carácter o símbolo sea el que se está leyendo el autómata puede tomar un camino para evaluar un identificador o un numero con decimal por ejemplo, para eso serviría manejar el autómata como el que pongo arriba con un final abierto para que al detectar un estado de aceptación en una parte, se reinicie y comience a analizar la parte que sigue e identificar que será de otra manera si se lee un error pues ya no seguirá analizando la demás parte(claro se puede poner condiciones para que si lo analice, pero para complicarnos la vida, se que en alguien momento se confundirían como me paso a mí, aunque parece algo simple no lo subestimen xD) )
—————————————————————————————————
En esta etapa del analizador léxico se manejan ciertas palabras como:
-.Tokens
-.Lexema
-.Patrón
-.Atributos
-.ER(Expresiones Regulares)
———————————————————————
¿Qué significan?
>Los token son la palabra con la que reconocemos algo.
>Lexema son las partes que abarca un token.
>Patrón es la estructura que debe tener un lexema: ).
>ER es la forma o nomenclatura con la que se escribe un patrón.
No se entendió? jeje es algo como cuando vimos teoría de conjuntos.
-.ejemplo es digito={0,1,2,3,4,5,6,7,8,9}, tienes que 0,1,2,3,4,5,6,7,8,9 pertenecen al conjuto digito.
otro ejemplo: letra={a,b,c,d,e,f,…….w,x,y,z} Tenemos que tanto la «a» como la «b» y las demas letras pertenecen al conjunto letra. Ahora, si tengo remplaza la palabra conjunto por token y elementos por lexema me queda que 0.1,2,3,4,5,6,7,8 son el lexema del token digito 🙂 quedo mas claro?.
También tenemos que a,b,c,d y todas son lexema del token letra.
Cuando nuestro compilador lea un carater que por ejemplo «A» o «7» no le importara como se llama, le importara que es, en este caso se detectara que es una letra y un numero.
Un ultimo ejemplo: Si nuestro analizador lexico detectara nombre de Identificadores (por ejemplo cuando programamos nosotros ponemos Int num; en este caso «num es un identificador que es un nombre de una variable ok, pues este nombre de variable tiene una patrón(ósea una estructura)
si revisamos las reglas para nombrar una variable, dice lo siguiente
-.el nombre debe comenzar con letra o como guion bajo»
-.después puede contener varias letras o guion bajo o numeros
-.el nombre de la variable se termina cuando tenga algo que no sea letra o numero o guion bajo
-.ejemplo: adf23_asd; o _asd23; )
Con respecto a eso podemos hacer:
1-.Definir el token
2-.Definir el lexema(no tanto como definir al final lexema son todas las combinaciones con respecto al patrón que tenga el token)
3-.Definir el patrón del lexema
4-.Escribir el patrón del lexema con Expresiones Regulares
5-.El autómata
6-.La tabla de transición.
-.Comenzamos ======================================
—————————————————
1-.===Definir token===
Nuestro token se llamara Identificador
Token = Identificador
—————————————————
2-.===Lexema=======
El lexema en si no se define, simplemente se mira y se dice si ese lexema corresponde al token que nosotros estamos programando.
—————————————————
3-.===Patron========
Bien como mencione el patron es la estructura que dira si un lexema corresponde o no a un token
nuestro patron para el lexema de Identificador sera
1-. Comienza con letra o guion bajo
2-. Despues pueden ir varias letras, guion bajo o numeros
3-. si esta algo que no sea lo mencionado en el paso 2 entonces hasta ese lugar abarcara nuestro identificador
—————————————————
4-.===Escribir el patron con una Expresion Regular : )====
-.la ER seria: ERIdentificador = [A-Za-z_]([\w])* o [A-Za-z_]([A-Za-z0-9_])*
—————————————————
5-.===Autómata de un Identificador===
——Letra=L, gb(guion bajo), #(digito),OC(otro caracter), -#(estado de aceptacion)
6-. ======Tabla de transicion del Automata==========
——st#(estado al que pasara), 200(mi error de caracter erroneo, o se esperaba algo que no es lo que esta xD) el estado final -#(-1 ejemplo) no se representa en la tabla, como otro estado mas.
| |
0 |
1 |
2 |
3 |
|
| |
L |
gb |
# |
OC |
|
| St0 |
St1 |
St1 |
200 |
200 |
0 |
| St1 |
St2 |
St2 |
200 |
200 |
1 |
| St2 |
St2 |
St2 |
St2 |
-1 |
2 |
—————————————————–
Bien, ya tenemos nuestro Autómata y nuestra tabla de transición : ), pero… que hago con eso D:?
A programar ^^
YA D:? claro, obviamente cuando programen para Tabla del Autómata de Analizador léxico del Compilador de verdad 😀 tardaran mucho en esa parte del llenado de la creación del autómata y el rellenado de la tabla pero en este ejemplo esta listo : ). Como se programa? pues eso ya les toca a ustedes^^….es broma vamos por partes de la programación de una Matriz 😀
Primero se manejaran vario métodos.
Antes del análisis poner la tabla del autómata en un arreglo : )
matriz int [][]=int [4][3];
Relleno la matriz con los datos que ya tenia.
| |
0 |
1 |
2 |
3 |
|
| |
L |
gb |
# |
OC |
|
| St0 |
St1 |
St1 |
200 |
200 |
0 |
| St1 |
St2 |
St2 |
200 |
200 |
1 |
| St2 |
St2 |
St2 |
St2 |
-1 |
2 |
——————y queda así : )
matriz[0][0]=1;matriz[0][1]=1;matriz[0][2]=200;matriz[0][3]=200;
matriz[1][0]=2;matriz[1][1]=2;matriz[1][2]=2; matriz[1][3]=200;
matriz[2][0]=2;matriz[2][1]=2;matriz[2][2]=2; matriz[2][3]=-1;
——————–
1-.Lo que se hará es que se tomara todo el texto
2-.Se pasara todo a una variable tipo string ejemplo String cadt;
4-.Eliminar comentarios, delimitadores (espacios, símbolos de puntación, fin de línea)
nota: la forma en que eh manejado todo es pensando en autómata complejo, que analizwn muchas cosas por lo que algunas cosas que eh manejado si las aplican para resolver ejemplo autómatas sencillos se podrían confundir un poco, por eso deben saber manejar autómatas y tablas almenos por ejemplo en un autómata sencillo de análisis de palabras separadas por una espacio en blanco en el paso 4 para eliminar espacion y separar palabras pueden usar el componente de java stringtokenizer que te separa una cadena en palabras 🙂 pero si es un automata pensado para un compilador grande en el que no importa si hay o no espacios en blanco pues eso no nos sirve, por que lo mismo pudo poner int variable;string variable2; y con tokenizer te kedaria (int)(variable;string)(variable2) por lo que eso no nos sirve obiamente, se debe analizar caracter por caracter para comprobar con nuestra tablita.
5-.recorrer caracter por caracter la cadena guardada en cadt, el estado inicial es 0 por eso sta=0
6-.identificar que tipo de caracter es, y en base a nuestra tabla se guarda en un int tcar; el numero
que le correspone al tipo de caracter por ejemplo si es una letra es 0 por tal tcar=0
sabien eso tenemos si por ejemplo nuestro ciclo es.
while(cont<cadt.lenth)
leemos el primer caracter
char c=cadt.charAt[cont];
despues con unas codiciones vemos que tipo de caracter es
if(c>=’a’ & c<=’z’) si es letra
cart=0;
if(c>=’0′ & c<=’9′) si es digito
cart=1;
if(c>=’_’) si es guion bajo
cart=2;
else si es cualquier cosa que no sea lo anterior : )
cart=3;
…………….
Suponiendo que fue letra(d) tenemos cart=0; y como el esto inicial es 0 osea sta=0; eso nos deja con que a la matriz le corresponde la posición de sta=matriz[sta][cart]; que es equivalente al siguiente estado al que pasara con eso sta=1; osea sta=matriz[[sta][cart]; es sta=matriz[0][0]; se almacena el cart en una variable string temporal seria String temp+=cart; y se reinicia cart=»;
——————-
matriz[0][0]=1;matriz[0][1]=1;matriz[0][2]=200;matriz[0][3]=200;
matriz[1][0]=2;matriz[1][1]=2;matriz[1][2]=2; matriz[1][3]=200;
matriz[2][0]=2;matriz[2][1]=2;matriz[2][2]=2; matriz[2][3]=-1;
Así que para el siguiente carácter que se lea si es por ejemplo un numero (3) según las condiciones que marcamos numero es cart=1; como sta=1; entonces en la matriz sta=matriz[sta][cart]; osea sta=matriz[1][1]; que quedaria sta=2;
nota: de antemano se que mi estado final es -1 asi que siempre se comprueba si sta es -1 si es así pues hasta ahí quedaría.
if(sta!=-1)
Se acumula el nuevo caracter en la variable temp osea temp+=cart; y se reinicia cart=»; mi variable temp ya tiene temp=»d3″
———————————
Si para el siguiente carácter resulta ser un «;» Entonces según nuestras condiciones como no es letra, numero o gb, entonces cart=3;
Nuestro sta=2;
por lo que sta=matriz[sta][cart] o sta=matriz[2][3] por lo que sta=-1
if(sta!=-1) si es estado terminal entonces ahi termina
Por lo que como “;” ya no se almacena en nuestra variable temp entonces nuestro identificador que da temp=d3 osea «d3»
————–
Ahora el hecho que termine cuando sea un carácter que mi autómata no reconocerá en determinada parte significa que ese carácter puede ser el comienzo de otro identificador u otro tipo de dato, con lo que teniendo eso reinicio el sta a 0 con eso tendría para comenzar a analizar la siguiente parte de la cadena y si es mucho el texto comenzar a guardar lo analizado en un arreglo de string, para después manejarlo. Muy pronto actualizare y modificare este pequeño artículo, disculpen que este algo revuelto pero lo eh escrito en un arranque de aburrimiento jejeje.
Hasta pronto.
Atte: CodigoBD
Cualquier duda ponerla aquí mismo, así se responde y sirve para que los demás se enteren si tienen la misma duda.
codigobd 