Расширяя [опционально], группировки и |или оператор в тексте

Question

Я пытаюсь расширить предложения, включающие [ ] для обозначения необязательных, ( ) для обозначения группировки и | для обозначения оператора or и перечисления всех возможностей. Так, например:

"Hey [there] you [hood]." должно вернуть четыре предложения:

Hey there you hood.
Hey there you.
Hey you hood.
Hey you.

Конечная цель будет выглядеть так:

Input: "(His|Her) dog was [very|extremely] confused."

Output: His dog was very confused.
        His dog was extremely confused.
        His dog was confused.
        Her dog was very confused.
        Her dog was extremely confused.
        Her dog was confused.

Я делаю это с помощью сопоставления регулярных выражений и рекурсии. Я искал как CPAN, так и SO по фразам:

Расширение текста
расширяющиеся предложения
расширяющиеся условия
расширяющиеся опции
расширяющиеся группировки

без удачи.

Спасибо.

---

Я отредактировал этот вопрос в значительной степени, чтобы лучше отразить его эволюцию, и удалил большие части, которые устарели по мере эволюции вопроса. Вопрос выше - это вопрос, на который пытаются ответить большинство ответов ниже.

Мое текущее состояние следующее:

После борьбы с вышеупомянутой проблемой в течение дня у меня есть два решения, очень близких к тому, что я хочу. Один мой, а второй ниже PLT. Однако я решил попробовать принципиально иной подход.

Использование регулярных выражений и ручной синтаксический анализ этих предложений кажется очень уродливым способом ведения дел. Поэтому я решил вместо этого написать грамматику для своего «языка» и использовать генератор синтаксического анализа, чтобы разобрать ее для меня.

Это дает мне дополнительный уровень абстракции и позволяет избежать следующего сценария, описанного Дамианом Конвеем в Perl Best Practices: [about regexps]

вырезать-пасты и изменение-чуть-и-о-теперь он-не-работает-на-все-так-модификация давайте-это несколько больше, и наблюдать, если не -Вот-помогает-не-он-didn't-но-мы-поручены-теперь так может быть, если мы, с изменением что-бит вместо-хммм-that's-ближе, но все еще не -Совершенно-право-возможно-если-я сделал то-третьих, повторение-нежадным-вместо-упс-теперь это-встречно-не-соответствия-на-все-возможно-я-должен-только -post-он-к-PerlMonks.org-увидим, если-они-ноу-как там неправильно

Это также значительно облегчает изменение грамматики этих выражений, и мне нужно было позже поддержать другие конструкции.

---

Последнее обновление:

Я решил свою проблему с помощью набора инструментов с открытым исходным кодом . Это расшифрует версию моего ввода в формате JSGF и сгенерирует преобразователь конечного состояния. Оттуда вы можете пройти через FST, чтобы получить все возможные результаты.

Answer 1

Хорошо, еще один завершите пересмотр ответа.Это будет работать как задумано.:) Теперь он также расширяет вложенные парены.Newline по-прежнему является разделителем, но я добавил способ быстро изменить его на что-то более сложное, если возникнет такая необходимость.

По сути, я начал с замены скобок на parens + pipe, поскольку [word ] и (|word )эквивалентны.

Затем я извлек все инкапсулирующие парены, например, (you |my friend) и (you |my (|friendly ) friend ).Затем я расширил вложенные парены в обычные, например, (you |my (|friendly ) friend ) был заменен на (you |my friendly friend |my friend ).

. После этого слова могут быть обработаны с помощью исходной подпрограммы.

Остается бытьпроверено на более сложных расширениях, но оно отлично работает во время моего тестирования.

Вот пересмотренный код:

use strict;
use warnings;

sub addwords {
    my ($aref, @words) = @_;
    my @total;
    for my $start (@$aref) {
        for my $add (@words) {
            push @total, $start . $add;
        }
    }
    return @total;
}

sub expand_words {
    my $str = shift;
    my @sentences = ('');
    for my $word (word_split($str)) {
        if ($word =~ /^([(])([^)]+)[)]$/) {
            my @options = split /\|/, $2;
            push @options, '' if ($1 eq '[');
            @sentences = addwords(\@sentences, @options);
        } else {
            @sentences = addwords(\@sentences, $word);
        }
    }
    return @sentences;
}

sub fix_parens {
    my $str = shift;
    $str =~ s/\[/(|/g;
    $str =~ s/\]/)/g;
    return $str;
}

