解析逻辑表达式并将其转换为Perl中的树 [英] Parsing of a logical expression and converting it to a tree in Perl

问题描述

我有一个看起来像这样的复杂逻辑表达式:

I have complex logical expression that look like this:

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

每行都有几十个表达式.允许的逻辑符号为||，&&，!和<=. <=表示线索，如a <= b表示b导致a.

Each line has several dozens of expressions. The allowed logical signs are ||, &&, ! and <=. <= means leads, as in a <= bmeans that b leads to a.

我需要检查这些语句并检查条件，因为其中一些不再有效.我希望能够将其解析为一棵树，然后检查其中的每个叶子(其中每个叶子都是一个条件)，删除不需要的叶子，并重新构建完整且正确的表达式.

I need to go over those statements and check the conditions, since some of them are no longer valid. I want to be able to parse it to a tree, then check each of it leafs (where each leaf is a condition), delete the unwanted leafs and build the full and correct expressions back.

我知道树的每个节点都是由一对第一个方括号和将其封闭的方括号定义的，但是我不知道如何识别此类对以及如何识别它们之间的逻辑符号.

I know that each node of the tree is defined by a pair of the first bracket and the bracket that closes it, but I don't know how to identify such pairs and how to identify the logical sign between them.

除!以外的所有符号都位于两个表达式之间.

All signs except for ! come between two expressions.

推荐答案

听起来像解析:: 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).

The whole thing is an expression. An expression is an operand followed by zero or more binary operators and their operands. Each operand is either a parenthesized expression, '!' followed by an operand, or a word (e.g. cond1).

产生的树中的每个节点均采用以下形式之一:

Every node in the produced tree is in one of the following forms:

• cond1-条件
• { 'op' => '!', 'value' => 'node' }-！应用于另一个节点
• { 'lvalue' => 'node', 'operations' => [ one or more of: { 'op' => 'binop', 'rvalue' => 'node' } ] }-表示节点binop节点binop节点...的一系列一个或多个操作...

• cond1 - a condition
• { 'op' => '!', 'value' => 'node' } - ! applied to another node
• { 'lvalue' => 'node', 'operations' => [ one or more of: { 'op' => 'binop', 'rvalue' => 'node' } ] } - series of one or more operations representing node binop node binop node ...

我没有将一系列二进制操作(例如((cond1) || (cond2) || (cond3)))分解为二进制树，因为您没有提供有关优先级或关联性的信息.

I didn't break series of binary operations (e.g. ((cond1) || (cond2) || (cond3))) into a binary tree because you provided no information about precedence or associativity.

您的示例的输出为:

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

这篇关于解析逻辑表达式并将其转换为Perl中的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！