import java.util.*;

/**
 * Shift-reduce parser
 * 
 * @author Nobo Komagata 
 * @version 5/30/03
 */
public class ShiftReduceParser
{
    // Grammar rules (productions) based on grammarArea
    Grammar grammar;
    
    // Input words based on inputArea
    Input input;
    
    // For shift-reduce parsing
    ParseStack stack = new ParseStack();
    
    // For backtracking and alternatives handling
    private ConfigStack configStack = new ConfigStack();
    
    // Temporary storage for possible reductions
    private Reductions reductions;
    // Current
    private int curReduction;
    // Status
    private boolean reductionOnHold = false;

    /**
     * Constructor for objects of class ShiftReduceParser
     */
    public ShiftReduceParser(String grammarArea, String inputStr) 
    {
        grammar = new Grammar(grammarArea);
        input = new Input(inputStr);
    }

    /**
     * Shift operation
     * 
     * @param       None
     * @return      Message
     */
    public String shift() {
        if (input.length() < 1)
            return "Warning: Nothing to shift";

        // save the current config for backtracking
        configStack.pushS(new Configuration((ParseStack) stack.clone(), 
                          (Input) input.clone()));

        String current = input.at(0);
        stack.pushS(new Category(current, null));
        //                                no semantics at this point
        input.removeAt(0);
        return "Info: Shifted = " + current;
    }
    
    /**
     * Reduce operation
     *
     * @param       None
     * @return      Message
     */
    public String reduce() {

        // When "reduce" button is pressed after alternatives have been found
        // (not applicable to the first time press of "reduce")
        if (reductionOnHold) {
            Production prod = 
                grammar.productions.at(reductions.at(curReduction).productionID);

            // save the current config for backtracking
            configStack.pushS(new Configuration((ParseStack) stack.clone(), 
                      (Input) input.clone()));

            // syntax-directed translation based on the Production
            String sem = translate(prod);

            for (int i = 0; i < reductions.at(curReduction).handleLen; ++i) {
                stack.popS();
            }

            stack.pushS(new Category(prod.lhs.type, sem));

            reductionOnHold = false;
            return "Info: Reduction = " + prod.toString();
        }

        // Find and keep alternative reductions
        int[] match = new int[grammar.productions.length()];
        reductions = new Reductions();

        for (int i = 0; i < grammar.productions.length(); ++i) {
            // Identify "handle" matches like the following
            // Stack: ..., X, Y
            // RHS: X Y
            match[i] = 
                lengthOfMatchedHandle(stack, grammar.productions.at(i).rhs);
            if (match[i] > 0)
                // Reduction cases are recorded with the folloing info: 
                // 1. Production ID
                // 2. Length of the matched handle
                reductions.add(new Reduction(i, match[i]));
        }

        if (reductions.length() == 0)
            return "Warning: Nothing to reduce";

        // No alternatives; execute the current one
        if (reductions.length() == 1) {
            // save the current config for backtracking
            configStack.pushS(new Configuration((ParseStack) stack.clone(), 
                              (Input) input.clone()));
            Production prod = 
                grammar.productions.at(reductions.at(0).productionID);

            // syntax-directed translation based on the Production
            String sem = translate(prod);

            for (int i = 0; i < reductions.at(0).handleLen; ++i) {
                stack.popS();
            }

            stack.pushS(new Category(prod.lhs.type, sem));
            return "Info: Reduction = " + prod.toString();
        }

        // Alternatives exist; Set the first available as the current
        reductionOnHold = true;
        curReduction = 0;
        Production prod = 
            grammar.productions.at(reductions.at(curReduction).productionID);

        return "Info: Press REDUCE to apply " + prod.toString() + "or press ALTERNATIVE";
    }
    
    /**
     * Find the length of the matched handle
     *
     * @param       Parse stack, RHS of the current production
     * @return      Length (0 if not matched)
     */
    private int lengthOfMatchedHandle(ParseStack stack, Category[] rhs) {
        // Work on a copy to keep the original intact
        ParseStack copy = (ParseStack) stack.clone();

        // RHS = [cat1, cat2, ..., catN]
        // match catN with the stack top, etc.
        for (int i = rhs.length - 1; i >= 0; --i) {
            if (copy.emptyS())
                return 0;

            // tmp: type of the last category of the RHS
            // (the index part "_#" must be removed)
            StringTokenizer tok = new StringTokenizer(rhs[i].type);
            String tmp = tok.nextToken("_");

            if (!copy.peekS().type.equals(tmp))
                return 0;
            else
                copy.popS();
        }

        return rhs.length;
    }
    
    /**
     * Translate the relevant portion of the input based on 
     * the current Production
     * 
     * Example: 
     *
     * @param       Production
     * @return      String
     */
    private String translate(Production prod) {
        // Work on a copy to keep the original intact
        ParseStack copy = (ParseStack) stack.clone();
        String sem = new String(prod.lhs.sem);

        if (!copy.emptyS()) {
            for (int i = prod.rhs.length - 1; i >=0; --i) {
                Category cat = copy.popS();
                if (cat.sem == null)
                    continue;

                sem = replaceStr(sem, prod.rhs[i].type, cat.sem);
            }
        }

        return sem;
    }
    
    /**
     * Replace all the instances of the specified string with another
     *
     * @param       Text String, "From" String, "To" String
     * @return      String
     */
    private String replaceStr(String str, String from, String to) {
        int pos = str.indexOf(from);
        if (pos < 0)
            return str;

        if (str.length() > pos + from.length() 
            && Character.isLetter(str.charAt(pos + from.length())))
            return str.substring(0, pos) + from 
                + replaceStr(str.substring(pos + from.length()), from, to);
        else
            return str.substring(0, pos) + to 
                + replaceStr(str.substring(pos + from.length()), from, to);
    }
    
    /**
     * Move to the next alternative
     *
     * @param       None
     * @return      Message
     */
    public String alternative() {
        if (!reductionOnHold)
            return "Warning: No alternative available";

        ++curReduction;
        if (curReduction >= reductions.length())
            curReduction = 0;

        Production prod = 
            grammar.productions.at(reductions.at(curReduction).productionID);

        return "Info: Press REDUCE to apply " + prod.toString()  
            + "or press ALTERNATIVE";
    }
    
    /**
     * Backtrack to the previous configuration
     *
     * @param       None
     * @return      Message
     */
    public String backtrack() {
        if (configStack.emptyS())
            return "Warning: No more backtracking";

        Configuration config = configStack.popS();
        stack = config.stack;
        input = config.input;
        return "Info: Backtracking successful";
     }
}