Last year I wrote about how we can build an extended syntax for Marpa on top of the basic interface.

For the counted rule lhs ::= rhs{5} where you want to match the right hand side multiple times, we can just generate the rhs item 5 times.

This isn’t the right thing. Jeffrey pointed out that you can build these {min,max} rules up out of blocks.

Then I remembered a piece of code from Elements of Programming which explained that it’s possible to generate the Fibonacci series in O(log n) time. The same should be possible for the counted rules.

So I wrote this code that generated these rules, not in O(log n) time, but with more rules and less items in the rules. This scales better for big n.

$ ./counted_rule.pl lhs rhs 5 action
_rhs_block_5  ::= _rhs_block_4 _rhs_block_1    action => do_flatten_list
_rhs_block_4  ::= _rhs_block_2 _rhs_block_2    action => do_flatten_list
_rhs_block_2  ::= rhs rhs                      action => do_flatten_list
_rhs_block_1  ::= rhs                          action => do_flatten_list
lhs           ::= _rhs_block_5                 action => action

$ ./counted_rule.pl lhs rhs 50 action
_rhs_block_50 ::= _rhs_block_48 _rhs_block_2   action => do_flatten_list
_rhs_block_48 ::= _rhs_block_32 _rhs_block_16  action => do_flatten_list
_rhs_block_32 ::= _rhs_block_16 _rhs_block_16  action => do_flatten_list
_rhs_block_16 ::= _rhs_block_8 _rhs_block_8    action => do_flatten_list
_rhs_block_8  ::= _rhs_block_4 _rhs_block_4    action => do_flatten_list
_rhs_block_4  ::= _rhs_block_2 _rhs_block_2    action => do_flatten_list
_rhs_block_2  ::= rhs rhs                      action => do_flatten_list
lhs           ::= _rhs_block_50                action => action

The number of rules scales logarithmically.

The code for counted-rule.pl is on GitHub.