#!/usr/bin/perl

#first get all elements
use strict;
use warnings;

my $arg_num = @ARGV;

my @file_content;
my %elem_hash = ();

#check parameter
if ($arg_num != 2)
{
    print "usage:$0 input_rule_file output_file\n";
    exit 1;
}

my $input_rule_file = $ARGV[0];
my $output_file = $ARGV[1];

#open for read
open(RULE_LIST, "<$input_rule_file") or die("could not open $input_rule_file for read\n");
#open for write
if (-e $output_file)
{
    `rm -f $output_file`;
}
open(OUTPUT_FILE, ">$output_file") or die ("could not open $output_file for write\n");

while (1)
{
    my $rule = <RULE_LIST>;

    if (not defined($rule))
    {
        last;
    }

    chomp($rule);

    push(@file_content, $rule);

    my @field = split /\s+/, $rule;

    for (my $index = 0; $index <= $#field; $index++)
    {
        if ($field[$index] =~ /[a-zA-Z]+/)
        {
            $elem_hash{$field[$index]}++;
        }
    }
}

close(RULE_LIST);

my @elems = keys(%elem_hash);
@elems = sort(@elems);

foreach (@elems)
{
    my %first_set_hash = &calc_first_all($_);
    my @first_set = keys(%first_set_hash);
    print OUTPUT_FILE "$_:{@first_set}\n";
}

sub calc_first_all
{
     my %first_set = ();
     my %temp_set = ();

     my $index = 0;

     while ($index <= $#_)
     {
         if ($_[$index] =~ /[A-Z]+/)
         {
             if ($_[$index] =~ /EMPTY/)
             {
                 $first_set{$_[$index]} ++;
                 $index ++;
             }
             else 
             {
                 $first_set{$_[$index]} ++;
                 last;
             }
         }
         elsif ($_[$index] =~ /[a-z]+/)
         {
             %temp_set = &calc_first_one($_[$index]);
             #merge two hash
             %first_set = (%first_set, %temp_set);
             if (!exists($temp_set{"EMPTY"}))
             {
                 last;
             }

             $index ++;
         }
         elsif ( $_[$index] =~ /\{|\[/)
         {
             $index ++;#skip first [ or {

             while ($_[$index] =~ /[a-zA-Z]+/)
             {
                 %temp_set = &calc_first_one($_[$index]);
                 #merge two hash
                 %first_set = (%first_set, %temp_set);
                 if (!exists($temp_set{"EMPTY"}))
                 {
                     last;
                 }

                 $index ++;
             }

             while ($_[$index] =~ /[a-zA-Z]+/)
             {
                 $index ++;
             }

             $first_set{"EMPTY"} ++;

             $index ++;#skip last [ or {
         }
         else
         {
             $index ++;
         }
     }

     $index --;

     if ($index == $#_)
     {
         if ($_[$index] =~ /[A-Z]+/)
         {
             if ($_[$index] =~ /EMPTY/)
             {
                 $first_set{"EMPTY"} ++;
             }
             elsif (exists($first_set{"EMPTY"}))
             {
                 delete($first_set{"EMPTY"});
             }
         }
         elsif ($_[$index] =~ /\{|\[/)
         {
             $first_set{"EMPTY"} ++;
         }
         elsif ($_[$index] =~ /[a-z]+/)
         {
             if (exists($temp_set{"EMPTY"}))
             {
                 $first_set{"EMPTY"} ++;
             }
             else
             {
                 if (exists($first_set{"EMPTY"}))
                 {
                     delete($first_set{"EMPTY"});
                 }
             }
         }
     }
     else
     {
         if (exists($first_set{"EMPTY"}))
         {
             delete($first_set{"EMPTY"});
         }
     }

     %first_set;
}

sub calc_first_one
{
    my %first_set = ();
    my %temp_set = ();

    my @temp_array;

    if ($_[0] =~ /[A-Z]+/)
    {
        $first_set{$_[0]}++;
    }
    elsif ($_[0] =~ /[a-z]+/)
    {
        foreach (@file_content)
        {
            my $rule = $_;

            chomp($rule);

            if ($rule =~ /(${_[0]})\s+->\s+(.+)/)
            {
                @temp_array = split /\s+/, $2;

                %temp_set = &calc_first_all(@temp_array);

                #merge two hash
                %first_set = (%first_set, %temp_set);
            }
        }
    }

    %first_set;
}