Heckendorn

Heckendorn.pl

use 5.010;
use strict;
use warnings;

=pod Almost SLIF Example from http://marvin.cs.uidaho.edu/Teaching/CS445/grammar.html

Here is a tree structure as nested parentheses. For instance (ant) or (cat, bat) 
or ((cat), (bat)) or ((cat, bat, dog), ant). 
Note the hierarchical handling of each feature. 
Note also that when <tree> points up from <thing> to the top of the grammar 
creating the nesting effect. Matching <tree> requires that parentheses 
be removed for each time through the loop to the top. This prevents infinite 
recursion because you will run out of parentheses if you remove a pair each time through.

<tree> ::= "(" <list> ")"                    // deal with parentheses
<list> ::= <thing> | <list> "," <thing>      // do the list of things
<thing> ::= <tree> | <name>                  // things are more trees or names
<name> ::= ant | bat | cow | dog

=cut

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

my $grammar_source = q{
    :default ::= action => [symbol, values]
    lexeme default = action => [symbol, values] latm => 1

    <tree> ::= '(' <list > ')'
    <list> ::= <thing> | <list> ',' <thing>
    <thing> ::= <tree> | <name>             
    <name> ::= 'ant' | 'bat' | 'cow' | 'dog' | 'cat'

    :discard ~ whitespace
    whitespace ~ [\s+]
};

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

my @input = (
    '(cat, bat)',
    '((cat), (bat))',
    '(ant, (cat, bat, dog), ant)',
);

for my $input (@input){
    warn "# $input";
    my $r = Marpa::R2::Scanless::R->new( { grammar => $g } );
    $r->read( \$input );
    my $ast = ${ $r->value() };
    warn Dumper $ast;
}