next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: La Dificultad de Elaboración Sup: Análisis de Ámbito Ant: Práctica: Construcción del AST Err: Si hallas una errata ...


Práctica: Análisis de Ámbito del Lenguaje Simple C

Haga una primera parte del análisis de ámbito del lenguaje Simple C presentado en la práctica 12.3.

En esta primera parte se construyen las declaraciones y las tablas de símbolos de cada bloque. Sin embargo no queda establecida la asignación desde una instancia de un objeto a su declaración.

La tabla de Símbolos

Comenzaremos describiendo las estructuras de datos que van a conformar la tabla de símbolos de nuestro compilador:

  1. Dote de los siguientes atributos a los nodos de tipo "bloque", esto es a aquellos nodos que definen ámbito. Por ejemplo, los nodos asociados con la variable sintáctica block son de tipo "bloque": 
    block:
    %name BLOCK
    '{' declaration %name DECLARATIONS * statement %name STATEMENTS * '}'

    1. Atributo symboltable: referencia a la tabla de símbolos asociada con el bloque La tabla de símbolos asociada al bloque es un simple hash.
    2. Atributo fatherblock: referencia al nodo BLOCK que inmediatamente anida a este. Los nodos de tipo bloque quedan enlazados según el árbol de anidamiento de bloques
    3. Los bloques con declaraciones vacías pueden ser simplificados en el árbol de bloques

  2. Los nodos FUNCTION asociados con las funciones son nodos de tipo bloque y serán tratados de manera similar a los nodos BLOCK, esto es, tendrán su tabla de símbolos asociada en la cual se guardarán los parámetros de la función. Este bloque es el bloque padre del bloque formado por el cuerpo de la función. Posteriormente se pueden fusionar estos dos bloques siempre que se conserve la información necesaria sobre los parámetros. 

    funcDef:
    %name FUNCTION
    ID '('  param <%name PARAMS * ','> ')' 
      block

  3. Los identificadores de funciones van en la tabla de símbolos global, asociada con el nodo PROGRAM: 

    pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '/^program:/,/^;/p' SymbolTables.eyp | cat -n
 1  program:
 2        { reset_file_scope_vars(); }
 3      definition<%name PROGRAM +>.program
 4        {
 5          $program->{symboltable} = { %st };  # creates a copy of the s.t.
 6          for (keys %type) {
 7            $type{$_} = Parse::Eyapp::Node->hnew($_);
 8          }
 9          $program->{depth} = 0;
10          $program->{line}  = 1;
11          $program->{types} = { %type };
12          $program->{lines} = $tokenend;
13
14          reset_file_scope_vars();
15          $program;
16        }
17  ;

    Observe que en C una función puede ser usada antes de que aparezca su definición.

  4. Las instancias de los objetos y en particular los nodos VAR deben tener atributos que determinen que declaración se les aplica y en que ámbito viven. Sin embargo estos atributos no serán trabajados en esta práctica:
    1. Atributo entry: Su entrada en la tabla de símbolos a la que pertenece
    2. Atributo scope: Una referencia al nodo BLOCK en el que fué declarada la variable

  5. La tabla de símbolos es un árbol de tablas. Cada tabla esta relacionada con un bloque. Cada tabla tiene una entrada para cada identificador que fué declarado en su bloque. En dicha entrada figuran los atributos del identificador: entre estos últimos la línea en la que fue declarado y su tipo.

¿Que es una declaración?

Para facilitar el análisis de ámbito y la comprobación de tipos debemos modificar la fase de construcción del AST para producir declaraciones que permitan comprobar con facilidad la equivalencia de tipos

La equivalencia de tipos se realiza habitualmente mediante expresiones de tipo. En nuestro caso vamos a elegir una representación dual mediante cadenas y árboles de las expresiones de tipo. Las cadenas serán términos árbol. Como primera aproximación, entenderemos que dos tipos son equivalentes si las cadenas que representan sus expresiones de tipo son iguales. 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '1,/%}/p' SymbolTables.eyp | cat -n
  1  /*
  2  File: SymbolTables.eyp
  3  Scope Analysis: Only symbol table construction
  4  */
  5  %{
  6  use strict;
  7  use Data::Dumper;
  8  use List::MoreUtils qw(firstval lastval);
  9  use Simple::Trans;
 10
 11  my %reserved = (
 ..    ..... => "....."
 20  );
 21
 22  my %lexeme = (
 ..    '..' => ".."
 53  );
 54
 55  our ($blocks);
 56
 57  sub is_duplicated {
 ..    .........
 65  }
 66
 67  sub build_type {
 ..    .............
 82  }
 83
 84  my ($tokenbegin, $tokenend);
 85  my %type;
 86  my $depth;
 87
 88  my %st; # Global symbol table
 89
 90  sub build_function_scope {
...    ................
114  }
115
116  sub reset_file_scope_vars {
117    %st = (); # reset symbol table
118    ($tokenbegin, $tokenend) = (1, 1);
119    %type = ( INT  => 1,
120              CHAR => 1,
121              VOID => 1,
122            );
123    $depth = 0;
124  }
125
126  %}

