RegExp Counting System

Question

RegExの値を整数に変換できるシステムを作成しようとしています。ゼロは、最も基本的な正規表現（おそらく"/./"を）だろう、とそれ以降の数字は、より複雑な正規表現の

私の最善のアプローチこれまでの配列に正規表現の中に含まれていることができ、すべての可能な値を固執することだっただろう。ここで

values = [ "!", ".", "\/", "[", "]", "(", ")", "a", "b", "-", "0", "9", .... ] 

した後、次のようにその配列から取る：

def get(integer) 
    if(integer.zero?) 
    return ''; 
    end 

    integer = integer - 1; 

    if(integer < values.length) 
    return values[integer] 
    end 

    get((integer/values.length).floor) + get(integer % values.length); 
end 

sample_regex = /#{get(100)}/; 

このアプローチの最大の問題は、無効な正規表現を容易に生成することができるということです。

私が試していることを達成するために既に確立されたアルゴリズムがありますか？そうでない場合は、何か提案しますか？

ありがとう
スティーブ

Answer 1

私は//が最も単純な正規表現（何にもマッチする）だと言います。 /./はかなり複雑です。/[^\n]/の省略形になっています。それ自体は、はるかに長い式（その式はあなたのキャラクタセットに依存します）の省略形です。次の最も簡単な式は/a/です。aがキャラクタセットの最初の文字です。その最後のステートメントはあなたの列挙に興味深い問題を引き起こします：どの文字セットを使用しますか？任意の列挙は、指定された文字セットに結び付けられます。 //を0とすると、/\x{00}/（ヌル文字にマッチする）は1、/\x{01}/は2などとなります。次に、ASCIIセットを使用した場合、約129個の関心のある正規表現（複数の文字列にマッチするもの）になります。 UNICODE 5.0の場合は1114112になります。

すべての場合、数字を一連のバイトとして扱い、使用している文字セットにそれらのバイトをマップし、正規表現コンパイラを使用してその数字が有効な正規表現かどうかを判断し、有効でない番号を破棄します。

Answer 2

正規表現が正式に再帰的に有限個の要素を適用することによって、定義することができますので、これを行うことができます。代わりに、単に要素を連結し、正規表現のルールに従ってそれらを結合。通常の言語もrecursively enumerableであるため、これは動作することが保証されています。

しかし、これを実装することはおそらく過剰です。これは何のために必要なのですか？ Number -> RegExpのキーと値のペアの単純な辞書は、正規表現を一意の番号に関連付けるのに適していないでしょうか？