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.
block
son de tipo "bloque":
block: %name BLOCK '{' declaration %name DECLARATIONS * statement %name STATEMENTS * '}'
symboltable
: referencia a la tabla de símbolos asociada con el bloque
La tabla de símbolos asociada al bloque es un simple hash.
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
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
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.
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:
entry
: Su entrada en la tabla de símbolos a la que pertenece
scope
: Una referencia al nodo BLOCK
en el que fué declarada la variable
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 %}
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 }
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; }
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 }
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.
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 5Sin embargo no podemos conocer los objetos no declarados (variables, funciones) hasta que hayamos finalizado el análisis de ámbito.
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$
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$