El código asociado con declaration

Veamos como modificamos la construcción del AST durante las declaraciones: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '/^declaration:/,/^;/p' SymbolTables.eyp | cat -n
 1  declaration:
 2      %name DECLARATION
 3      $basictype $declList ';'
 4        {
 5           my %st; # Symbol table local to this declaration
 6           my $bt = $basictype->type;
 7           my @decs = $declList->children();
 8           while (my ($id, $arrspec) = splice(@decs, 0, 2)) {
 9             my $name = $id->{attr}[0];
10             my $type = build_type($bt, $arrspec);
11             $type{$type} = 1; # has too much $type for me!
12
13             # control duplicated declarations
14             die "Duplicated declaration of $name at line $id->{attr}[1]\n" if exists($st{$name});
15             $st{$name}->{type} = $type;
16             $st{$name}->{line} = $id->{attr}[1];
17           }
18           return \%st;
19        }
20  ;
El código de la función build_type es como sigue: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '/^sub build_type/,82p' SymbolTables.eyp | cat -n
 1  sub build_type {
 2    my $bt = shift;
 3    my @arrayspec = shift()->children();
 4
 5    my $type = '';
 6    for my $s (@arrayspec) {
 7      $type .= "A_$s->{attr}[0](";
 8    }
 9    if ($type) {
10      $type = "$type$bt".(")"x@arrayspec);
11    }
12    else {
13      $type = $bt;
14    }
15    return $type;
16  }

Tratamiento de los Bloques

La variable sintáctica bloque genera el lenguaje de las definiciones seguidas de sentencias:

'{' { datadefinition } { statement } '}'

El lenguaje de los bloques es modificado en consonancia: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '/^block:/,/^;/p' SymbolTables.eyp | cat -n
  1  block:
  2      '{'.bracket declaration<%name DECLARATIONS *>.decs statement<%name STATEMENTS *>.sts '}'
  3         {
  4           my %st;
  5
  6           for my $lst ($decs->children) {
  7
  8               # control duplicated declarations
  9             my $message;
 10             die $message if $message = is_duplicated(\%st, $lst);
 11
 12             %st = (%st, %$lst);
 13           }
 14           $sts->{symboltable} = \%st;
 15           $sts->{line} = $bracket->[1];
 16           $sts->type("BLOCK") if %st;
 17           return $sts;
 18         }
 19
 20  ;

El código de la función is_duplicated es como sigue: 

sub is_duplicated {
  my ($st1, $st2) = @_;

  my $id;

    defined($id=firstval{exists $st1->{$_}} keys %$st2)
  and return "Error. Variable $id at line $st2->{$id}->{line} declared twice.\n";
  return 0;
}

Tratamiento de las Funciones

El código para las funciones es similar. Unimos la tabla de símbolos de los parámetros a la del bloque para posteriormente reconvertir el bloque en un nodo FUNCTION: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '/^funcDef:/,/^;/p' SymbolTables.eyp | cat -n
  1  funcDef:
  2      $ID '('  $params  ')'
  3        $block
  4      {
  5         my $st = $block->{symboltable};
  6         my @decs = $params->children();
  7         $block->{parameters} = [];
  8         while (my ($bt, $id, $arrspec) = splice(@decs, 0, 3)) {
  9             my $bt = ref($bt); # The string 'INT', 'CHAR', etc.
 10             my $name = $id->{attr}[0];
 11             my $type = build_type($bt, $arrspec);
 12             $type{$type} = 1; # has too much $type for me!
 13
 14             # control duplicated declarations
 15             #die "Duplicated declaration of $name at line $id->{attr}[1]\n" if exists($st->{$name});
 16             die "Duplicated declaration of $name at line $st->{$name}{line}\n" if exists($st->{$name});
 17             $st->{$name}->{type} = $type;
 18             $st->{$name}->{param} = 1;
 19             $st->{$name}->{line} = $id->{attr}[1];
 20             push @{$block->{parameters}}, $name;
 21         }
 22         $block->{function_name} = $ID;
 23         $block->type("FUNCTION");
 24         return $block;
 25      }
 26  ;

