#!/usr/bin/perl

#first get all NON TERMINAL
use strict;
use warnings;

my $arg_num = @ARGV;

my @file_content;
my %elem_hash = ();

my %non_recu = ();

#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-z]+/)
        {
            $elem_hash{$field[$index]}++;
        }
    }
}

close(RULE_LIST);

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

foreach (@elems)
{
    print "----------------------------------$_ start----------------------------------\n";
    my %follow_set_hash = &calc_follow($_);
    my @follow_set_array = keys(%follow_set_hash);
    print "@follow_set_array\n";
    print OUTPUT_FILE "$_:{@follow_set_array}\n";
}

sub calc_follow
{
    my %follow_set = ();
    my %temp_follow_set = ();
    my %temp_first_set = ();
    my @param_array;
    my @temp_array;
    my $is_start = 1;

    my $temp;

    $non_recu{$_[0]} ++;

    if ($non_recu{$_[0]} != 1)
    {
        return;
    }

    foreach (@file_content)
    {
        my $rule = $_;

        chomp($rule);

        if ($rule =~ /(.+)\s+->(.+)/)
        {
            my $father = $1;
            my $right = $2;

            if ($right =~ /\s+${_[0]}\s+(.*)/)
            {
                $is_start = 0;
                $temp = $1;

                if ($right =~ /\{(.*\s+${_[0]}\s+)\}/)
                {
                    @param_array = split /\s+/, $1;
                    
                    %temp_first_set = &calc_first_all(@param_array);

                    if (exists($temp_first_set{"EMPTY"}))
                    {
                        delete $temp_first_set{"EMPTY"};
                    }

                    %follow_set = (%follow_set, %temp_first_set);
                }

                if (!($temp =~ /[a-zA-Z]+|\{|\{/))
                {
                    if ($_[0] ne $father)
                    {
                        print "calc father $father\n";
                        %temp_follow_set = &calc_follow($father);
                        %follow_set = (%follow_set, %temp_follow_set);
                    }

                }
                else
                {
                    @param_array = split /\s+/, $temp;
                    %temp_first_set = &calc_first_all(@param_array);

                    if (exists($temp_first_set{"EMPTY"}))
                    {
                        if ($_[0] ne $father)
                        {
                            print "calc father $father\n";
                            %temp_follow_set = &calc_follow($father);
                            %follow_set = (%follow_set, %temp_follow_set);
                        }
                        #delete EMPTY from temp_first_set
                        delete $temp_first_set{"EMPTY"};
                    }

                    %follow_set = (%follow_set, %temp_first_set);
                }
            }
        }
    }

    $non_recu{$_[0]} = 0;

    if ($is_start)
    {
        $follow_set{"EOF"} ++;
    }

    %follow_set;
}

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;
}