2

我正在尝试使用 Perl & Parse::RecDescent 从文件中解析一些数据。我不能把完整的数据文件扔给 perl 脚本,因为 RecDescent 需要几天的时间来研究它。因此,我将庞大的数据文件拆分为 RD 大小的块以减少运行时间。

但是,我需要在平衡括号内提取部分,并且我现在拥有的例程并不可靠(它过多地取决于换行符中最后一个右括号的位置)。例子:

cell ( identifier ) {
  keyword2 { };
  ...
  keyword3 { keyword4 {  } };
}

...more sections...

我需要抓住一切,从cell ... {匹配的结束},可以有不同数量的间距和小节。

必须有一些 linux 命令行的东西才能轻松做到这一点?有任何想法吗?

编辑:输入文件大约 8M,语法约 60 条规则。

4

3 回答 3

5

显示你正在喂什么 Parse::RecDescent; 有可能让它变得更好。

或者您可以尝试使用Text::Balanced来解析 { ... }。

于 2009-06-15T23:20:20.670 回答
3

为什么 RecDescent 需要这么长时间?是因为你的语法很复杂吗?如果是这种情况,您可以使用 Parse::RecDescent 进行两次二级传递。这个想法是,您将定义一个简单的语法来解析 cell ... { ... },然后使用更复杂的语法将第一个解析器的解析输出传递给 Parse::RecDescent 的调用。这是猜测 RecDescent 处理数据速度慢的原因。

另一种选择是编写自己的简单解析器,匹配单元格条目,计算到目前为止看到的大括号数,然后在右大括号数等于左大括号数时找到匹配的大括号。这应该很快,但上面的建议可能更快实施并且更容易维护。

编辑:您绝对应该尝试使用简化语法的 Parse::RecDescent。递归下降解析的算法复杂度与可能的解析树的数量成正比,应该类似于 B ^ N,其中 B 是语法中的分支点数,N 是节点数。

如果您想尝试滚动您自己的简单解析器以对您的输入进行第一次传递,以下代码可以帮助您入门。

#!/usr/bin/perl -w

use strict;

my $input_file = "input";
open FILE, "<$input_file" or die $!;

my $in_block = 0;
my $current_block = '';
my $open_bracket_count = 0;
while( my $line = <FILE> ) {
    if ( $line =~ /cell/ ) {
        $in_block = 1;
    }

    if ( $in_block ) {
        while ( $line =~ /([\{\}]{1})/g ) {
            my $token = $1;
            if ( $token eq '{' ) {
                $open_bracket_count++;
            } elsif ( $token eq '}' ) {
                $open_bracket_count--;
            }
        }

        $current_block .= $line;
    }

    if ( $open_bracket_count == 0 && $current_block ne '' ) {
        print '-' x 80, "\n";
        print $current_block, "\n";
        $in_block = 0;
        $current_block = '';
    }
}
close FILE or die $!;

编辑:更改代码以避免将整个文件放入内存中。虽然这对于一个 8MB 的文件来说是微不足道的,但只逐行读取文件会更干净。

于 2009-06-15T23:30:40.240 回答
1

使用在线性时间和恒定空间中工作的yapp LALR(1) 解析器。

于 2009-06-16T10:14:37.923 回答