Cụm từ thông dụng có thể được sử dụng để khớp với các mẫu lồng nhau không?

Question

Có thể viết cụm từ thông dụng khớp với mẫu lồng nhau xảy ra với số lần không xác định không? Ví dụ, một biểu thức chính quy có thể khớp với dấu ngoặc mở và đóng khi có một số dấu ngoặc mở/đóng không xác định được lồng trong các dấu ngoặc ngoài?

Ví dụ:

public MyMethod() 
{ 
    if (test) 
    { 
    // More { } 
    } 

    // More { } 
} // End 

nên phù hợp:

{ 
    if (test) 
    { 
    // More { } 
    } 

    // More { } 
} 

Answer 1

No. Thật dễ dàng. Một automaton hữu hạn (là cấu trúc dữ liệu bên dưới một biểu thức chính quy) không có bộ nhớ ngoài trạng thái của nó, và nếu bạn có tùy ý làm tổ sâu, bạn cần một automaton tùy ý lớn, va chạm với khái niệm hữu hạn automaton.

Bạn có thể so khớp các phần tử lồng nhau/ghép nối với độ sâu cố định, trong đó độ sâu chỉ bị giới hạn bởi bộ nhớ của bạn, vì máy tự động rất lớn. Tuy nhiên, trong thực tế, bạn nên sử dụng một automaton đẩy xuống, ví dụ như một trình phân tích cú pháp cho ngữ pháp không có ngữ cảnh, ví dụ LL (từ trên xuống) hoặc LR (từ dưới lên). Bạn phải thực hiện hành vi thời gian chạy tồi tệ hơn vào tài khoản: O (n^3) so với O (n), với n = chiều dài (đầu vào).

Có nhiều trình tạo phân tích cú pháp không thể thực hiện được, ví dụ ANTLR cho Java. Tìm một ngữ pháp hiện tại cho Java (hoặc C) cũng không khó.
Đối với nền hơn: Automata Theory tại Wikipedia

Answer 2

Không, bạn đang đi vào cõi Context Free Grammars tại điểm đó.

Answer 3

No. Bạn cần trình phân tích cú pháp toàn diện cho loại sự cố này.

Answer 4

lẽ làm việc giải pháp Perl, nếu chuỗi là trên cùng một dòng:

my $NesteD ; 
$NesteD = qr/ \{([^{}] | (??{ $NesteD }))* \} /x ; 

if ($Stringy =~ m/\b(\w+$NesteD)/x) { 
    print "Found: $1\n" ; 
    } 

HTH

EDIT: kiểm tra:

• http://dev.perl.org/perl6/rfc/145.html
thông tin 10
• ruby: http://www.ruby-forum.com/topic/112084
• hơn perl: http://www.perlmonks.org/?node_id=660316
• thậm chí nhiều hơn perl: https://metacpan.org/pod/Text::Balanced
• perl, perl, perl: http://perl.plover.com/yak/regex/samples/slide083.html

Và một điều nữa bởi Torsten Marek (người đã chỉ ra một cách chính xác, rằng nó không phải là regex nữa):

• http://coding.derkeiler.com/Archive/Perl/comp.lang.perl.misc/2008-03/msg01047.html

Answer 5

Pumping lemma for regular languages là lý do tại sao bạn không thể làm điều đó.

Automaton được tạo sẽ có số trạng thái hữu hạn, ví dụ k, vì vậy một chuỗi dấu ngoặc mở k + 1 bị ràng buộc có trạng thái lặp lại ở đâu đó (khi quá trình tự động hóa các ký tự). Một phần của chuỗi giữa cùng một trạng thái có thể được nhân đôi vô số lần và automaton sẽ không biết sự khác biệt.

Cụ thể, nếu nó chấp nhận dấu ngoặc mở k + 1 theo sau là dấu ngoặc k + 1 (mà nó cần), nó cũng sẽ chấp nhận số niềng răng đang mở theo sau là dấu ngoặc đóng k + 1 không thay đổi (mà nó không nên t).

