Разбор логического выражения и преобразование его в дерево в Perl - PullRequest
Новая
       24

Разбор логического выражения и преобразование его в дерево в Perl

7 голосов
/ 23 декабря 2010

У меня есть сложное логическое выражение, которое выглядит так: 

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

Каждая строка содержит несколько десятков выражений. Допустимые логические знаки: ||, &&, ! и <=. <= означает, ведет, как в a <= b означает, что b ведет к a.

Мне нужно просмотреть эти заявления и проверить условия, поскольку некоторые из них больше не действительны. Я хочу иметь возможность проанализировать его в дереве, а затем проверить каждый из его листьев (где каждый лист является условием), удалить ненужные листья и построить полное и правильное выражение обратно.

Я знаю, что каждый узел дерева определяется парой первой скобки и скобки, которая ее закрывает, но я не знаю, как определить такие пары и как определить логический знак между ними.

Все знаки, кроме !, находятся между двумя выражениями.

1 Ответ

11 голосов
/ 23 декабря 2010

Звучит как случай для 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;

Грамматика на английском языке:

Все это выражение. Выражение - это операнд, за которым следуют ноль или более бинарных операторов и их операндов. Каждый операнд является выражением в скобках, '!' сопровождаемый операндом или словом (например, cond1).

Каждый узел в созданном дереве имеет одну из следующих форм:

  • cond1 - состояние
  • { 'op' => '!', 'value' => 'node' } -! применяется к другому узлу
  • { 'lvalue' => 'node', 'operations' => [ one or more of: { 'op' => 'binop', 'rvalue' => 'node' } ] } - серия из одной или нескольких операций, представляющих узел binop узел binop узел ...

Я не разбивал ряд двоичных операций (например, ((cond1) || (cond2) || (cond3))) на двоичное дерево, потому что вы не предоставили информацию о приоритетности или ассоциативности.

Вывод для вашего примера: 

$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'
          }
        ]
      }
    }
  ]
};
...