Używanie wyrażeń regularnych do porównywania numerów

Question

Jest to oczywisty przypadek "robisz to źle". I w rzeczywistości nie zamierza robić tego, ale rozmowa w pracy zachęciły to pytanie:

można wygenerować wyrażenie regularne, aby określić, czy liczba całkowita jest mniejsza niż arbitralne wartości.

Dla niektórych wartości jest to łatwe. Dla liczb całkowitych mniejszych niż 1000, \ d {1,3} powinno wystarczyć. Dla liczb całkowitych < 500, jest nieco trudniejsze, ale nie takie złe, jak możesz użyć [0-4] {0,1} \ d {1,2}.

Gdy dojdziesz do wartości arbitralnych, staje się on znacznie trudniejszy. Na przykład wszystkie liczby mniejsze niż 255 będą miały wartość \ d {1,2} | [0-1] \ d {2} | [2] [0-4] \ d | [2] [5] [0-4].

Czy istnieje jedno wyrażenie regularne, które działa tutaj? Czy musisz programowo wygenerować wyrażenie regularne?

(I znowu, chciałbym zwrócić uwagę, że nie mam zamiaru faktycznie to robi. Oczywiście przy użyciu „foo < bar” w swoim ulubionym języku programowania jest o wiele bardziej wydajny i łatwy do odczytania.)

Answer 1

You” konieczne będzie wygenerowanie wyrażenia dla każdego numeru granicznego. Powiedzmy, że było to wyrażenie regularne, które wykonałoby zadanie. Wtedy to wyrażenie regularne musiałoby przyjmować jako wejście pewną sekwencję znaków. Wiemy jednak, że wyrażenia regularne i skończone automaty stanów są równoważne, więc jest to to samo, co stwierdzenie, że możemy skonstruować FSM, ponieważ możliwa liczba jest nieograniczona, co wymagałoby nieograniczonej liczby stanów, co jest sprzeczne z definicją FSA.

Answer 2

To całkiem proste.

#!/usr/bin/env perl 
use strict; 
use warnings; 
use Regexp::Assemble; 

for my $n (@ARGV) { 
    my $asm = new Regexp::Assemble; 
    for (1 .. $n) { $asm->add($_) } 
    for ($asm->re){ 
     s/\)$/\$/; 
     s/^[^:]*:/^/; 
     print "$n => /$_/\n"; 
    } 
} 

Teraz uruchom go znaleźć wzór, który pasuje do liczb całkowitych od 1 do tej liczby:

$ perl /tmp/ra 5 15 153 401 1144 
5 => /^[12345]$/ 
15 => /^(?:[23456789]|1[]?)$/ 
153 => /^(?:1(?:[6789]|5[0123]?|0\d?|1\d?|2\d?|3\d?|4\d?)?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)$/ 
401 => /^(?:1(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|3(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|4(?:[123456789]|0[01]?)?|5\d?|6\d?|7\d?|8\d?|9\d?)$/ 
1144 => /^(?:1(?:0(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|1(?:[56789]|4[]?|0\d?|1\d?|2\d?|3\d?)?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|3(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|4(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|5(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|6(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|7(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|8(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|9(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?)$/