2

Perl & Parse::RecDescent を使用して、ファイルからいくつかのデータを解析しようとしています。RecDescent はデータ ファイルを調べるのに何日もかかるため、perl スクリプトで完全なデータ ファイルをスローすることはできません。そこで、実行時間を短縮するために、巨大なデータファイルを 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 を使用して 2 レベル パスを作成できます。cell ... { ... } を解析する単純な文法を定義し、最初のパーサーからの解析済み出力を、より複雑な文法を使用して Parse::RecDescent への呼び出しに渡すという考え方です。これは、RecDescent がデータに対して遅い理由を推測しています。

もう 1 つのオプションは、セル エントリに一致する独自の単純なパーサーを作成し、これまでに表示された中かっこの数をカウントし、右中かっこの数が左中かっこの数と等しいときに一致する中かっこを見つけることです。それは速いはずですが、上記の提案は実装がより速く、保守がより簡単になる可能性があります。

編集: 単純化された文法で 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 のファイルでは些細なことですが、ファイルを 1 行ずつ読み取る方が簡潔です。

于 2009-06-15T23:30:40.240 に答える
1

線形時間と定数空間で動作するyapp LALR(1) パーサーを使用します。

于 2009-06-16T10:14:37.923 に答える