Programacion de sistemas análisis semántico y traducción análisis Semántico



Descargar 17,78 Kb.
Fecha de conversión10.01.2017
Tamaño17,78 Kb.

PROGRAMACION DE SISTEMAS

  • ANÁLISIS SEMÁNTICO Y TRADUCCIÓN

Análisis Semántico

  • Comprobación estática
    • Comprobación de tipos
    • La aplicación de los operadores y operandos deben ser compatibles
    • Comprobaciones del flujo del control
    • Las proposiciones que hacen que se abandone el flujo del control de una construcción debe transferirse a otro punto. (break, exit)
  • Comprobaciones de unicidad
    • Hay situaciones en los que un objeto solo puede definirse una vez exclusivamente. Las etiquetas de una sentencia case no deben repetirse, declaraciones de objetos,..
  • Comprobaciones relacionadas con nombre
    • El mismo nombre debe aparecer dos o más veces. En Ada el nombre que aparece en un bloque puede aparecer al principio y final, el compilador debe comprobar que se utiliza el mismo el ambos sitios

Análisis Semántico

  • Además de comprobar que un programa cumple con las reglas de la gramática, hay que comprobar que lo que se quiere hacer tiene sentido.
  • Esta fase también modifica la tabla de símbolos y suele estar mezclada con la generación de código intermedio.
  • Las gramáticas independientes del contexto (G2) no son suficientes para realizar el análisis semántico.
  • Por ejemplo, no hay forma de comprobar si una variable ha sido definida ya, o si existe una determinada etiqueta.
  • Es necesario definir un tipo de gramática más rica como las gramáticas de atributo.

Definición

  • Definición
    • Las gramáticas de atributo son gramáticas G2 a las que se añaden atributos y reglas de evaluación de atributos (funciones/reglas semánticas)

Traducción dirigida por sintaxis

Traducción dirigida por sintáxis

  • Notaciones
    • Definición dirigida por la sintaxis (DDS)
    • Esquema de Traducción (EDT)
    • Evaluación de una acción
  • Generación de código
    • Guardar/Consultar información de la Tabla de Símbolos
    • Notificación de mensajes de error.

Traducción dirigida por sintáxis

  • Definición dirigida por la sintaxis
    • Cada símbolo tiene un conjunto de atributos asociados
      • Atributo: una cadena, número, tipo, posición de memoria, etc
      • NombredeSímbolo.NombredeAtributo
    • Cada producción A=a tiene asociada un conjunto de acciones semánticas que se representan como una función:
    • X.atr=f (Y1.atr, ..., Yn.atr)
  • Dos tipos de atributos
    • Sintetizados (locales)
      • El valor a asignar a un nodo depende del valor de los nodos hijos
  • Heredados
    • Se pasan a niveles inferiores del árbol. Su valor depende del valor de los hermanos y del padre.

Ejemplo

  • Ejemplo
    • Sintetizados, CALCULADORA, Análisis Ascendente
    • Producción Reglas Semánticas
    • L->E n print (E.val)
    • E->E1 + T E.val := E1.val + T.val
    • E->T E.val := T.val
    • T->T1 * F T.val := T1.val * F.val
    • T->F T.val := F.val
    • F-> ( E ) F.val := E.val
    • F->dígito F.val := dígito.valex

Traducción dirigida por sintáxis

  • Ejemplo
  • Heredados, INFORMACIÓN DE TIPOS
    • Producción Reglas Semánticas
    • D->T L L.her := T.tipo
    • T->int T.tipo := integer
    • T->real T.tipo := real
    • L->L1,id L1.her := L.her
    • añadetipo (id.entrada, L.her)
    • L->id añadetipo (id.entrada, L.her)

Grafos de dependencias

  • Si un atributo b en un nodo depende de un atributo c, entonces se debe evaluar la regla semántica para b después de la regla semántica que define a c
  • Las interdependencias entre atributos heredados y sintetizados de un árbol de análisis sintáctico se pueden representar mediante un grafo dirigido llamado Grafo de Dependencias