En la línea 8 se procesan las declaraciones de parámetros. La lista de parámetros estaba definida por: 

params: 
    ( basictype ID arraySpec)<%name PARAMS * ','>
      { $_[1] }

En una segunda fase, a la altura de definition se construye la entrada para la función en la tabla de símbolos global: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '/^definition:/,/^;/p' SymbolTables.eyp | cat -n
 1  definition:
 2      $funcDef
 3        {
 4          build_function_scope($funcDef, 'INT');
 5        }
 6    | %name FUNCTION
 7      $basictype $funcDef
 8        {
 9          build_function_scope($funcDef, $basictype->type);
10        }
11    | declaration
12       {
13         #control duplicated declarations
14         my $message;
15         die $message if $message = is_duplicated(\%st, $_[1]);
16         %st = (%st,  %{$_[1]}); # improve this code
17         return undef; # will not be inserted in the AST
18       }
19  ;
El código de la función build_function_scope es como sigue: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '/sub build_func/,114p' SymbolTables.eyp | cat -n
 1  sub build_function_scope {
 2    my ($funcDef, $returntype) = @_;
 3
 4    my $function_name = $funcDef->{function_name}[0];
 5    my @parameters = @{$funcDef->{parameters}};
 6    my $lst = $funcDef->{symboltable};
 7    my $numargs = scalar(@parameters);
 8
 9    #compute type
10    my $partype = "";
11    my @types = map { $lst->{$_}{type} } @parameters;
12    $partype .= join ",", @types if @types;
13    my $type = "F(X_$numargs($partype),$returntype)";
14
15    #insert it in the hash of types
16    $type{$type} = 1;
17
18    #insert it in the global symbol table
19    die "Duplicated declaration of $function_name at line $funcDef-->{attr}[1]\n"
20      if exists($st{$function_name});
21    $st{$function_name}->{type} = $type;
22    $st{$function_name}->{line} = $funcDef->{function_name}[1]; # redundant
23
24    return $funcDef;
25  }

El Tratamiento del Programa Principal

Sigue el código (incompleto) asociado con la variable sintáctica de arranque: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '/^program:/,/^;/p' SymbolTables.eyp | cat -n
 1  program:
 2        { reset_file_scope_vars(); }
 3      definition<%name PROGRAM +>.program
 4        {
 5          $program->{symboltable} = { %st };  # creates a copy of the s.t.
 6          for (keys %type) {
 7            $type{$_} = Parse::Eyapp::Node->hnew($_);
 8          }
 9          $program->{depth} = 0;
10          $program->{line}  = 1;
11          $program->{types} = { %type };
12          $program->{lines} = $tokenend;
13
14          reset_file_scope_vars();
15          $program;
16        }
17  ;
Las árboles asociados con las expresiones de tipo son calculados en las líneas 6-8.

Ejemplo de Salida: Control de declaraciones duplicadas

A estas alturas del análisis de ámbito podemos controlar la aparición de declaraciones duplicadas: para el programa de entrada: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/script$ usesymboltables.pl declaredtwice.c 2
int a, b[1][2];
char d, e[1][2];
char f(int a, char b[10]) {
  int c[1][2];
  char b[10], e[9]; /* b is declared twice */

  return b[0];
}

Duplicated declaration of b at line 5
Sin embargo no podemos conocer los objetos no declarados (variables, funciones) hasta que hayamos finalizado el análisis de ámbito.

Un ejemplo de Volcado de un AST

Sigue un ejemplo de salida para un programa sin errores de ámbito: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/script$ usesymboltables.pl prueba10.c 2
int a,b;
f(int a, int b) {
  b = a+1;
}

int main() {
  a = 4;
  {
    int d;
    d = f(a);
  }
}

