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

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

package syntacticanalysis;

import java.util.ArrayList;

/**
 *
 * @author Brandon
 */
public class SignatureCalculator {
    
    /** Creates a new instance of SignatureCalculator */
    public SignatureCalculator() {
    }
    
    /**
     * using the previously constructed first tables, construct
     * the rules signatures.
     */
    public static void constructSignatures(Grammar grammar) {
        
        ArrayList<GrammarRule> rules = grammar.getRules();
        grammar.rulesSignature = new ArrayList<ArrayList<GrammarToken>>();
        
        /* check out each rule */
        for (int i=0; i<rules.size(); i++) {
            
            GrammarRule rule = rules.get(i);
            ArrayList<GrammarToken> rhs = rule.getRhs();
            
            /* is lambda in first(currentCharacter) */
            boolean lambda = true;
            
            for(int j=0; j<rhs.size() && lambda; j++) {
                /* what character are we looking at */
                GrammarToken Xk = rhs.get(j);
                
                ArrayList<GrammarToken> firstXk = grammar.first.get(Xk);
                
                if (Xk instanceof ActionSymbol) {
                    firstXk = new ArrayList<GrammarToken>();
                    firstXk.add(new Terminal("#"));
                }
                
                addToSignature(i, firstXk, grammar.rulesSignature);
                
                /* can this character go to lambda */
                if (!firstXk.contains(new Terminal("#"))) {
                    lambda = false;
                }
                
                /* can everything in the rhs go to lambda */
                if ( (j == rhs.size()-1) && lambda) {
                    /* if so, then add follow(lhs) to the signature */
                    GrammarToken lhs = rule.getLhs();
                    ArrayList<GrammarToken> followLhs = grammar.follow.get(lhs);
                    addToSignature(i, followLhs, grammar.rulesSignature);
                }
            }
        }
    }
    
    /**
     * add everything in firstX to the index-th element of rulesSignature
     */
    private static void addToSignature(int index, ArrayList<GrammarToken> firstX, ArrayList<ArrayList<GrammarToken>> rulesSignature) {
        
        /* make sure we have don't need another signature */
        while(rulesSignature.size() <= index) {
            rulesSignature.add(new ArrayList<GrammarToken>());
        }
        
        /* find the current signature for this rule */
        ArrayList<GrammarToken> sig = rulesSignature.get(index);
        
        /* add everything in firstX to sig, unless it is already there */
        for(int i=0; i<firstX.size(); i++) {
            
            GrammarToken curr = firstX.get(i);
            
            if(curr instanceof ActionSymbol) {
                continue;
            }
            
            if (curr.name.equals("#")) {
                continue;
            }
            
            if (!sig.contains(curr)) {
                sig.add(curr);
            }
        }
    }
    
}