Разбор синтаксиса расширенного поиска в стиле Gmail?

Question

Я хочу проанализировать строку поиска, аналогичную той, которая предоставляется 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. Токены в фигурных скобках являются альтернативными вариантами (ИЛИ). Скобки могут идти до или после спецификатора поля. то есть «by: {user1 user2}» и «{by: user1 by: user2}» эквивалентны.
3. Токены с префиксом дефиса исключаются.

Эти элементы также могут быть объединены и вложены: например, "{by: user5 - {tag: k by: user3}} и т. д.".

Я подумываю написать контекстно-свободную грамматику для представления этих правил, а затем разбора ее в дерево. Разве это не нужно? (Возможно ли это с помощью простых регулярных выражений?)

Какие модули рекомендуются для разбора контекстно-свободных грамматик?

(В конце концов, это будет использоваться для создания запроса к базе данных с DBIx :: Class.)

Answer 1

Regex не делает вложенные вещи (например, круглые скобки) очень хорошо. К тому времени, когда вы получите регулярное выражение, скопированное скобкой и захватом, вы, вероятно, можете иметь достойный синтаксический анализатор CFG. CFG могут логически гарантировать правильный синтаксический анализ, в то время как с помощью решения регулярного выражения вы много оставляете до магии. Я не могу рекомендовать какие-либо Perl CFG-библиотеки, но кодирование одного звучит очень cathartic.

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 может делать то, что вы хотите. Вы можете использовать его для генерации, а затем использовать LARR (1) Parsing Automaton.

Answer 4

Parse::Recdescent может генерировать парсеры для такого рода вещей. Вам, вероятно, нужен некоторый опыт работы с парсерами, чтобы использовать его эффективно.