Concise way to make a 0+ length list in Marpa grammar?

Question

I'm new to Marpa. I've tried a couple ways to describe a list of 0 or more terms in my grammar, and I want to avoid multiple parse trees.

My language will have exactly 1 component followed by 0+ subcomponents:

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

What I tried first was this:

{ 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' },

(Full code at end of post.)

Here's my input:

$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');

I get two parse trees, the first one with an undesirable undef, and the second one which I prefer. Both give the list back as inherently a tree.

$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'
            }
          ]
        ];

The nullable rule for subcomponent-list was to allow the case of 0 subcomponents, but it introduces the null element on the front of a list of 1+ subcomponents, which is an alternate parse. (Marpa descends the cycle only once, thank goodness.)

My other idea was to make subcomponent-list non-nullable, and introduce an intermediate rule that is 0 or 1 subcomponent-lists:

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

This at least eliminated the multiple parse, but I still have a cycle, and a messy nested tree to compress.

Is there a more direct way to make a 0+ length list or otherwise make a symbol optional?

Full sample code:

#!/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

Specify a sequence rule with the min argument. The value may either be 0 (aka the * quantifier in regexes) or 1 (aka the + quantifier). You can do this by removing the subcomponents and subcomponent-list rules. Instead add:

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

Your grammar then runs without further modifications.

Using sequence rules is preferable: No flattening has to take place, and the grammar should be more efficient.

---

Note that you are encouraged to use the Scanless Interface. The DSL abstracts nicely over this issue:

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