#!/usr/bin/perl
#####
# from http://www.adp-gmbh.ch/perl/rec_descent.html
#
# adapted to return a parse tree as well as the numeric result.
#
###############
use strict;
use warnings;

use Parse::RecDescent;

my $grammar = q {

start:          statements               { \%item }

statements:     statement ';' statements { \%item }
              | statement		 { \%item }

statement:      variable '=' statement   { \%item }
              | expression               { \%item }

expression:     term '+' expression      { \%item }
              | term '-' expression      { \%item }
              | term			 { \%item }

term:           factor '*' term          { \%item }
              | factor '/' term          { \%item }
              | factor			 { \%item }			 

factor:         number			 { \%item }
              | variable                 { \%item }
              | '+' factor               { \%item }
              | '-' factor               { \%item }
              | '(' statement ')'        { \%item }

number:         /\d+/                    { { __VALUE__ => $item[1]} }

variable:       /[a-z]+/i                { { __NAME__ => $item[1]} }

};

my $parser = Parse::RecDescent->new($grammar);
# my $text   = "three=3;six=2*three;eight=three+5;2+eight*six+50";
my $text = "1 + 2 * 3 + 4";
my $result = $parser->start($text);

sub display {
  my ($node, $indent) = @_;
  if (ref $node eq 'HASH'){
    print " {\n";
    for my $key (sort keys %$node){
      next if $key =~ /RULE|ACTION/;
      print " "x $indent . " $key => ";
      display($node->{$key}, $indent+2);
    }
    print " "x$indent ." }\n";
  }
  elsif (not ref $node){
    print "$node\n";
  }
}
print "The parse tree of '$text' is \n";
display($result,0);




