1

我想解析一个类似于 Gmail 使用 Perl 提供的搜索字符串。一个示例输入是“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 的数据库查询。）

4

4 回答 4

1

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

于 2009-07-26T06:59:41.837 回答
0

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

例如：

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;
}

正则表达式很棒:)！

于 2009-07-26T07:01:29.210 回答
0

YAPP可能会做你想做的事。您可以使用它来生成然后使用 LALR(1) Parsing Automaton。

于 2009-07-26T07:19:33.060 回答
0

Parse::Recdescent可以为这类事情生成解析器。不过，您可能需要一些解析器经验才能有效地使用它。

于 2009-07-27T14:51:43.690 回答