テキストファイルを括弧で囲まれたセクションにチャンクする簡単な方法はありますか？

Question

私は、Perl & Parse :: RecDescentを使ってファイルからいくつかのデータを解析しようとしています。私はPerlスクリプトで完全なデータファイルを投げることはできません。なぜなら、RecDescentはそれについて数日を要するからです。そこで私は膨大なデータファイルをRDサイズのチャンクに分割してランタイムを減らしました。

しかし、私はバランスの取れた括弧内のセクションを抽出する必要があります。私が現在行っているルーチンは堅牢ではありません（改行からの最後の閉じ括弧の位置にあまり依存しません）。例：

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

...more sections... 

私はcell ... {からの間隔とサブセクションの様々な量を持つことができます}を閉じるマッチングにすべてを取得する必要があります。

これを簡単に行うには、いくつかのLinuxコマンドラインが必要ですか？何か案は？

編集：入力ファイルは約8M、文法〜60ルールです。

Answer 1

なぜRecDescentは時間がかかりますか？あなたの文法は複雑なのですか？その場合、Parse :: RecDescentを使用して2つのバイレベルパスを行うことができます。その考え方は、セルを解析する簡単な文法を定義することです... {...}そして、より複雑な文法で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行ずつ読み込むだけです。

Answer 2

あなたが食べているものを表示するParse :: RecDescent;それをもっと良くすることが可能かもしれません。

または、Text::Balancedを使用して{...}を解析できます。

Answer 3

yapp LALR（1）パーサーは、線形の時間と一定の空間で動作します。