[字符串匹配算法] 嵌套匹配

Perlvim

进行过许多文本解析之后，发现有一个非常有用的算法：在具有嵌套结构的文本中匹配字符串：

字符串： if a then if b then if c then d end if e then f end end end

要求匹配出所有  if .. end 的结构, 按照深度保存成一个散列：

{
    0 => [ q<if a then if b then if c then d end if e then f end end end> ],
    1 => [ q<if b then if c then d end if e then f end end> ],
    2 => [ q<if c then d end>, q<f e then f end>],
}

通常的正则匹配是从内层进行匹配的，也有用递归的算法来从最外层开始计算。

rubyish

修正了一些错误:{:3_188:}

1. #!/usr/bin/perl
   
2. use 5.016;
   
3. 
   
4. my $s = 'if a then if b then if c then d end if e then f end end end';
   
5. sub parse {
   
6.     my @data = map /(\S.*\S)/, split /(if|end)/, shift;
   
7.     my ( %i, %result );
   
8.     $data[$_] =~ /(if|end)/ and push @{$i{$1}}, $_ for 0 .. $#data;
   
9.     @{$i{if}} = reverse @{$i{if}};
   
10.     my @L = reverse 0 .. $#{$i{end}};
    
11.     for my $i ( 0 .. $#{$i{end}} ) {
    
12.         if ( $i{if}[$i] > $i{end}[$i] ) {
    
13.             my $l;
    
14.             $i{if}[++$l] < $i{end}[$i] and last for @{$i{if}};
    
15.             @{ $i{if} }[ $i .. $l ] = reverse @{$i{if}}[$i .. $l];
    
16.             @L[$i .. $l] = ($L[$l]) x ($l - $i + 1);
    
17.         }
    
18.         my $join = "@data[$i{if}[$i] .. $i{end}[$i]]";
    
19.         push @{$result{$L[$i]}}, $join;
    
20.     }
    
21.     \%result;
    
22. }
    
23. my $r1 = parse $s;
    
24. 
    
25. say "$_ => ", join ' | ', @{ $r1->{$_} } for sort keys $r1;

复制代码

Perlvim

rubyish 写的代码编译器最喜欢。

rubyish

Perlvim 发表于 2013-04-25 06:04
rubyish 写的代码编译器最喜欢。

十分感谢编译器的错爱~{:3_188:} {:3_188:} {:3_188:}

kk861123

回复 1# Perlvim

这样可以吗?

1. #!/usr/bin/perl -w
   
2. use strict;
   
3. use Data::Dumper;
   
4. 
   
5. my $line = 'if a then if b then if c then d end if e then f end end end';
   
6. my @aConds;
   
7. if ( $line =~ /^( # GROUP 1
   
8.                   if \s*\S+\s* then \s*
   
9.                     ( (?1)+  # Recurse to start of GROUP 1
   
10.                        |     
    
11.                        \S+   
    
12.                     ) (?{ unshift @aConds, $2 }) # unshift the string matched in inner
    
13.                   \s*end\s*
    
14.                 )
    
15.                       (?{ unshift @aConds, $1 }) # unshift the string matched in GROUP 1
    
16.                 $/x ) {
    
17.     print Dumper \@aConds;
    
18. }
    
19. 
    

复制代码

rubyish

回复 5# kk861123


很好的解决方案 {:3_203:} {:3_203:}

第一次看到   (?1)  这件宝贝 大牛
它是什么？

kk861123

回复 6# rubyish


    perlre中搜"(?PARNO) (?-PARNO) (?+PARNO) (?R) (?0) "
我理解的是pattern捕捉，(?1) 代表了第一个group中的pattern

Perlvim

回复 5# kk861123

结果对，但没看懂。



   

kk861123

文本解析的利器：

1. use Parse::RecDescent;

复制代码

1. #!/usr/bin/perl
   
2. use strict; use warnings;
   
3. use Data::Dumper;
   
4. use Parse::RecDescent;
   
5. 
   
6. # define grammar
   
7. my $grammar = <<'EOG';
   
8. start: condition { $return = [ $item[1] ] }
   
9. condition: 'if' expr 'then' condition(s?) 'end' { $return = [ @item[1..5] ] }
   
10.          | 'if' expr 'then' code 'end'          { $return = [ @item[1..5] ] }
    
11. expr: /\S+/
    
12. code: /\S+/
    
13. EOG
    
14. 
    
15. my $line = 'if a then if b then if c then d end if e then f end end end';
    
16. my $parser = new Parse::RecDescent($grammar)
    
17.     or die "Compilation error!\n";
    
18. 
    
19. my $raConds = $parser->start($line);
    
20. print Dumper $raConds;
    
21. exit;

复制代码

result:

1. $VAR1 = [
   
2.           [
   
3.             'if',
   
4.             'a',
   
5.             'then',
   
6.             [
   
7.               [
   
8.                 'if',
   
9.                 'b',
   
10.                 'then',
    
11.                 [
    
12.                   [
    
13.                     'if',
    
14.                     'c',
    
15.                     'then',
    
16.                     'd',
    
17.                     'end'
    
18.                   ],
    
19.                   [
    
20.                     'if',
    
21.                     'e',
    
22.                     'then',
    
23.                     'f',
    
24.                     'end'
    
25.                   ]
    
26.                 ],
    
27.                 'end'
    
28.               ]
    
29.             ],
    
30.             'end'
    
31.           ]
    
32.         ];

复制代码

kk861123

回复 8# Perlvim


    加了点注释，你再看看？