análisis sintáctico de una expresión lógica y convertirlo en un árbol en Perl

Question

que tienen expresión lógica compleja que se parecen a esto:

((((!((cond1) || (cond2) || (cond3)) && (cond4))) && (cond5)) <= (((cond6) || (cond7) || (cond8)) || (cond9))) 

Cada línea tiene varias docenas de expresiones. Los signos lógicos permitidos son ||, &&, ! y <=. <= significa cables, como en a <= b significa que b conduce a a.

Necesito repasar esas declaraciones y verificar las condiciones, ya que algunas de ellas ya no son válidas. Quiero poder analizarlo en un árbol, luego verificar cada hoja (donde cada hoja es una condición), eliminar las hojas no deseadas y volver a generar las expresiones completas y correctas.

Sé que cada nodo del árbol está definido por un par del primer corchete y el corchete que lo cierra, pero no sé cómo identificar dichos pares y cómo identificar el signo lógico entre ellos.

Todas las señales a excepción de ! vienen entre dos expresiones.

Answer 1

Suena como un caso para Parse::RecDescent:

use strict; 
use warnings; 
use Parse::RecDescent; 

my $text = '((((!((cond1) || (cond2) || (cond3)) && (cond4))) && (cond5)) <= (((cond6) || (cond7) || (cond8)) || (cond9)))'; 

#$::RD_TRACE=1; 

my $grammar = q{ 

startrule: expr 

expr: operand operation(s?) 
    { $return = @{$item[2]} ? { 'operations' => $item[2], 'lvalue' => $item[1] } : $item[1] } 

operation: /\|\||&&|<=/ operand 
    { $return = { 'op' => $item[1], 'rvalue' => $item[2] } } 

operand: '(' expr ')' 
    { $return = $item[2] } 

operand: '!' operand 
    { $return = { 'op' => '!', 'value' => $item[2] } } 

operand: /\w+/ 

}; 

my $parser = Parse::RecDescent->new($grammar); 
my $result = $parser->startrule($text) or die "Couldn't parse!\n"; 

use Data::Dumper; 
$Data::Dumper::Indent = 1; 
$Data::Dumper::Sortkeys = 1; 
print Dumper $result; 

La gramática, en Inglés:

Todo esto es una expresión. Una expresión es un operando seguido de cero o más operadores binarios y sus operandos. Cada operando es una expresión entre paréntesis, '!' seguido de un operando, o una palabra (por ejemplo, cond1).

Cada nodo en el árbol producido se encuentra en una de las siguientes formas:

• cond1 - una condición
• { 'op' => '!', 'value' => 'node' } -! aplicado a otro nodo
• { 'lvalue' => 'node', 'operations' => [ one or more of: { 'op' => 'binop', 'rvalue' => 'node' } ] } - serie de una o más operaciones que representa el nodo binop nodo nodo binop ...

que no se rompió serie de operaciones binarias (por ejemplo ((cond1) || (cond2) || (cond3))) en un árbol binario, ya que ya ha proporcionado no hay información sobre precedencia o asociatividad.

de salida para el ejemplo es:

$VAR1 = { 
    'lvalue' => { 
    'lvalue' => { 
     'lvalue' => { 
     'op' => '!', 
     'value' => { 
      'lvalue' => 'cond1', 
      'operations' => [ 
      { 
       'op' => '||', 
       'rvalue' => 'cond2' 
      }, 
      { 
       'op' => '||', 
       'rvalue' => 'cond3' 
      } 
      ] 
     } 
     }, 
     'operations' => [ 
     { 
      'op' => '&&', 
      'rvalue' => 'cond4' 
     } 
     ] 
    }, 
    'operations' => [ 
     { 
     'op' => '&&', 
     'rvalue' => 'cond5' 
     } 
    ] 
    }, 
    'operations' => [ 
    { 
     'op' => '<=', 
     'rvalue' => { 
     'lvalue' => { 
      'lvalue' => 'cond6', 
      'operations' => [ 
      { 
       'op' => '||', 
       'rvalue' => 'cond7' 
      }, 
      { 
       'op' => '||', 
       'rvalue' => 'cond8' 
      } 
      ] 
     }, 
     'operations' => [ 
      { 
      'op' => '||', 
      'rvalue' => 'cond9' 
      } 
     ] 
     } 
    } 
    ] 
};