/*
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/>.
*/

/*
 * FirstCalculator.java
 *
 * Created on March 3, 2008, 12:33 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 FirstCalculator {
    
    /** Creates a new instance of FirstCalculator */
    public FirstCalculator() {
    }
    
    /**
     * attempt to add a given string to the first of a specified nonteminal
     */
    private static boolean addToFirst(GrammarToken X, ArrayList<GrammarToken> toAdd, HashMap<GrammarToken, ArrayList<GrammarToken>> first) {
        
        if (toAdd == null) {
            return false;
        }
        
        if (X instanceof ActionSymbol) {
            return false;
        }
        
        // first, go ahead and retrieve First(X)
        ArrayList<GrammarToken> firstX = first.get(X);
        
        // note if any additions are made to First(X)
        boolean added = false;
        
        for (GrammarToken curr : toAdd) {
            
            /* ignore action symbols */
            if(curr instanceof ActionSymbol) {
                continue;
            }
            
            // is it already in First(X)
            if (!firstX.contains(curr)) {
                firstX.add(curr);
                added = true;
            }
        }
        
        // let the caller know if anything was added
        return added;
    }
    
    /**
     *  follow the algorithms to construct the first table for the
     *  grammar that was read in.
     **/
    public static void constructFirsts(Grammar grammar) {
        
        ArrayList<GrammarRule> rules = grammar.getRules();
        ArrayList<Terminal> terminals = grammar.getTerminals();
        ArrayList<Nonterminal> nonterminals = grammar.getNonterminals();
        
        grammar.first = new HashMap<GrammarToken, ArrayList<GrammarToken>> ();
        boolean keepGoing = true;
        
        for(Terminal terminal : terminals) {
            ArrayList<GrammarToken> firstSet = new ArrayList<GrammarToken>();
            firstSet.add(terminal);
            grammar.first.put(terminal, firstSet);
        }
        
        for(Nonterminal nonterminal : nonterminals) {
            ArrayList<GrammarToken> firstSet = new ArrayList<GrammarToken>();
            grammar.first.put(nonterminal, firstSet);
        }
        
        // loop through the rules until no additions occur over an entire pass
        do {
            
            keepGoing = false;
            for (int i=0; i<rules.size(); i++) {
                
                // what rule are we considering
                GrammarRule rule = rules.get(i);
                
                // get X, the lhs of the rule
                Nonterminal X = rule.getLhs();
                
                // get X1...Xn, the rhs of the rule
                ArrayList<GrammarToken> X1Xn = rule.getRhs();
                
                /**
                 * now, beginning with X1, add First(Xi) to First(X)
                 * until First(Xi) does not contain the empty string.
                 */
                boolean canBeLambda = true;
                
                for(int j=0; j<X1Xn.size() && canBeLambda; j++) {
                    
                    canBeLambda = false;
                    
                    // consider Xi
                    GrammarToken Xi = X1Xn.get(j);
                                        
                    // what is First(Xi)
                    ArrayList<GrammarToken> firstXi = grammar.first.get(Xi);
                    
                    if (Xi instanceof ActionSymbol) {
                        // just assume action symbols can go to empty string
                        firstXi = new ArrayList<GrammarToken>();
                        firstXi.add(new Terminal("#"));
                    }
                    
                    //System.out.println(firstXi);
                    
                    // add it to First(X)
                    if (addToFirst(X, firstXi, grammar.first)) {
                        keepGoing = true;
                    }
                    
                    // can Xi be lambda
                    if (firstXi.contains(new Terminal("#"))) {
                        canBeLambda = true;
                        // at the end of the rule?
                        if (j == X1Xn.size()-1){
                            ArrayList<GrammarToken> lambdaFirstSet = new ArrayList<GrammarToken>();
                            lambdaFirstSet.add(new Terminal("#"));
                            addToFirst(X, lambdaFirstSet, grammar.first);
                        }
                    }
                }
            }
        } while (keepGoing);
    }
}