/*
PseudoCode Interpreted Language (PCIL):  Part of the algoviz@vt collection of algorithm visualizations.
Copyright (C) 2008  Brandon Malone, Frank Hadlock

This file is part of the PseudoCode Interpreted Language.

PseudoCode Interpreted Language is free software: you can redistribute
it and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation, either version 3 of the License,
or (at your option) any later version.

PseudoCode Interpreted Language is distributed in the hope that it will
be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
Public License for more details.

You should have received a copy of the GNU General Public License along with
PseudoCode Interpreted Language.  If not, see
<http://www.gnu.org/licenses/>.
*/

/*
 * FollowCalculator.java
 *
 * Created on March 3, 2008, 1:06 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package syntacticanalysis;

import java.util.ArrayList;
import java.util.HashMap;

/**
 *
 * @author Brandon
 */
public class FollowCalculator {
    
    /** Creates a new instance of FollowCalculator */
    public FollowCalculator() {
    }
    
    
    /**
     * attempt to add a given string to the follow of a specified nonteminal
     */
    private static boolean addToFollow(GrammarToken X, ArrayList<GrammarToken> toAdd, HashMap<GrammarToken, ArrayList<GrammarToken>> follow) {
        
        if (toAdd == null) {
            return false;
        }
        
        if (X instanceof ActionSymbol) {
            return false;
        }
        
        // first, go ahead and retrieve Follow(X)
        ArrayList<GrammarToken> followX = follow.get(X);
        
        // note if any additions are made to Follow(X)
        boolean added = false;
        
        for(GrammarToken curr : toAdd) {
            
            if(curr instanceof ActionSymbol) {
                continue;
            }
            
            // is it already in Follow(X)
            if (!followX.contains(curr)) {
                
                // add it if it isn't
                followX.add(curr);
                added = true;
            }
        }
        
        // let the caller know if anything was added
        return added;
    }
    
    /**
     *  construct the follow tables for the language.
     **/
    public static void constructFollows(Grammar grammar) {
        
        ArrayList<GrammarRule> rules = grammar.getRules();
        ArrayList<Terminal> terminals = grammar.getTerminals();
        ArrayList<Nonterminal> nonterminals = grammar.getNonterminals();
        
        grammar.follow = new HashMap<GrammarToken, ArrayList<GrammarToken>> ();
        boolean keepGoing = true;
        
        for(Nonterminal nonterminal : nonterminals) {
            ArrayList<GrammarToken> followSet = new ArrayList<GrammarToken>();
            grammar.follow.put(nonterminal, followSet);
        }
        
        /* make sure to add $ to follow(s) */
        ArrayList<GrammarToken> endOfSourceFollowSet = new ArrayList<GrammarToken>();
        endOfSourceFollowSet.add(new Terminal("$"));
        addToFollow(grammar.getStartSymbol(), endOfSourceFollowSet, grammar.follow);
        
        /* loop through the rules until no new additions occur over an entire pass */
        do {
            
            keepGoing = false;
            
            for(int i=0; i<rules.size(); i++) {
                
                GrammarRule rule = rules.get(i);
                
                /* search for nonterminals in the rhs */
                ArrayList<GrammarToken> rhs = rule.getRhs();
                
                for(int j=0; j<rhs.size(); j++) {
                    
                    /* what are we examining */
                    GrammarToken curr = rhs.get(j);
                    
                    if(curr instanceof ActionSymbol) {
                        continue;
                    }
                    
                    /* is this a nonterminal */
                    if (curr instanceof Nonterminal ) {
                        
                        /* is there something after this one */
                        if (j<rhs.size()-1) {
                            /* add the first of that character to the follow of this one */
                            GrammarToken nextChar = rhs.get(j+1);
                            
                            boolean needToCheck = true;
                            
                            /* make sure to skip past any action symbols */
                            if (nextChar instanceof ActionSymbol) {
                                int counter = 1;
                                while (nextChar instanceof ActionSymbol) {
                                    counter++;
                                    
                                    if (j + counter >= rhs.size()) {
                                        needToCheck = false;
                                        break;
                                    }

                                    nextChar = rhs.get(j + counter);
                                }
                                
                            }
                            if (needToCheck) {
                                /* then this was not the last symbol in this rule */
                                ArrayList<GrammarToken> toAdd = grammar.first.get(nextChar);
                                
                                /* make sure we actually added something */
                                if (addToFollow(curr, toAdd, grammar.follow) ) {
                                    keepGoing = true;
                                }
                            } else {
                                /* so it must be the last symbol in the rule, so add follow(lhs) to follow(rhs) */
                                
                                GrammarToken lhs = rule.getLhs();
                                ArrayList<GrammarToken> toAdd = grammar.follow.get(lhs);
                                if (addToFollow(curr, toAdd, grammar.follow) ) {
                                    keepGoing = true;
                                }
                            }
                        }
                        /* so it must be the last symbol in the rule, so add follow(lhs) to follow(rhs) */
                        else {
                            GrammarToken lhs = rule.getLhs();
                            ArrayList<GrammarToken> toAdd = grammar.follow.get(lhs);
                            if (addToFollow(curr, toAdd, grammar.follow) ) {
                                keepGoing = true;
                            }
                        }
                        /* can everything after this go to # */
                        boolean add = true;
                        boolean notLast=false;
                        for(int k=j+1;k<rhs.size();k++) {
                            notLast=true;
                            GrammarToken nextChar = rhs.get(k);
                            
                            if (nextChar instanceof ActionSymbol) {
                                continue;
                            }
                            
                            ArrayList<GrammarToken> nextFirst = grammar.first.get(nextChar);
                            
                            if (!nextFirst.contains(new Terminal("#"))) {
                                add = false;
                                break;
                            }
                        }
                        /* add follow(lhs) to follow(rhs) */
                        if (add && notLast) {
                            
                            /* find follow(lhs) */
                            ArrayList<GrammarToken> followLhs = grammar.follow.get(rule.getLhs());
                            
                            /* add it to follow(rhs) */
                            if (addToFollow(curr, followLhs, grammar.follow)) {
                                keepGoing=true;
                            }
                        }
                    } // end if (nonterminal)
                    
                } // end for each character in the rhs
            } // end for each rule
        }  while (keepGoing);
    }
    
}