Crear una estructura de datos de árbol (debe ser nativa) en Perl para representar un árbol de llamadas que se encuentra en un archivo externo
https://stackoverflow.com/questions/4891453
-
28-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Aquí hay un ejemplo del archivo.
powrup.asm POWER_UP
......EXTERNAL_RAM_ADDRESSING_CHECK powrup.asm:461
......EXRAM powrup.asm:490
......INRAM powrup.asm:540
......OUTPUT_TEST powrup.asm:573
............AD_READ douttst.asm:276
............AD_READ douttst.asm:366
......OUTPUT2_TEST powrup.asm:584
............AD_READ douttst2.asm:253
............AD_READ douttst2.asm:342
......OUTPUT3_TEST powrup.asm:599
............AD_READ douttst3.asm:307
............AD_READ douttst3.asm:398
......INPUT_TEST powrup.asm:614
......PROGRAM_PINS2_INPUT powrup.asm:629
......ARINC_TEST powrup.asm:633
............ARINC_LEVEL_TEST artest.asm:178
..................AD_READ arltst.asm:204
..................AD_READ arltst.asm:250
..................AD_READ arltst.asm:300
..................AD_READ arltst.asm:346
..................AD_READ arltst.asm:396
..................AD_READ arltst.asm:442
............ARINC_READ artest.asm:209
............ARINC_WORD_TXRX_TEST artest.asm:221
..................ARINC_OUT artxrx.asm:207
..................ARINC_READ artxrx.asm:221
............ARINC_READ artest.asm:251
............ARINC_WORD_TXRX_TEST artest.asm:263
..................ARINC_OUT artxrx.asm:207
..................ARINC_READ artxrx.asm:221
......PROGRAM_PINS2_INPUT powrup.asm:640
......PROGRAM_PIN_TEST powrup.asm:642
......PT_RCVR_BITE powrup.asm:645
............AD_READ10 ptbite.asm:225
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:308
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:384
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:467
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:542
..................AD_READ adread10.asm:141
............AD_READ10 ptbite.asm:622
..................AD_READ adread10.asm:141
......PROGRAM_PINS2_INPUT powrup.asm:653
......EXEC_INIT powrup.asm:663
El ... representa la profundidad de la llamada. El nombre del archivo después de la línea indica el nombre del archivo y el número de línea desde el que se llamó en el padre. Puedo analizar el archivo. Lo que estoy tratando de hacer una vez que he analizado el archivo es poner los datos en un árbol N-ARY. Estoy haciendo un análisis de acoplamiento y acoplamiento de control de datos y ya he recopilado todos los datos establecidos/de uso para todas las variables en la compilación. Ahora necesito poder atravesar el árbol y, en función de la profundidad, averiguar si hay algún conjunto antes de usar situaciones o situaciones de conjunto pero no utilizadas. Pensé que un recorrido de árbol tendría más sentido.
Aquí hay un ejemplo de los datos recopilados:
$hash_DB{'alt_deviation_evaluation.asm->ALT_STATUS'} = [
'alt_deviation_evaluation.asm',
'ALT_STATUS',
'1.1',
1,
"",
"",
"135,188,202,242",
"130,144"
];
'alt_deviation_evaluation.asm->ALT_STATUS' is the file name and variable name.
'alt_deviation_evaluation.asm', File name
'ALT_STATUS', Variable name
'1.1', versions of file
1, indicates has been processed
"", not used (maybe in future)
"", not used (maybe in future)
"135,188,202,242", variable Set line numbers for this fileVariable
"130,144" Variable Use line number for this file/Variable
También tengo una matriz con todos los nombres de variables. Ejemplo acortado:
our @vars_list = (
'A429_TX_BUFFER_LENGTH',
'A429_TX_INPUT_BUFFER',
'A429_TX_INT_MASK',
'ABS_ALT_DIFF',
'ACTUAL_ALT',
'ADDRESS_FAIL',
'AD_CONV_FAIL',
'AD_CONV_SIGNAL',
'AD_DATA',
'AD_FAIL',
'AD_STATUS',
'AIR_MODE',
'AIR_MODE_COUNT',
'AIR_MODE_LAST',
'ALPHA_COR_SSM',
'ALPHA_EC_SSM',
'ALPHA_GRAD_SSM',
'ALPHA_LE_SSM',
'ALPHA_LG_SSM',
'ALPHA_MAX_MC_SSM'
};
Mi mayor obstáculo es descubrir las estructuras y algoritmos de datos adecuados para lograr esta tarea.
Pensé que una primera búsqueda de profundidad de un árbol n-oral me daría lo que quiero.
Aquí está mi solución final:
#!/usr/local/bin/perl
# !/usr/bin/perl
use Data::Dumper; #!!!
sub Create_Tree;
sub Treverse;
#for my $node (@TREE) {
# print_node($node[0], 1);
#}
#Main
our @TREE;
Create_Tree("call_tree.small_01.txt");
my $str = Dumper @TREE;
$str =~ s/^(\s+)/' 'x(length($1)>>2)/meg;
#print "\n\n=======================================\n$str"; #!!!
#print "\n\n=======================================\n" . (Dumper @TREE); #!!!
#print "Arr = @TREE, SZ = $#TREE\n\n";
Treverse(\@TREE,1);
sub Create_Tree
{
my ($call_tree) = @_;
my @stack;
my ($old_depth, $p_arr) = (0, \@TREE);
open(IN, "< $call_tree" ) or die "Can not open '$call_tree' for input.\n";
for (<IN>)
{
if (m/^(\s*)(\S+)\s*=>\s*(\S+):(\d+)/ or m/^(\s*)(\S+)()()/)
{
my ($depth, $callee_fn, $caller_fn, $ln, $diff) = ($1, $2, $3, $4, 0);
$depth = int(length($depth) / 6);
$diff = $depth - $old_depth;
if ($diff == 1)
{
push @stack, $p_arr;
$p_arr = \@{$$p_arr[$#{$p_arr}]{children}};
}
elsif ($diff < 0)
{
$p_arr = pop @stack while ++$diff <= 0;
}
elsif ($diff > 1)
{
die "Incorrectly formated call tree:\n $_\n";
}
push @$p_arr, {
caller => $caller_fn,
called_by => $callee_fn,
at_line => $ln
};
$old_depth = $depth;
}
}
close IN;
}
exit;
La salida se ve así:
......file1
............file1 101:A
..................XXX.AA 102:AA
........................XXX.AAA 103:AAA
........................XXX.AAB 104:AAB
..............................XXX.AABA 105:AABA
..................XXX.AB 106:AB
........................XXX.ABA 107:ABA
............file1 108:B
..................XXX.BA 109:BA
........................XXX.BAA 110:BAA
........................XXX.BAB 111:BAB
Desde este archivo Call_tree.txt:
file1
A => file1:101
AA => XXX.AA:102
AAA => XXX.AAA:103
AAB => XXX.AAB:104
AABA => XXX.AABA:105
AB => XXX.AB:106
ABA => XXX.ABA:107
B => file1:108
BA => XXX.BA:109
BAA => XXX.BAA:110
BAB => XXX.BAB:111
Usando esta subrutina:
sub Treverse
{
my ($p_arr, $level) = @_;
for (my $ind=0; $ind<=$#{$p_arr}; $ind++)
{
print "." x ($level*6);
if ($$p_arr[$ind]{'caller'} ne "") {print "$$p_arr[$ind]{'caller'}" . " " x 4;}
if ($$p_arr[$ind]{'at_line'} ne "") {print "$$p_arr[$ind]{'at_line' }" . ":";}
if ($$p_arr[$ind]{'called_by'} ne "") {print "$$p_arr[$ind]{'called_by'}" . "\n";}
Treverse(\@{$$p_arr[$ind]{children}}, $level +1) if defined $$p_arr[$ind]{children};
}
}
# END of Treverse
Solución
Para las estructuras de datos, una de las mayores poderes de Perl es la anidación arbitraria de las estructuras. Por lo tanto, en lugar de tener una sola variable que contenga todos los datos para todas las notas que puede tener "subnodos" dentro de sus padres.
Digamos que tenía un hash para una entrada:
%node1 = ( name => 'ALPHA_MAX_MC_SSM', file => 'arltst.asm', line => 42 );
El código anterior creará un buen nodo simplemente para almacenar datos. Pero en realidad puede almacenar más datos dentro de los mismos. Un "nodo infantil":
%node2 = (
name => 'ACTUAL_ALT',
file => 'foo.asm',
line => 2001
);
$node1{children}[0] = \%node2;
Entonces tienes un nodo infantil ('niños') en el primer nodo que es una matriz de todos sus hijos. Puede acceder a la fecha en el niño directamente como:
$node1{'children'}[0]{'name'};
Para comprender esto y cómo funciona, debe leer sobre las referencias de Perl y los tipos de datos de Perl. Se necesita un poco como un nuevo programador de Perl para obtener los conceptos, pero una vez que lo obtiene, puede hacer programas rápidos increíblemente poderosos que gruñen datos jerárquicos complejos y procesarlos.
Otros consejos
Aquí es cómo imprimir la estructura que construyó con la respuesta de Wes.
Una vez procesado los datos, termina con algo como esto:
my @nodes = (
{ name => 'ARINC_TEST', file => 'powrup.asm', line => 633,
children => [
{ name => 'ARINC_LEVEL_TEST', file => 'artest.asm', line => 178,
children => [
{ name => 'AD_READ', file => 'arltst.asm', line => 204 },
{ name => 'AD_READ', file => 'arltst.asm', line => 250 },
{ name => 'AD_READ', file => 'arltst.asm', line => 300 },
{ name => 'AD_READ', file => 'arltst.asm', line => 346 },
{ name => 'AD_READ', file => 'arltst.asm', line => 396 },
{ name => 'AD_READ', file => 'arltst.asm', line => 442 },
],
},
{ name => 'ARINC_READ', file => 'artest.asm', line => 209,
children => [],
},
{ name => 'ARINC_WORD_TXRX_TEST', file => 'artest.asm', line => 221,
children => [
{ name => 'ARINC_OUT', file => 'artxrx.asm', line => 207 },
{ name => 'ARINC_READ', file => 'artxrx.asm', line => 221 },
],
}
]
}
);
La estructura es recursiva y children Punto clave a ArrayRef de otro hash. Para imprimir esto, necesita código recursivo:
for my $node (@nodes) {
print_node($node, 1);
}
sub print_node {
my ($node, $level) = @_;
# the node itself
print "." x ($level*6)
, $node->{name}, " " x 4
, $node->{file}, ":"
, $node->{line}, "\n";
# recurse for children
if(defined $node->{children}) {
for my $child (@{ $node->{children} }) {
print_node($child, $level + 1);
}
}
}
Para los datos anteriores, el código sale
......ARINC_TEST powrup.asm:633
............ARINC_LEVEL_TEST artest.asm:178
..................AD_READ arltst.asm:204
..................AD_READ arltst.asm:250
..................AD_READ arltst.asm:300
..................AD_READ arltst.asm:346
..................AD_READ arltst.asm:396
..................AD_READ arltst.asm:442
............ARINC_READ artest.asm:209
............ARINC_WORD_TXRX_TEST artest.asm:221
..................ARINC_OUT artxrx.asm:207
..................ARINC_READ artxrx.asm:221
