#!/usr/bin/perl
use strict;
use warnings;
use Parse::RecDescent;
use Data::Dumper;

my $grammar = q{
    evaluate        : ADD_SUB

    #ADD_SUB         : MULT_DIV_MOD ADD_SUB_OP ADD_SUB
    #                  { [@item[1,2,3]] }
    #                  | MULT_DIV_MOD

    # Reverse to ADD_SUB : ADD_SUB ADD_SUB_OP MULT_DIV_MOD | MULT_DIV_MOD
    # Use following formula to eliminate left recursion
    # A : A x | y -> A : y R, R : x R | e
    # Let A = ADD_SUB
    # Let x = ADD_SUB_OP MULT_DIV_MOD
    # let y = MULT_DIV_MOD

    ADD_SUB         : MULT_DIV_MOD ADD_SUB_TAIL
                      { [@item[1,2]] }
    ADD_SUB_TAIL    : ADD_SUB_OP MULT_DIV_MOD ADD_SUB_TAIL
                      { [@item[1..3]] }
                      |

    ADD_SUB_OP      : '+'  |  '-'

    # Same as above
    MULT_DIV_MOD      : GROUP MULT_DIV_MOD_TAIL
                        { [@item[1,2]] }
    MULT_DIV_MOD_TAIL : MULT_DIV_MOD_OP GROUP MULT_DIV_MOD_TAIL
                        { [@item[1..3]] }
                        |

    MULT_DIV_MOD_OP : '*'  |  '/'  |  '%'

    GROUP           : '(' ADD_SUB ')'
                      { $item[2] }
                      | NUMBER

    NUMBER          : INTEGER  |  FLOAT  |  NAN
    INTEGER         : /[+-]?\d+/
    FLOAT           : /([+-]?)(?=\d|\.\d)\d*(\.\d*)?([Ee]([+-]?\d+))?/
    NAN             : /(Inf(inity)?|NaN)/i
};
my $parser = new Parse::RecDescent $grammar;
print Dumper $parser->evaluate('42 - 5 + 1');