sub fix_nested {
    my @array = @_;
    my @return;
    for (my $i=0; $i <= $#array; ) {
        my $inc = 1;
        my ($co, $cc);
        do {
            $co = () = $array[$i] =~ /\(/g;
            $cc = () = $array[$i] =~ /\)/g;
            if ( $co > $cc ) {
                $array[$i] .= $array[$i + $inc++];
            }
        } while ( $co > $cc );
        push @return, expand_nest($array[$i]);
        $i += $inc;
    }
    return @return;
}

sub expand_nest {
    my $str = shift;
    my $co = () = $str =~ /\(/g;
    return $str unless ($co > 1);
    while ($str =~ /([^|(]+\([^)]+\)[^|)]+)/) {
        my $match = $1;
        my @match = expand_words($match);
        my $line = join '|', @match;
        $match =~ s/([()|])/"\\" . $1/ge;
        $str =~ s/$match/$line/ or die $!;
    }
    return $str;
}

sub word_split {
    my $str = shift;
    my $delimeter = "\n";
    $str = fix_parens($str);
    $str =~ s/([[(])/$delimeter$1/g;
    $str =~ s/([])])/$1$delimeter/g;
    my @tot = split /$delimeter/, $str;
    @tot = fix_nested(@tot);
    return @tot;
}
my $str = "Hey [there ](you|my [friendly ]friend) where's my [red|blue]berry?";
my @sentences = expand_words($str);
print "$_\n" for (@sentences);
print scalar @sentences . " sentences\n";

Будет выдавать:

Hey you where's my berry?
Hey you where's my redberry?
Hey you where's my blueberry?
Hey my friend where's my berry?
Hey my friend where's my redberry?
Hey my friend where's my blueberry?
Hey my friendly friend where's my berry?
Hey my friendly friend where's my redberry?
Hey my friendly friend where's my blueberry?
Hey there you where's my berry?
Hey there you where's my redberry?
Hey there you where's my blueberry?
Hey there my friend where's my berry?
Hey there my friend where's my redberry?
Hey there my friend where's my blueberry?
Hey there my friendly friend where's my berry?
Hey there my friendly friend where's my redberry?
Hey there my friendly friend where's my blueberry?
18 sentences

Answer 2

Вот довольно простое решение, если вы преодолеете некоторые уродливые регулярные выражения из-за коллизий между вашим синтаксисом и синтаксисом регулярного выражения. Он допускает синтаксис [] и (), которые на самом деле очень похожи, [foo] такой же, как (foo |).

Основой является замена каждого чередования маркером # 0, # 1, # 2 ... при сохранении их в массиве. затем замените последний маркер, генерируя несколько фраз, затем замените следующий за последним маркер в каждой из этих фраз ... пока все маркеры не будут заменены. Внимательные читатели Perl высшего порядка , без сомнения, найдут более элегантный способ сделать это.

#!/usr/bin/perl

use strict;
use warnings;

while( my $phrase=<DATA>)
  { my $original= $phrase;
    $phrase=~s{\[([^\]]*)\]}{($1| )}g;           # replace [c|d] by (c|d| )
    my $alts=[]; my $i=0;
    while( $phrase=~ s{\(([^)]*)\)}{#$i})        # replace (a|b) ... (c|d| )  by #0 ... #1
      { push @$alts, [ split /\|/, $1 ]; $i++;   # store [ ['a', 'b'], [ 'c', 'd', ' '] ]
      }

    my $expanded=[$phrase];                       # seed the expanded list with the phrase

    while( @$alts) { expand( $alts, $expanded); } # expand each alternation, until none left

    print "$original    - ", join( "    - ", @$expanded), "\n\n";

  }

exit;

# expand the last #i of the phrase in all the phrases in $expanded
sub expand
  { my( $alts, $expanded)=@_;
    my @these_alts= @{pop(@$alts)};   # the last alternations 
    my $i= @$alts;                    # the corresponding index in the phrases

    @$expanded= map { my $ph= $_;               
                     map { my $ph_e= $ph;       
                           $ph_e=~ s{#$i}{$_};  # replace the marker #i by one option
                           $ph_e=~ s{ +}{ };    # fix double spaces
                           $ph_e;
                         } @these_alts          # for all options
                   } @$expanded                 # for all phrases stored so far
  }


__DATA__
(His|Her) dog was [very|extremely

Answer 3

Данные :: Сформировать . Я нашел это, когда искал комбинацию , которая является математическим термином того, что вы делаете со своими наборами слов.