Grafos de dependencias

  • Algoritmo de Construcción
  • Para cada nodo n en el árbol de análisis sintáctico hacer
  • Para cada atributo a del símbolo gramatical en el nodo n hacer
  • Construir un nodo en el grafo de dependencias para a;
  • Para cada nodo n en el árbol de análisis sintáctico hacer
  • Para cada regla semántica b:=f(c1, c2, ..., ck) asociada con la
  • producción utilizada en n hacer
  • Para cada i:=1 hasta k hacer
  • Construir una arista desde el nodo ci hasta el nodo para b;
  • Producción Regla Semántica
  • E->E1+E2 E.val:=E1.val+E2.val

Grafo de dependencias

  • Ejemplo: real id1, id2, id3

Grafo de dependencias

  • Evaluación de las reglas semánticas
    • Métodos con árbol de análisis sintáctico
    • Se realiza en el momento de compilación
    • El orden se obtiene de un ordenamiento topológico del grado de dependencias construido según el árbol de análisis sintáctico para cada entrada
    • Si hay ciclos no funciona
  • Métodos basados en reglas
    • Se realiza en el momento de construcción del compilador
    • Las reglas semánticas asociadas con las producciones se analizan a mano
    • No necesita construir un grafo de dependencias de forma explícita
  • Métodos “sin recuerdo”
    • Para realizar el orden de evaluación no tiene en cuenta las reglas semánticas. Por ejemplo en el momento de análisis sintáctico.
    • No necesita construir un grafo de dependencias de forma explícita

Evaluación Ascendente de Definiciones con Atributos Sintetizados (I)

  • Los atributos sintetizados se pueden evaluar con un analizador sintáctico ascendente conforme la entrada es analizada
  • El analizador sintáctico conserva en su pila los valores de los atributos sintetizados asociados a los símbolos gramaticales
  • Cuando se hace una reducción se calculan los valores de los nuevos atributos sintetizados a partir de los atributos de la pila para los símbolos gramaticales del lado derecho de la producción.

Evaluación Ascendente de Definiciones con Atributos Sintetizados (II)

  • Ejemplo
  • Producción Fragmento de Código
  • L->E n print (val [tope])
  • E->E1 + T val [ntope] := val [tope-2] + val [tope]
  • E->T
  • T->T1 * F val [ntope] := val [tope-2] * val [tope]
  • T->F
  • F-> ( E ) val [ntope] := val [tope-1]
  • F->dígito F.val := dígito.valex

Definiciones con Atributos por la Izquierda

  • Si la traducción ocurre durante el análisis sintáctico, el orden de evaluación de los atributos se corresponde con el orden en el que se “crean” los nodos de un árbol de análisis sintáctico
  • Un orden natural para los métodos de traducción descendente y ascendente es el “orden de evaluación en profundidad”
  • procedimiento visitaprof (n:nodo)
  • empezar
  • para cada hijo m de n, de izquierda a derecha
  • hacer empezar
  • evaluar los atributos heredados de m;
  • visitarprof (m)
  • fin;
  • evaluar los atributos sintetizados de n
  • fin

Esquema de traducción

  • Cada símbolo tiene un conjunto de atributos asociados
    • Nombre_de_Símbolo.Nombre_de_Atributo
  • Las acciones semánticas se intercalan con los símbolos del consecuente
    • X::=ab {accion();} b
  • Orden de evaluación fijo
  • Dos tipos
    • EDT sólo con atributos sintetizados
      • Acciones al final de la producción
    • EDT con atributos sintetizados y heredados
      • Atributos heredados de un símbolo del consecuente
      • Atributos sintetizados utilizados en acciones
      • Atributos sintetizados del antecedente

Esquemas de traducción

  • Sólo con atributos sintetizados
    • Una acción para cada regla semántica
    • Se coloca al final del lado derecho de la producción
    • Producción Regla Semántica
    • T->T1*F T.val:=T1.val x F.val
    • T->T1*F {T.val:=T1.val x F.val}
  • Con atributos heredados y sintetizados
    • Un atributo heredado para un símbolo en el lado derecho de una producción debe calcularse en una acción antes que dicho símbolo.
    • Una acción no debe referirse a un atributo sintetizado de un símbolo que esté a la derecha de la acción
    • Un atributo sintetizado para el NO terminal de la izquierda solo puede calcularse después de que se hayan calculado todos los atributos a los que hace referencia. (La acción se sitúa al final del lado derecho de la producción).

