public
Created

A grammar that generates Pascal's triangle

  • Download Gist
pascal.pl
Perl
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
#!perl
use 5.010;
use strict;
use warnings;
 
use English qw( -no_match_vars );
use Marpa::R2;
use MarpaX::Simple::Rules '0.2.6', 'parse_rules';
 
my $basic_pascal_rules = parse_rules(<<"RULES");
A ::= a
A ::= E
E ::= Null
RULES
 
sub do_pascal {
my ( $g, $n ) = @_;
my $parse_count = 0;
my $recce = Marpa::R2::Recognizer->new( { grammar => $g } );
 
# Just in case
$recce->set( { max_parses => 999, end => $n } );
for my $token_ix ( 0 .. $n - 1 ) {
defined $recce->read('a') or die "Cannot read char $token_ix";
}
$parse_count++ while $recce->value();
return $parse_count;
} ## end sub do_pascal
 
my @pascal_numbers = (
'1',
'1 1',
'1 2 1',
'1 3 3 1',
'1 4 6 4 1',
'1 5 10 10 5 1',
'1 6 15 20 15 6 1',
'1 7 21 35 35 21 7 1',
'1 8 28 56 70 56 28 8 1',
'1 9 36 84 126 126 84 36 9 1',
'1 10 45 120 210 252 210 120 45 10 1',
'1 11 55 165 330 462 462 330 165 55 11 1',
'1 12 66 220 495 792 924 792 495 220 66 12 1'
);
 
for my $n ( 0 .. 12 ) {
 
my $variable_rule = [ S => [ ('A') x $n ] ];
my $grammar = Marpa::R2::Grammar->new(
{ start => 'S',
rules => [ $variable_rule, @{$basic_pascal_rules} ],
warnings => ( $n ? 1 : 0 ),
}
);
 
$grammar->precompute();
 
my $expected = join q{ }, $pascal_numbers[$n];
my $actual = join q{ }, map { do_pascal( $grammar, $_ ) } 0 .. $n;
say "$actual" or die "say failed: $ERRNO";
if ( $actual ne $expected ) {
say " MISMATCH, above should have been $expected"
or die "say failed: $ERRNO";
}
 
} ## end for my $n ( 0 .. 10 )

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.