Как сделать правила последовательности Марпы жадными?

Question

Я работаю над Marpa::R2 грамматика, которая группирует элементы в тексте. Каждая группа может содержать только элементы определенного вида, но без явного разделения. Это вызывает проблемы, потому что x...x (где . представляет элемент, который может быть частью группы) может быть сгруппирован как x(...)x, x(..)(.)x, x(.)(..)x, x(.)(.)(.)x, Другими словами, грамматика очень неоднозначна.

Как я могу устранить эту двусмысленность, если я хочу только x(...)x разбор, т.е. если я хочу заставить + квантификатор, который ведет себя только как "жадный" (как в регулярных выражениях Perl)?

В приведенной ниже грамматике я попытался добавить rank наречия к правилам последовательности, чтобы расставить приоритеты Group над Sequence, но это не похоже на работу.

Ниже приведен тестовый пример, который демонстрирует это поведение.

use strict;
use warnings;

use Marpa::R2;
use Test::More;

my $grammar_source = <<'END_GRAMMAR';
inaccessible is fatal by default
:discard ~ space
:start ::= Sequence

Sequence
    ::= SequenceItem+  action => ::array
SequenceItem
    ::= WORD    action => ::first
    |   Group   action => ::first
Group
    ::= GroupItem+  action => [name, values]
GroupItem
    ::= ('[') Sequence (']')  action => ::first

WORD    ~ [a-z]+
space   ~ [\s]+
END_GRAMMAR

my $input = "foo [a] [b] bar";

diag "perl $^V";
diag "Marpa::R2 " . Marpa::R2->VERSION;

my $grammar = Marpa::R2::Scanless::G->new({ source => \$grammar_source });
my $recce = Marpa::R2::Scanless::R->new({ grammar => $grammar });

$recce->read(\$input);

my $parse_count = 0;
while (my $value = $recce->value) {
    is_deeply $$value, ['foo', [Group => ['a'], ['b']], 'bar'], 'expected structure'
        or diag explain $$value;
    $parse_count++;
}
is $parse_count, 1, 'expected number of parses';

done_testing;

Выход теста (FAIL):

# perl v5.18.2
# Marpa::R2 2.09
ok 1 - expected structure
not ok 2 - expected structure
#   Failed test 'expected structure'
#   at - line 38.
#     Structures begin differing at:
#          $got->[1][2] = Does not exist
#     $expected->[1][2] = ARRAY(0x981bd68)
# [
#   'foo',
#   [
#     'Group',
#     [
#       'a'
#     ]
#   ],
#   [
#     ${\$VAR1->[1][0]},
#     [
#       'b'
#     ]
#   ],
#   'bar'
# ]
not ok 3 - expected number of parses
#   Failed test 'expected number of parses'
#   at - line 41.
#          got: '2'
#     expected: '1'
1..3
# Looks like you failed 2 tests of 3.

Answer 1

Правила последовательности разработаны для не хитрых случаев. Правила последовательности всегда могут быть переписаны как правила BNF, когда дело становится сложным, и это то, что я предлагаю здесь. Следующее заставляет ваш тест работать:

use strict;
use warnings;

use Marpa::R2;
use Test::More;

my $grammar_source = <<'END_GRAMMAR';
inaccessible is fatal by default
:discard ~ space

# Three cases
# 1.) Just one group.
# 2.) Group follows by alternating words and groups.
# 3.) Alternating words and groups, starting with words
Sequence ::= Group action => ::first
Sequence ::= Group Subsequence action => [values]
Sequence ::= Subsequence action => ::first

Subsequence ::= Words action => ::first

# "action => [values]" makes the test work unchanged.
# The action for the next rule probably should be
# action => [name, values] in order to handle the general case.
Subsequence ::= Subsequence Group Words action => [values]

Words ::= WORD+ action => ::first
Group
::= GroupItem+  action => [name, values]
GroupItem
::= ('[') Sequence (']')  action => [value]

WORD    ~ [a-z]+
space   ~ [\s]+
END_GRAMMAR

my $input = "foo [a] [b] bar";

diag "perl $^V";
diag "Marpa::R2 " . Marpa::R2->VERSION;

my $grammar = Marpa::R2::Scanless::G->new( { source  => \$grammar_source } );
my $recce   = Marpa::R2::Scanless::R->new( { grammar => $grammar } );

$recce->read( \$input );

my $parse_count = 0;
while ( my $value = $recce->value ) {
is_deeply $$value, [ 'foo', [ Group => ['a'], ['b'] ], 'bar' ],
    'expected structure'
    or diag explain $$value;
$parse_count++;
} ## end while ( my $value = $recce->value )
is $parse_count, 1, 'expected number of parses';

done_testing;

Answer 2

Однозначная грамматика:

Sequence           : WORD+ SequenceAfterWords
                   | Group SequenceAfterGroup

SequenceAfterWords : Group SequenceAfterGroup
                   |

SequenceAfterGroup : WORD+ SequenceAfterWords
                   |

---

Джеффри Кеглер говорит, что ведение с помощью рекурсии обрабатывается в Марпе более эффективно. Тот же самый подход, принятый выше, может быть использован для этого.

Sequence            : SequenceBeforeWords WORD+
                    | SequenceBeforeGroup Group

SequenceBeforeWords : SequenceBeforeGroup Group
                    |

SequenceBeforeGroup : SequenceBeforeWords WORD+
                    |

---

В обоих случаях,

Group     : GroupItem+

GroupItem : '[' Sequence ']'