Generación de código intermedio

  • Proceso de Síntesis
    • Lenguaje Intermedio
    • Generación de Código
  • Ventajas del código intermedio
    • Facilitar la fase de optimización
    • Aumentar la portabilidad del compilador de una máquina a otra
      • Se puede utilizar el mismo analizador para diferentes generadores
      • Se pueden utilizar optimizadores independientes de la máquina
    • Facilitar la división en fases del proyecto

Esquema del proceso

Tipos de representaciones intermedias

  • Notación Polaca Inversa (RPN)
    • Los operadores van después de los operandos
      • S = A + B * C ® S A B C * + =
    • Ventajas
      • Facilidad para generar código a partir de ella
      • Es la notación más sencilla para el lenguaje intermedio
    • Inconvenientes
      • El código es difícil de entender
      • No es útil para optimización de código
  • Árboles de Sintaxis Abstracta (Árbol Semántico)
  • Códigos de tres direcciones
    • Cuartetos
    • Tercetos
    • Tercetos Indirectos

Árboles de sintaxis abstracta

  • Son árboles de derivación en los que no existe información superflua
  • Cada nodo hoja representa un operando y cada no-hoja un operador

Códigos de tres direcciones

  • Cada línea de código tiene un operador y hasta tres direcciones
    • Tipos: Cuartetos, Tercetos, Tercetos Indirectos
    • Cuartetos. Se representan por cuatro valores:
        • (,,,)

Tercetos

  • Los cuartetos son la herramienta más general
  • Inconvenientes
    • Ocupan demasiado espacio
    • Requieren muchas variables auxiliares para almacenar los resultados intermedios
  • Los tercetos resuelven este problema suprimiendo el operando del resultado, queda implícito y asociado a dicho terceto
    • (, , )
    • Hacen referencia a otro terceto
    • Son equivalentes a Árboles de Sintaxis Abstracta

Tercetos y tercetos indirectos

  • Los Tercetos Indirectos son análogos a los anteriores pero en lugar de ejecutarse secuencialmente se ejecutan según un vector llamado SECUENCIA.
    • Son más fáciles de optimizar
    • Ocupan menos memoria, el mismo terceto aparece una vez

Tercetos indirectos, ejemplos

Tercetos indirectos, optimización

Comparación entre representaciones

  • Nivel de Indirección
  • La representación de tercetos tiene mayor nivel de indirección que los cuartetos
  • Optimización
    • Mover código en los tercetos es relativamente más difícil, aunque en menor grado para los tercetos indirectos
    • Espacio
    • Los cuartetos ocupan más memoria, especialmente si se utilizan las variables temporales más de una vez

Tercetos

  • Traducción dirigida por la sintaxis a código de tres direcciones
    • Se construyen nombres temporales para los nodos interiores del árbol sintáctico
    • Se calcula el valor del no terminal E en el lado izquierdo de E->E1+E2 dentro de un nuevo temporal t
      • E.lugar, es el nombre que contendrá el valor de E
      • E.código, es la secuencia de proposiciones de tres direcciones que evalúan E
    • La función tempnuevo devuelve una secuencia de nombres distintos

Ejemplos TDS a Tercetos

Generación de código a partir de Notación Polaca

  • El código se genera cuando se encuentra el operador.

Generación de Código Intermedio en el Análisis Sintáctico Recursivo

  • Se pueden utilizar las rutinas de árboles de sintaxis abstracta, incorporándolas al código
    • Supongamos que se genera con el análisis un árbol binario con tres campos por nodo: info (información del nodo); izda (puntero al subárbol izquierdo; dcha (puntero al subárbol derecho)
  • Se pueden definir las funciones
  • Se añade un parámetro a cada procedimiento que contiene el árbol generado hasta ese momento
  • Además, se pueden formar grafos dirigidos para optimizar las expresiones aritméticas

GCI con ASA

Ejemplo GCI

GCI – Asignaciones con cuartetos

GCI – Expresiones lógicas

GCI - Condicionales

GCI - Ciclos

Generación de código final

  • Traducción de la representación intermedia a código objeto.
  • Hay que tener en cuenta la arquitectura de la máquina para realizar una gestión eficiente de la memoria y de los registros.
  • Primero se generan las directivas para reservar memoria para las variables y datos.
  • Luego se genera el resto del código. Por ejemplo, los árboles de sintaxis abstracta se recorren para generar el código directamente.
  • Hay que tener en cuenta :

Generación de código

Estrategias



La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal