解析 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",
    ]},
}

一般规则是：

1. 标记以空格分隔，默认为 AND 运算符。
2. 大括号中的标记是替代选项 (OR)。 大括号可以位于字段说明符之前或之后。 即“by:{user1 user2}”和“{by:user1 by:user2}”是等效的。
3. 排除以连字符为前缀的标记。

这些元素也可以组合和嵌套：例如“{by:user5 -{tag:k by:user3}} 等”。

我正在考虑编写一个上下文无关语法来表示这些规则，然后将其解析到树中。 这有必要吗？ （使用简单的正则表达式可以实现这一点吗？）

建议使用哪些模块来解析上下文无关语法？

（最终这将用于使用 DBIx::Class 生成数据库查询。）

Answer 1

如果您的查询不是树形结构，那么正则表达式将为您完成这项工作。

例如：

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 2

Parse::Recdescent 可以生成这种排序的解析器的东西。 不过，您可能需要一些解析器方面的经验才能有效地使用它。

Answer 3

正则表达式不能很好地处理嵌套的事情（例如括号）。 当您获得正则表达式计数括号并正确捕获时，您可能就拥有了一个不错的 CFG 解析器。 CFG 可以在逻辑上保证正确的解析，而使用正则表达式解决方案则需要更多的魔法。 我不能推荐任何 Perl CFG 库，但编写一个听起来很宣泄。

Answer 4

YAPP 可能会做你想做的事。 您可以使用它来生成然后使用 LALR(1) 解析自动机。