perl - 在 Marpa 语法中制作 0+ 长度列表的简洁方法？

Question

我是马尔巴的新手。我尝试了几种方法来描述语法中 0 个或多个术语的列表，并且我想避免使用多个解析树。

我的语言将恰好有 1 个组件，后跟 0 个以上的子组件:

package => component-rule [subcomponent-rule ...]

我首先尝试的是这样的:

{ lhs => 'Package', rhs => [qw/component-rule subcomponents/] },
{ lhs => 'subcomponents', rhs => [qw/subcomponent-list/] },
{ lhs => 'subcomponent-list', rhs => [qw/subcomponent-rule/], action => 'do_subcomponent_list' },
{ lhs => 'subcomponent-list', rhs => [qw/subcomponent-list subcomponent-rule/], action => 'do_subcomponent_list' },
{ lhs => 'subcomponent-list', rhs => [qw//], action => 'do_subcomponent_empty_list' },
{ lhs => 'subcomponent-rule', rhs => [qw/subcomponent subcomponent-name/], action => 'do_subcomponent' },

(完整代码在帖子末尾。)

这是我的输入:

$recce->read( 'component', );
$recce->read( 'String', 'MO Factory');
$recce->read( 'subcomponent', );
$recce->read( 'String', 'Memory Wipe Station');
$recce->read( 'subcomponent', );
$recce->read( 'String', 'DMO Tour Robot');

我得到两个解析树，第一个带有不受欢迎的 undef，第二个是我更喜欢的。两者都将列表作为固有的树返回。

$VAR1 = [
          {
            'Component' => 'MO Factory'
          },
          [
            [
              {
                'Subcomponent' => undef
              },
              {
                'Subcomponent' => 'Memory Wipe Station'
              }
            ],
            {
              'Subcomponent' => 'DMO Tour Robot'
            }
          ]
        ];
$VAR2 = [
          {
            'Component' => 'MO Factory'
          },
          [
            {
              'Subcomponent' => 'Memory Wipe Station'
            },
            {
              'Subcomponent' => 'DMO Tour Robot'
            }
          ]
        ];

subcomponent-list 的可空规则是允许 0 个子组件的情况，但它在 1+ 个子组件列表的前面引入了 null 元素，这是一种替代解析。 (Marpa 只下降一次循环，谢天谢地。)

我的另一个想法是使 subcomponent-list 不可为空，并引入一个中间规则，即 0 或 1 个 subcomponent-lists:

{ lhs => 'subcomponents', rhs => [qw//] },
{ lhs => 'subcomponents', rhs => [qw/subcomponent-list/] },

这至少消除了多次解析，但我仍然有一个循环，还有一个凌乱的嵌套树要压缩。

是否有更直接的方法来制作 0+ 长度列表或以其他方式使符号可选？

完整示例代码:

#!/usr/bin/perl

use Marpa::R2;
use Data::Dumper;

my $grammar = Marpa::R2::Grammar->new(
    {   start   => 'Package',
        actions => 'My_Actions',
        default_action => 'do_what_I_mean',
        rules => [
        { lhs => 'Package', rhs => [qw/component-rule subcomponents/] },
        { lhs => 'component-name', rhs => [qw/String/] },
        { lhs => 'component-rule', rhs => [qw/component component-name/], action => 'do_component' },
        { lhs => 'subcomponent-name', rhs => [qw/String/] },
        { lhs => 'subcomponent-rule', rhs => [qw/subcomponent subcomponent-name/], action => 'do_subcomponent' },
        { lhs => 'subcomponents', rhs => [qw//] },
        { lhs => 'subcomponents', rhs => [qw/subcomponent-list/] },
        { lhs => 'subcomponent-list', rhs => [qw/subcomponent-rule/], action => 'do_subcomponent_list' },
        { lhs => 'subcomponent-list', rhs => [qw/subcomponent-list subcomponent-rule/], action => 'do_subcomponent_list' },
#       { lhs => 'subcomponent-list', rhs => [qw//], action => 'do_subcomponent_empty_list' },
#       { lhs => 'subcomponent-list', rhs => [qw//],  },
        ],
    }
);

$grammar->precompute();

my $recce = Marpa::R2::Recognizer->new( { grammar => $grammar } );

$recce->read( 'component', );
$recce->read( 'String', 'MO Factory');

if (1) {
$recce->read( 'subcomponent', );
$recce->read( 'String', 'Memory Wipe Station');
$recce->read( 'subcomponent', );
$recce->read( 'String', 'DMO Tour Robot');
$recce->read( 'subcomponent', );
$recce->read( 'String', 'SMO Break Room');
}


my @values = ();
while ( defined( my $value_ref = $recce->value() ) ) {
    push @values, ${$value_ref};
}

print "result is ",Dumper(@values),"\n";

sub My_Actions::do_what_I_mean {

    print STDERR "do_what_I_mean\n";

    # The first argument is the per-parse variable.
    # At this stage, just throw it away
    shift;

    # Throw away any undef's
    my @children = grep { defined } @_;

    # Return what's left
    return scalar @children > 1 ? \@children : shift @children;
}

sub My_Actions::do_component {
    my ( undef, $t1 ) = @_;
    print STDERR "do_component $t1\n";
    my $href = { 'Component' => $t1 };
    return $href;
}
sub My_Actions::do_subcomponent{
    my ( undef, $t1 ) = @_;
    print STDERR "do_subcomponent $t1\n";
    my $href = { 'Subcomponent' => $t1 };
    return $href;
}

sub My_Actions::do_subcomponent_empty_list
{
    print STDERR "do_subcomponent_empty_list\n";
    my $href = { 'Subcomponent' => undef };
    return $href;
}

sub My_Actions::do_subcomponent_list{
    # The first argument is the per-parse variable.
    # At this stage, just throw it away
    shift;

    # Throw away any undef's
    my @children = grep { defined } @_;

    print STDERR "do_subcomponent_list size ",scalar(@children),"\n";
# Do this to collapse recursive trees to a list:
#    @children = map { ref $_ eq "ARRAY" ? @{$_} : $_; } @children;

    return scalar @children > 1 ? \@children : shift @children;
}

Answer 1

指定一个 sequence rule与 min争论。该值可以是 0 (又名 * 正则表达式中的量词)或 1 (又名 + 量词)。您可以通过删除 subcomponents 来做到这一点。和 subcomponent-list规则。而是添加:

{
  lhs => 'subcomponents',
  rhs => ['subcomponent-rule'],
  min => 0,
  action => 'do_subcomponent_list',
}

然后您的语法无需进一步修改即可运行。

最好使用序列规则:不必进行扁平化，并且语法应该更有效。

请注意，我们鼓励您使用无扫描界面。 DSL 很好地抽象了这个问题:

subcomponents ::= <subcomponent rule>* action => do_subcomponent_list