Teora de Autmatas y Compiladores

La tabla de smbolos es una estructura de datos que nos permite realizar operaciones de insercin, bsqueda y eliminacin de informacin en varias construcciones del lenguaje fuente, la cual es analizada por el compilador originndose un cdigo objeto.

Las principales operaciones de la tabla de smbolos las definimos as:Insercin: Almacena informacin proporcionada por las declaraciones de nombre cuando estas son procesadas.Bsqueda: Recupera la informacin asociada con un nombre cuando este se utiliza en una declaracin o el cdigo asociado.

Eliminacin: Elimina la informacin proporcionada por una declaracin cuando esta ya no se aplica.Ejemplo : Parte de procedimientos en programa fuenteDatos(var1, var2)SiSe aplica la operacinNoSe procesa de nuevoLa operacin Datos(var1, var2) porSer llamada de nuevo en la aplicacinSe elimina de la tabla de smbolosLa operacin Datos(var1, var2)Ya que no se considera necesarios para procesos posteriores

En las sintaxis anteriores, tambin se pueden emplear palabras reservadas como pueden ser los componentes lxico por ej: mod, div

Insertar (div, div); Insertar (mod, mod);

Cualquier llamada posterior busca(div) devuelve el componente lxico div, de modo que div no puede usarse como identificador o variable.

En la siguiente tabla de smbolos de matriz para el almacenamiento de cadenas, una cadena fija de espacios no puede ser lo suficientemente grande para guardar un identificador muy largo, y puede ser innecesariamente grande para un identificador corto, donde se determina que al final de cada cadena se finaliza con un fin-de-cadena representado por FDC, y que no puede aparecer en los identificadores.

MATRIZ TABLASIMBMatriz Lexemas

divFDCmodFDCiFDC

DivModi

La maquina tiene memorias independiente para las instrucciones y datos, y todas las operaciones aritmticas se realizan con los valores en una pila. Las instrucciones son bastantes limitadas y estn comprendidas en las siguientes clases:Aritmtica, Manipulacin de la pila

A continuacin se simula la representacin de una expresin en una pila. La evaluacin se realiza de izq. A der. Insertando los operadores en la pila a medida que los encuentran asi:La expresin -- 1 3 + 5 Insertar 1 en la pilaInsertar 3 en la pilaSumar Insertar 5 en la pilaSumar los dos elementos de la cima, extraerlos e insertar en la pila el resultado 9PILA----------------------------------13Operador aritmtico 5+ (VALOR DE LA CIMA)9

El anlisis gramatical es la tarea de determinar la sintaxis, o estructura de un programa. Por esta razn tambin se le conoce como anlisis sintctico. La sintaxis de un lenguaje de programacin por lo regular se determina mediante las reglas gramaticales de una gramtica libre de contexto de manera similar como se determina mediante expresiones regulares la estructura lxica de los tokens.

La tarea del analizador sintctico es determinarla estructura sintctica de un programa a partirde los tokens producidos por el analizador lexico y, ya sea de manera explicita o implcita, construirun rbol de anlisis gramatical o rbol sintctico Que represente esta estructura. De este modo, Se puede ver el analizador sintctico como una Funcion que toma su entrada la secuencia de

Tokens producidos por el analizador lxico y que produce como su salida el rbol sintctico.Secuencia de tokens Analizador sintctico rbol sintctico La secuencia de tokens por lo regular no es un parmetro de entrada explicito pero el analizador sintctico llama a un procedimiento del analizador lxico, como get token para obtener el siguiente token desde la entrada a medida que lo necesite durante el proceso de anlisis sintctico. De este modo, la etapa de anlisis sintctico del compilador se reduce a una llamada al analizador lxico de la manera :

syntaxtree = parse (); En un compilador de una sola pasada el analizador sintctico incorpora todas las otras fases de un compilador incluyendo la generacion del codigo y no es necesario construir ningun arbol sintactico explicito (las mismas etapas del analizador sintactico representaran de manera implicita al arbol sintactico y por consiguiente una llamada. parse();

Una gramtica libre de contexto es una especificacin para la estructura sintactica de un lenguaje de programacin. Una especificacin as es muy similar a la especificacin de la estructura lexica de un lenguaje utilizando expresiones regulares, excepto que una gramtica libre de contexto involucra reglas de recursividad. Como ejemplo de ejecucin utilizaremos expresiones aritmeti

Simples de enteros con operaciones de suma resta y multiplicacin. Estas expresiones se pueden dar mediante la gramatica siguienteexp exp op exp /(exp)/ numero op -- +/-/*

Corresponde al rbol de anlisis gramatical