# csc3005h
# tutorial 2/3 parser
# hussein suleman
# 22 august 2006

# parse and create tree
sub parse_tree
{
   (parse_children ('', $_[0]))->[1]->[0];
}
sub parse_children
{
   my ($head, $tail) = @_;
   my @childnodes = ();
   my $lefts = 0;
   for ( my $i=0; $i<length ($tail); $i++ )
   {
      if (substr ($tail, $i, 1) eq '(') { $lefts++; }
      elsif (substr ($tail, $i, 1) eq ')') { $lefts--; }
      elsif ((substr ($tail, $i, 1) eq ',') && ($lefts == 0)) { substr ($tail, $i, 1) = '#'; }
   }
   my @tailpieces = split ('#', $tail);
   foreach my $newhead (@tailpieces)
   {
      my $newtail = '';
      if (index ($newhead, '(') > -1)
      {
         $newtail = substr ($newhead, index ($newhead, '(')+1);
         $newtail = substr ($newtail, 0, length ($newtail)-1);
         $newhead = substr ($newhead, 0, index ($newhead, '('));
      }
      push (@childnodes, parse_children ($newhead, $newtail));
   }
   
   [ $head, [ @childnodes ] ];
}

# node->[0] tag
# node->[1] child nodes
# node->[1]->[0] first child node
# node->[1]->[0]->[0] first child node tag
# node->[1]->[0]->[1] first child node child nodes

# general form
#  node->[tag/children]->[childno]

# output tree
sub output_tree
{
   my ($node) = @_;
   ($node->[0]).(($#{$node->[1]} == -1)?'':('('.(join (',', map { output_tree ($_) } @{$node->[1]})).')'));
}


# sample code to read in, output, and extract data
my $tree = parse_tree ('print(integer(42))');
print output_tree ($tree)."\n";
print "ROOT = ".$tree->[0]."\n";
print "INTEGER = ".$tree->[1]->[0]->[1]->[0]->[0]."\n";