Answer 6

Cụm từ thông dụng phù hợp sẽ không thể thực hiện được khi bạn rời khỏi lĩnh vực Ngôn ngữ thông thường để tiếp cận các lãnh thổ trong Ngữ cảnh tự do.

Tuy nhiên, các gói "cụm từ thông dụng" mà nhiều ngôn ngữ cung cấp sẽ mạnh hơn rất nhiều. Ví dụ: Lua cụm từ thông dụng có ký hiệu "%b()" sẽ khớp với dấu ngoặc đơn cân bằng. Trong trường hợp của bạn, bạn sẽ sử dụng "%b{}"

Một công cụ tinh vi khác tương tự như sed là gema, nơi bạn sẽ khớp các dấu ngoặc nhọn cân bằng rất dễ dàng với {#}.

Vì vậy, tùy thuộc vào các công cụ bạn có theo ý của mình, "cụm từ thông dụng" của bạn (theo nghĩa rộng hơn) có thể khớp với dấu ngoặc đơn lồng nhau.

Answer 7

như zsolt đã đề cập, một số động cơ regex hỗ trợ đệ quy - tất nhiên, đây thường là những người sử dụng thuật toán backtracking để nó sẽ không đặc biệt hiệu quả. ví dụ: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

Answer 8

Có, nếu có .NET RegEx-engine. .Net engine hỗ trợ máy trạng thái hữu hạn được cung cấp với một chồng bên ngoài. thấy details

Answer 9

Điều này dường như làm việc: /(\{(?:\{.*\}|[^\{])*\})/m

Answer 10

Sử dụng biểu thức thông thường để kiểm tra các mô hình lồng nhau là rất dễ dàng.

'/(\((?>[^()]+|(?1))*\))/' 

Answer 11

Sử dụng kết hợp đệ quy trong công cụ regex PHP nhanh hơn so với kết hợp thủ tục của dấu ngoặc đơn. đặc biệt là với các chuỗi dài hơn.

http://php.net/manual/en/regexp.reference.recursive.php

ví dụ:

$patt = '!\((?: (?: (?>[^()]+) | (?R))*) \)!x'; 

preg_match_all($patt, $str, $m); 

vs

matchBrackets($str); 

function matchBrackets ($str, $offset = 0) { 

    $matches = array(); 

    list($opener, $closer) = array('(', ')'); 

    // Return early if there's no match 
    if (false === ($first_offset = strpos($str, $opener, $offset))) { 
     return $matches; 
    } 

    // Step through the string one character at a time storing offsets 
    $paren_score = -1; 
    $inside_paren = false; 
    $match_start = 0; 
    $offsets = array(); 

    for ($index = $first_offset; $index < strlen($str); $index++) { 
     $char = $str[ $index ]; 

     if ($opener === $char) { 
      if (! $inside_paren) { 
       $paren_score = 1; 
       $match_start = $index; 
      } 
      else { 
       $paren_score++; 
      } 
      $inside_paren = true; 
     } 
     elseif ($closer === $char) { 
      $paren_score--; 
     } 

     if (0 === $paren_score) { 
      $inside_paren = false; 
      $paren_score = -1; 
      $offsets[] = array($match_start, $index + 1); 
     } 
    } 

    while ($offset = array_shift($offsets)) { 

     list($start, $finish) = $offset; 

     $match = substr($str, $start, $finish - $start); 
     $matches[] = $match; 
    } 

    return $matches; 
} 

Answer 12

My question+answer có liên quan và tôi làm cho một biểu thức và meta-biểu thức có thể phù hợp với tùy ý cấp (hữu hạn) của tổ. Nó khá là thú vị nhưng bạn có thể mong đợi điều gì khác? Sử dụng backreferences trong trận đấu nếu động cơ của bạn hỗ trợ nó.