텍스트 파일을 중괄호 균형 섹션으로 쉽게 채울 수 있습니까?

Question

나는 Perl & Parse :: RecDescent를 사용하여 파일의 일부 데이터를 구문 분석하려고합니다. RecDescent가 일일이 걸리므로 perl 스크립트에서 전체 데이터 파일을 던질 수는 없습니다. 따라서 거대한 데이터 파일을 RD 크기의 청크로 분할하여 런타임을 줄였습니다.

그러나 균형 잡힌 대괄호 안의 섹션을 추출해야하며 지금 가지고있는 루틴은 강력하지 않습니다 (줄 바꿈에서 최종 닫는 대괄호의 위치에 너무 많이 의존 함). 예 :

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

...more sections... 

나는 간격과 하위 섹션의 다양한 양을 가질 수 }을 닫는 일치에 cell ... { 모든 것을 잡아해야합니다.

쉽게 이렇게하려면 몇 가지 Linux 명령 줄이 있어야합니까? 어떤 아이디어?

편집 : 입력 파일은 약 8M 문법 ~ 60 규칙입니다.

Answer 1

왜 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 $!; 

편집 : 전체 파일을 메모리로 스 루핑하지 않도록 코드를 변경했습니다. 이 작업은 8MB 파일에는 쉽지 않지만 줄 단위로 파일을 읽는 것이 더 깔끔합니다.

Answer 2

무엇을 먹이고 있는지 보여주세요. Parse :: RecDescent; 훨씬 더 나아질 수도 있습니다.

또는 Text::Balanced을 사용하여 {...}을 (를) 파싱 할 수 있습니다.

Answer 3

선형 시간 및 상수 공간에서 작동하는 yapp LALR (1) 파서를 사용하십시오.