Procesadores de lenguajes Proyecto: Generador Lenguaje M

PROCESADORES DE LENGUAJES

Objetivo general.

Realizar un proyecto integrador de los temas vistos en clase, aplicando la teoría de procesadores de lenguajes.

Diseñar y codificar una solución, utilizando un enfoque orientado a objetos, para las diferentes fases de la compilación, partiendo de la especificación de una gramática independiente del contexto incluyendo acciones semánticas, léxicas y sintácticas.

Introducción

El objetivo del proyecto es implementar un programa que, a partir de un código propio, generar un código equivalente en el lenguaje “m” y guardarlo en un archivo con la extensión correspondiente. El archivo generado es capaz de ejecutarse directamente en MATLAB.

El programa se limita a generar un archivo.m de los comandos especificados por nuestro lenguaje:

Las matrices pueden ser declaradas de la siguiente forma, especificando su dimensión:

A = [[1,2,3,4,5],[1,2,3,4,5],[1,2,3,4,5]]; // Se construye con los elementos

Las operaciones deben de tener la forma:

A = operación (M0, … , Mn); // Se crea la matriz resultante de una operación de matrices

Se pueden modificar o acceder a elementos de las matrices de la siguiente manera

A[2,4] = 5; // modificar elemento en fila 2 renglón 4, iniciando desde 0 como en lenguaje C

Se podrán incluir las funciones de control: if-else, for y while.

Se podrán llamar funciones predefinidas de Computer Vision.

Además de operaciones con matrices, se podrán hacer operaciones con números enteros y flotantes y guardarlos en variables para poder ser utilizadas posteriormente.

Se podrá hacer la definición de funciones, las cuales contarán con los inputs (parámetros) y outputs (return).

El programa no ejecutará las operaciones, solo realizará el análisis de los comandos de entrada y los traducirá a lenguaje M, el cual podrá ser ejecutado en Matlab.

Diagrama:

[pic 1]

Análisis léxico 

Lista de Tokens con sus expresiones regulares:

• IN: "in"
• OUT: "out"
• FUNC: "func"
• WHILE: "while"
• FOR: "for"
• UNTIL: "until"
• ELSE_IF: "else if"
• ELSE: "else"
• IF: "if"
• RESERVED_TOKEN: “{“ | “}” | “[“ | “]” | “==” | “=” | “,” | “(“ | “)” | “;” | “<=” | “<” | “>=” | “>” | “!=” | “!” | “-” | “*” | “/” | “+” | “'”
• STRING: "'".*"'"
• NUMBER: 0 | "-"?[0-9][0-9]*("."[0-9][0-9]*)?
• ID: [A-Za-z_][A-Za-z_0-9]*
• ERROR: .
• Se ignora cualquier espacio o termino de línea con: [\r|\n|\r\n] | [ \t\f]

Nota: La clase Error actua con cualquier caracter/cadena ajena al lenguaje.

Ejemplos:

Análisis sintáctico:

Método:

Para el análisis sintáctico se utilizó el método de análisis ascendente visto en clase:

[pic 2]

Es un algoritmo con 4 acciones:

Goto, Reduce, Shift y Accept.

Lo primero que se realizó fue estructurar el cómo recibiríamos la entrada en un archivo de texto, ya que la entrada sería la gramática, los no terminales, los terminales, las clases de tokens, la tabla SLR1 y las entradas a comprobar. Decidimos hacer esto en donde cada una de los puntos anteriores estarían separados por una línea de uno o más ‘#’. Cada una de los puntos estarían separados por un ‘enter’, por ejemplo, para la gramática, cada producción estaría en cada línea (S → A, S → B, etc.) Cada no terminal, estaría separado por ‘enter’ de igual forma (en una línea el no terminal S, en otra A, etc.); así sucesivamente con todas las entradas. Luego se definió que cada línea de las entradas que contuvieran más de un elemento, por ejemplo, las clases de tokens o la tabla SLR1, cada uno de estos elementos estaría separado por comas ‘,’ sin espacios. En este caso, la tabla SLR estaría compuesta por el número de estado, seguido de una “,”, la columna de la tabla, seguido de una “,”, una letra que corresponde a la acción a realizar (s = shift, r = reduce, g = goto, a = aceptar), seguido de una “,” y el estado al que le corresponde dicha acción.

Una vez definido todo esto, se realizó a mano el desarrollo de las actividades correspondientes a la práctica para poder pasarlo al archivo txt.

Lo que se hace en la implementación Java es primero leer el archivo txt, cada vez que nos encontramos con uno o más ‘#’ se hace el llenado de una estructura de datos correspondiente a la entrada (tokens, no terminales, etc.). Para identificar las entradas que contenían más de un elemento (como la tabla SLR1) se realiza un Split de las comas (“,”) encontradas en la línea para poder asignarla a su parte correspondiente.

Una vez que se comience a leer la parte de las entradas, lo primero que se hace es hacer el manejo de las clases de tokens, donde cada token es sustituido en la entrada para poder hacer uso de la tabla SLR1.

Cuando la clase que hace el manejo del algoritmo tiene todas sus estructuras de datos llenas, se manda a llamar el análisis de las entradas. En este análisis lo que se hace primero es buscar en la tabla SLR si existe algo en la posición tope pila estados con el tope de la pila de la entrada; si no existe nada el algoritmo muestra que hay un error, pero si existe algo puede haber 3 escenarios.

