Есть ли простой способ разбить текстовый файл на сбалансированные разделы? - PullRequest
Новая
       52

Есть ли простой способ разбить текстовый файл на сбалансированные разделы?

2 голосов
/ 16 июня 2009

Я пытаюсь проанализировать некоторые данные из файла, используя Perl & Parse :: RecDescent. Я не могу выбросить полный файл данных в сценарий perl, потому что RecDescent будет занимать несколько дней. Поэтому я разделил огромный файл данных на куски размером с RD, чтобы сократить время выполнения.

Однако мне нужно извлечь секции в сбалансированных скобках, и процедура, которую я сейчас имею, не является надежной (она слишком сильно зависит от положения последней закрывающей скобки от новой строки). Пример: 

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

...more sections...

Мне нужно захватить все, начиная с cell ... { и заканчивая соответствующим закрытием }, которое может иметь различное количество интервалов и подразделов.

Должна быть какая-то вещь командной строки linux, чтобы сделать это легко? Есть идеи?

Редактировать: Входные файлы имеют размер около 8 МБ, грамматика ~ 60 правил.

Ответы [ 3 ]

5 голосов
/ 16 июня 2009

Показать, что вы кормите Parse :: RecDescent; может быть возможно сделать это намного лучше.

Или вы можете попробовать использовать Text :: Balanced для анализа {...}.

3 голосов
/ 16 июня 2009

Почему RecDescent занимает так много времени? Это потому, что ваша грамматика сложна? Если это так, вы можете выполнить двухуровневую передачу, используя Parse :: RecDescent. Идея состоит в том, что вы определяете простую грамматику, которая анализирует ячейку ... {...}, а затем передает проанализированный вывод из первого анализатора в вызов 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 $!;

Редактировать: изменен код, чтобы избежать попадания всего файла в память. Для 8-мегабайтного файла это тривиально, но проще читать файл построчно.

1 голос
/ 16 июня 2009

Использовать yapp LALR (1) парсер, который работает в линейном времени и постоянном пространстве.

...