El analisis con Tokens - norman-ipn/Errores GitHub Wiki

Analizador léxico

Este analizador se encarga de formar los componentes léxicos del lenguaje fuente. Estos componentes reciben el nombre de token. Un token es un elemento que puede formar parte del lenguaje fuente. Para implementar un analizador léxico necesitamos un DTE (diagrama de transición de estados) que nos proporcione la especificación léxica del lenguaje fuente. Ejemplo: queremos reconocer como tokens el número 0 (cero), el número 1 (uno), la palabra reservada casa (casa) y cadenas formadas por las letras a y b (cadena).

Partimos de un estado inicial (e) a partir de la cual vemos que con un 0 o con un 1 directamente obtenemos los tokens cero y uno respectivamente. Si tenemos una c, luego una a, luengo una s y luego una a obtenemos el token casa. Y si tenemos uno o más caracteres que sean a o b, obtenemos el token cadena. Cualquier otra posibilidad no contemplada en el DTE nos llevaría a un error léxico: por ejemplo la palabra cab, ya que a partir del estado ca no hay ningún arco que se active con la letra b.

Analizador Sintáctico

Este analizador se encarga de formar componentes sintácticos del lenguaje fuente. En definitiva, nos permitirá saber si un texto concreto pertenece al conjunto de posibles textos de un lenguaje. Para implementar un analizador sintáctico necesitamos una gramática que nos proporcione la especificación sintáctica del lenguaje fuente. Una gramática está formado por una serie de reglas. Cada regla tiene una parte izquierda y una parte derecha. Si se reconoce la parte derecha de una regla, se puede sustituir todo por la parte izquierda de la misma regla. Las reglas están formadas por dos tipos de símbolos:

  • no terminales: también llamados variables y que se expanden en partes derechas de otras reglas.
  • terminales: son tokens de la especificación léxica. Ejemplo: queremos especificar la sintaxis de operaciones aritméticas de números enteros. Las operaciones en cuestión son la suma y la resta. Una primera aproximación podría ser: E → E + E E → E – E E → nint Los tokens son: +: el signo más (suma) -: el signo menos (resta) nint: un número entero, cuya expresión regular sería [0-9]*

Sin embargo, esta gramática no es válida ya que es ambigua. La ambiguedad es un problema bastante importante ya que implica que puede haber más de un árbol de derivación para encontrar una misma cadena. No se pueden implementar analizadores mediante gramáticas ambiguas, ya que aparecerían conflictos.

La ambiguedad es bastante difícil de detectar. Para ello se definen una serie de subconjuntos de gramáticas, y a la hora de diseñar el analizador podemos detectar dicha ambiguedad. En nuestro caso interesa usar las gramáticas SLR a partir de las cuales se pueden implementar analizadores sintácticos ascendentes. La gramática anterior en SLR sería: E → E + T E → E - T E → T T → nint 9

Traductor sintáctico

Un traductor sintáctico es un programa que realiza traducciones parciales del lenguaje fuente al lenguaje destino. Cada regla efectúa una traducción parcial y la regla inicial del programa se encarga de proporcionar la traducción total. Para implementar un traductor sintáctico necesitamos un ETDS (esquema de traducción dirigida por la sintaxis) que nos indique las traducciones parciales de cada regla. Un ETDS es una extensión sobre una gramática que contiene:

  • atributos sintetizados: son valores devueltos por la una regla una vez que se ha reconocido toda la parte derecha de una regla
  • atributos heredados: son valores pasados de una regla a otra, y que aparecen a la izquierda de la regla receptora. Para indicar los valores de los atributos se emplean instrucciones de asignación que aparecen entre llaves ({…}). También se pueden poner instrucciones tipo C. Ejemplo: queremos traducir las expresiones de la gramática anterior a un lenguaje tipo árbol en el que disponemos de las siguientes instrucciones: Suma(a,b) Resta(a,b) La traducción de 1+2+3 sería Suma(Suma(1,2),3) El ETDS resultante es: E → E’ + T {E.t = “Suma(” || E’.t || “,” || T.t || “)”} E → E’ – T {E.t = “Resta(“ || E’.t || “,” || T.t || “)”} E → T {E.t = T.t} T → nint {T.t = nint.lexema} Aquí conviene explicar que:
  • el operador || nos permite realizar concatenaciones
  • Usamos la comilla simple (‘) para distinguir la E de la parte izquierda de la E de la parte derecha en las dos primeras reglas
  • Se supone que el analizador léxico guarda el lexema de todos los tokens.

Diseño de un compilador complejo

Como hemos indicado antes, no siempre traducimos directamente de un lenguaje A a un lenguaje B si no que empleamos front-ends y back-ends. Además, hay que tener en cuenta que los lenguajes objeto de un compilador suelen ser de bajo nivel, mientras que los lenguajes fuente suelen ser de alto nivel. Esto implica que en la traducción se deben tratar conceptos de alto nivel como clases, objetos, etc… A la hora de tratar estos conceptos podemos optar o bien por simular todo en el lenguaje destino mediante rutinas de librería (y de esta manera obtendríamos un ejecutable) o bien delegar en un intérprete. El caso de C es el primero, es decir, obtenemos un ejecutable y lo que hacemos es servirnos de rutinas de librería (entrada / salida, cadenas , etc…). Sin embargo, Java sigue el segundo camino, es decir, el lenguaje objeto de Java es el lenguaje Class, que es un lenguaje interpretado. Los intérpretes de Class, llamados intérpretes de la máquina virtual, son los encargados de manejar conceptos de alto nivel como la creación de clases, recolección de basura, etc… Otro concepto es el de la optimización, ya que muchas el código generado es redudante y se puede mejorar. Una traducción ya optimizada sería bastante costoso y no compensa, es por ello que normalmente en la fase de traducción lo que se busca es rapidez y eficiencia. Luego se suele filtrar la salida con un optimizador.

para mas informacion http://megazar.tripod.com/compil.pdf