El primer escenario es que la celda contenga la operación shift en cuyo caso lo que se hace es hacer un push a la pila de estados el estado correspondiente al shift y remover el primer carácter de la lista que contiene la entrada y agregarlo a la pila de símbolos.

El segundo escenario que se puede dar es que la celda contenga la operación reduce, lo que se hace en este caso es extraer de la gramática la producción que indica la regla a la que se le tiene que aplicar el reduce, con la producción extraída se tiene que ver si la longitud de la ésta es menor o igual al tamaño de la pila de estados, se pueden dar dos escenarios; el primero es que la producción sea épsilon entonces en la tabla de símbolos se inserta la cabeza de la producción, el segundo escenario es que sea algo distinto a épsilon entonces se comparan los n elementos del cuerpo de la producción con los n elementos del tope de la pila de símbolos, si los n elementos son iguales, entonces se reemplazan éstos de la pila de símbolos por la cabeza de la producción y se aplica la función goto del tope de la pila de estados con la cabeza de producción y se agrega el estado obtenido de la tabla SLR a la pila de estados.

El tercer y último escenario es que la acción a realizar sea aceptar, si se llega a éste escenario quiere decir que se acepta la cadena.

Para hacer la impresión de la tabla en consola, se utiliza un string al cual se le concatenan los atributos a imprimir y se imprime dicha cadena al final de cada iteración del ciclo.

Si al final del algoritmo el resultado es falso (una variable boolean), se imprime que la cadena no fue aceptada; si fue verdadero, se imprime que la cadena fue aceptada.

Nótese que se apoyó de el software grammophone (http://mdaines.github.io/grammophone/) para la construcción de dicha tabla.

Gramática:

• S -> Commands .  
• S -> func id ( Outs ) { Commands } S .  
• S -> .  
• Commands -> Command Commands' .  
• Commands' -> Commands .  
• Commands' -> .  
• Command -> id Command' .  
• Command -> If_exp .  
• Command -> While .  
• Command -> For .  
• Command' -> Assign .  
• Command' -> Assign2 .  
• Assign2 -> [ Numbers ] = Expr ; .  
• Numbers -> number Numbers2 .  
• Numbers2 -> , Numbers .  
• Numbers2 -> .  
• Command' -> Func .  
• Assign -> = Assign' ; .  
• Assign' -> Expr .  
• Assign' -> Matrix .  
• Assign' -> ' string ' .  
• Assign' -> id [ Numbers ] .  
• Expr2 -> + Factor .  
• Expr2 -> - Factor .  
• Expr -> Factor Expr3 .  
• Expr3 -> Expr2 Expr3 .  
• Expr3 -> .  
• Factor -> Term Factor2 .  
• Factor2 -> Factor' Factor2 .  
• Factor2 -> .  
• Factor' -> * Term .  
• Factor' -> / Term .  
• Term -> ( Expr ) .  
• Term -> number .  
• Term -> id .  
• If_exp -> if ( Comparison ) { Commands } ElseIf Else .  
• ElseIf -> elseif ( Comparison ) { Commands } ElseIf .  
• ElseIf -> .  
• Else -> else { Commands } .  
• Else -> .  
• Comparison -> Expr Expr' .  
• Expr' -> > Expr .  
• Expr' -> < Expr .  
• Expr' -> >= Expr .  
• Expr' -> <= Expr .  
• Expr' -> == Expr .  
• Expr' -> != Expr .  
• Comparison -> ! ( Comparison ) .  
• While -> while ( Comparison ) { Commands } .  
• For -> for ( id = Expr until Expr ) { Commands } .  
• Func -> ( Func' ) ; .  
• Func' -> id Func2 .  
• Func2 -> , Func' .  
• Func2 -> .  
• Outs -> out id Outs' .  
• Outs -> in Ins .  
• Outs' -> .  
• Outs' -> , Outs .  
• Ins -> id Ins' .  
• Ins' -> .  
• Ins' -> , in Ins .  
• Matrix -> [ Matrix' .  
• Matrix' -> Z ] .  
• Matrix' -> Y ] .  
• Z -> [ Y ] Z' .  
• Z' -> , Z .  
• Z' -> .  
• Y -> number Y' .  
• Y' -> , Y .  
• Y' -> .  

Errores sintácticos:

Cuando existe algún carácter inválido en la entrada; es decir, que sea ajeno a nuestro alfabeto entonces se imprime un mensaje de error:  "Invalid characters detected:\n". Sí este mensaje es mostrado en consola, se tienen que quitar todos los caracteres inválidos para que prosiga el build. Cabe destacar que cuando existe éste mensaje, en consola se despliega la lista de los caracteres inválidos de la entrada y en qué posición del string se encuentran.

Cuando se pasa la etapa anterior (no caracteres ajenos al alfabeto en la entrada), se realiza la recuperación de errores sintáctica, la cual muestra el mensaje de "Unexpected token " + el token que se encontró que no se supone debería estar ahí + "\n". Si a la entrada del programa le falta algún carácter (es decir el top de la pila de la entrada es $ y aún no se llega a la cadena aceptada) se muestra un mensaje de “Expected token before end of code \n”. A continuación, se muestran ejemplos de los errores.

...