1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#!perl
# Copyright 2014 Jeffrey Kegler
# This file is part of Marpa::R2. Marpa::R2 is free software: you can
# redistribute it and/or modify it under the terms of the GNU Lesser
# General Public License as published by the Free Software Foundation,
# either version 3 of the License, or (at your option) any later version.
#
# Marpa::R2 is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser
# General Public License along with Marpa::R2. If not, see
# http://www.gnu.org/licenses/.
use 5.010;
# Count the ways of parenthesizing N symbols in pairs
# This generates the Catalan numbers
use strict;
use warnings;
use Test::More tests => 7;
use lib 'inc';
use Marpa::R2::Test;
use Marpa::R2;
my $g = Marpa::R2::Grammar->new(
{ start => 'pair',
rules => [
[ pair => [qw(a a)], '::whatever' ],
[ pair => [qw(pair a)], '::whatever' ],
[ pair => [qw(a pair)], '::whatever' ],
[ pair => [qw(pair pair)], '::whatever' ],
],
terminals => ['a'],
}
);
$g->precompute();
sub do_pairings {
my $n = shift;
my $parse_count = 0;
my $recce = Marpa::R2::Recognizer->new( { grammar => $g } );
# An arbitrary maximum is put on the number of parses -- this is for
# debugging, and infinite loops happen.
$recce->set( { max_parses => 999, } );
for my $token_ix ( 0 .. $n - 1 ) {
$recce->read('a');
}
while ( my $value_ref = $recce->value() ) {
$parse_count++;
}
return $parse_count;
} ## end sub do_pairings
my @catalan_numbers = ( 0, 1, 1, 2, 5, 14, 42, 132, 429 );
for my $a ( ( 2 .. 8 ) ) {
my $actual_parse_count = do_pairings($a);
Marpa::R2::Test::is( $actual_parse_count, $catalan_numbers[$a],
"Catalan number $a matches parse count ($actual_parse_count)" );
} ## end for my $a ( ( 2 .. 8 ) )
1; # In case used as "do" file
# Local Variables:
# mode: cperl
# cperl-indent-level: 4
# fill-column: 100
# End:
# vim: expandtab shiftwidth=4:
|
