Existe uma maneira fácil de reduzir um arquivo de texto em seções equilibradas?

Question

Estou tentando analisar alguns dados de um arquivo usando o Perl & Parse :: RecDescent. Não posso jogar o arquivo de dados completo no script Perl, porque o RecDescent levará dias por isso. Por isso, divida o enorme arquivo de dados em pedaços do tamanho de RD para reduzir o tempo de execução.

No entanto, preciso extrair seções entre colchetes e a rotina que tenho agora não é robusta (depende muito da posição do suporte final de uma nova linha). Exemplo:

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

...more sections...

Eu preciso pegar tudo de cell ... { para o fechamento correspondente } que podem ter várias quantidades de espaçamento e subseções.

Deve haver alguma coisa de linha de comando Linux para fazer isso facilmente? Alguma ideia?

Editar: Os arquivos de entrada são de cerca de 8m, gramática ~ 60 regras.

Answer 1

Por que o recuo leva tanto tempo? É porque sua gramática é complexa? Se for esse o caso, você poderá dois um passe de dois níveis usando o Parse :: Recdescent. A idéia é que você definisse uma gramática simples que analisa a célula ... {...} e depois passa a saída analisada do primeiro analisador em uma chamada para analisar :: RecDescent com sua gramática mais complexa. Isso está adivinhando sobre o motivo de o RecDescente estar lento em seus dados.

Outra opção é escrever seu próprio analisador simples que corresponda às entradas da célula, conta o número de aparelhos que ele é visto até agora e encontra o cinto de correspondência quando a contagem de suporte de fechamento é igual à contagem de abertura. Isso deve ser rápido, mas a sugestão acima pode ser mais rápida de implementar e mais fácil de manter.

EDIT: Você definitivamente deve tentar o Parse :: Recdescent com uma gramática simplificada. A complexidade algorítmica da análise de descida recursiva é proporcional ao número de possíveis árvores de análise, o que deve ser algo como é B ^ n, onde B é o número de pontos de ramificação na sua gramática e n é o número de nós.

Se você quiser tentar rolar seu próprio analisador simples para uma primeira passagem pela sua contribuição, o código a seguir pode iniciar.

#!/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 $!;

Editar: alterou o código para evitar arrastar o arquivo inteiro na memória. Embora isso seja trivial para um arquivo de 8 MB, é mais limpo ler o arquivo em linha a linha.

Answer 2

Mostre o que você está alimentando Parse :: Recdescent; Pode ser possível torná -lo muito melhor.

Ou você pode tentar usar Texto :: equilibrado Para analisar o {...}.

Answer 3

Usar yapp Lalr (1) Parser que funciona em tempo linear e espaço constante.