Gmailスタイルの詳細検索構文の解析？

Question

Perlを使用してGmailで提供されている検索文字列と似た検索文字列を解析したいと考えています。入力の例は、 "tag：thing by：{user1 user2} {-tag：a by：user3}"となります。私は、このような

{and => [ 
    "tag:thing", 
    {or => [ 
     "by:user1", 
     "by:user2", 
    ]}, 
    {or => [ 
     {not => "tag:a"}, 
     "by:user3", 
    ]}, 
} 

として、ツリー構造に入れたいの一般的なルールは以下のとおりです。宇宙へのデフォルトAND演算子で区切ら

1. トークン。
2. 中括弧内のトークンは代替オプション（OR）です。中カッコは、フィールド指定子の前後に置くことができます。すなわち「by：{user1 user2}」と「{by：user1 by：user2}」は等価である。
3. ハイフンを先頭に付けたトークンは除外されます。

これらの要素は、組み合わせてネストすることもできます。 "{by：user5 - {tag：k by：user3}}など"

私は文脈自由文法を書いてこれらの規則を表現し、それを木に構文解析することを考えています。これは不要ですか？ （これは簡単な正規表現を使って可能ですか？）

文脈自由文法の解析にはどのようなモジュールが推奨されていますか？

（結局これはDBIx ::クラスとデータベースクエリを生成するために使用されます。）

Answer 1

正規表現は非常によく（括弧のような）ネストされた事を行いません。あなたが正規表現のかっこと正確なキャプチャを取得するときには、まともなCFGパーサを持っている可能性があります。 CFGは論理的に正しい構文解析を保証することができますが、正規表現のソリューションでは魔法を多用することになります。私はPerl CFGのライブラリを推薦することはできませんが、コーディングは非常にカタルシス的です。

Answer 2

クエリがツリー構造でない場合は、正規表現が自動的に処理されます。例えば

：

my $search = "tag:thing by:{user1 user2} {-tag:a by:user3}" 
my @tokens = split /(?![^{]*})\s+/, $search; 
foreach (@tokens) { 
    my $or = s/[{}]//g; # OR mode 
    my ($default_field_specifier) = /(\w+):/; 
} 

---

クエリがツリー構造化された場合でも、正規表現は、再帰的な解析がはるかに快適にすることができます

$_ = "by:{user1 z:{user2 3} } x {-tag:a by:user3} zz"; 
pos($_) = 0; 
scan_query(""); 

sub scan_query { 
    my $default_specifier = shift; 
    while (/\G\s*((?:[-\w:]+)|(?={))({)?/gc) { 
     scan_query($1), next if $2; 
     my $query_token = $default_specifier . $1; 
    } 
    /\G\s*\}/gc; 
} 

正規表現は素晴らしい:)です！

Answer 3

YAPP希望することがあります。これを使用して、LALR（1）解析オートマトンを生成し、使用することができます。

Answer 4

Parse::Recdescentは、このような種類のパーサーを生成できます。効果的に使用するには、パーサーの経験が必要です。