PROGRAM^{0}(
  FUNCTION[f]^{1}(
    ASSIGN(
      VAR[No declarado!](
        TERMINAL[b:3]
      ),
      PLUS(
        VAR[No declarado!](
          TERMINAL[a:3]
        ),
        INUM(
          TERMINAL[1:3]
        )
      ) # PLUS
    ) # ASSIGN
  ) # FUNCTION,
  FUNCTION[main]^{2}(
    ASSIGN(
      VAR[No declarado!](
        TERMINAL[a:7]
      ),
      INUM(
        TERMINAL[4:7]
      )
    ) # ASSIGN,
    BLOCK[8]^{3}(
      ASSIGN(
        VAR[No declarado!](
          TERMINAL[d:10]
        ),
        FUNCTIONCALL[No declarado!](
          TERMINAL[f:10],
          ARGLIST(
            VAR[No declarado!](
              TERMINAL[a:10]
            )
          ) # ARGLIST
        ) # FUNCTIONCALL
      ) # ASSIGN
    ) # BLOCK
  ) # FUNCTION
) # PROGRAM
---------------------------
0)
Types:
$VAR1 = {
  'CHAR' => bless( {
    'children' => []
  }, 'CHAR' ),
  'VOID' => bless( {
    'children' => []
  }, 'VOID' ),
  'INT' => bless( {
    'children' => []
  }, 'INT' ),
  'F(X_0(),INT)' => bless( {
    'children' => [
      bless( {
        'children' => []
      }, 'X_0' ),
      $VAR1->{'INT'}
    ]
  }, 'F' ),
  'F(X_2(INT,INT),INT)' => bless( {
    'children' => [
      bless( {
        'children' => [
          $VAR1->{'INT'},
          $VAR1->{'INT'}
        ]
      }, 'X_2' ),
      $VAR1->{'INT'}
    ]
  }, 'F' )
};
Symbol Table of the Main Program:
$VAR1 = {
  'a' => {
    'type' => 'INT',
    'line' => 1
  },
  'b' => {
    'type' => 'INT',
    'line' => 1
  },
  'f' => {
    'type' => 'F(X_2(INT,INT),INT)',
    'line' => 2
  },
  'main' => {
    'type' => 'F(X_0(),INT)',
    'line' => 6
  }
};

---------------------------
1)
Symbol Table of f
$VAR1 = {
  'a' => {
    'type' => 'INT',
    'param' => 1,
    'line' => 2
  },
  'b' => {
    'type' => 'INT',
    'param' => 1,
    'line' => 2
  }
};

---------------------------
2)
Symbol Table of main
$VAR1 = {};

---------------------------
3)
Symbol Table of block at line 8
$VAR1 = {
  'd' => {
    'type' => 'INT',
    'line' => 9
  }
};

pl@nereida:~/Lbook/code/Simple-SymbolTables/script$

Métodos de soporte para el Volcado del Arbol

Se han utilizado las siguientes funciones de soporte para producir el volcado: 

pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$ sed -ne '683,$p' SymbolTables.eyp
############## Debugging and Display
sub show_trees {
 my ($t) = @_;

 print Dumper $t if $debug > 1;
 $Parse::Eyapp::Node::INDENT = 2;
 $Data::Dumper::Indent = 1;
 print $t->str."\n";
}

$Parse::Eyapp::Node::INDENT = 1;
sub TERMINAL::info {
  my @a = join ':', @{$_[0]->{attr}};
  return "@a"
}

sub PROGRAM::footnote {
  return "Types:\n"
         .Dumper($_[0]->{types}).
         "Symbol Table of the Main Program:\n"
         .Dumper($_[0]->{symboltable})
}

sub FUNCTION::info {
  return $_[0]->{function_name}[0]
}

sub FUNCTION::footnote {
  my $text = '';
  $text .= "Symbol Table of $_[0]->{function_name}[0]\n" if $_[0]->type eq 'FUNCTION';
  $text .= "Symbol Table of block at line $_[0]->{line}\n" if $_[0]->type eq 'BLOCK';
  $text .= Dumper($_[0]->{symboltable});
  return $text;
}

sub BLOCK::info {
  my $info = "$_[0]->{line}";
  return $info;
}

*BLOCK::footnote = \&FUNCTION::footnote;

sub VAR::info {
  return $_[0]->{type} if defined $_[0]->{type};
  return "No declarado!";
}

*FUNCTIONCALL::info = *VARARRAY::info = \&VAR::info;
pl@nereida:~/Lbook/code/Simple-SymbolTables/lib/Simple$


Subsecciones
next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: La Dificultad de Elaboración Sup: Análisis de Ámbito Ant: Práctica: Construcción del AST Err: Si hallas una errata ...
Casiano Rodríguez León
2013-03-05