/**
 * LR parser for Java generated by the Syntax tool.
 *
 * https://www.npmjs.com/package/syntax-cli
 *
 *   npm install -g syntax-cli
 *
 *   syntax-cli --help
 *
 * To regenerate run:
 *
 *   syntax-cli \
 *     --grammar ~/path-to-grammar-file \
 *     --mode LALR1 \
 *     --output ~/ParserClassName.java
 */

package com.syntax;

import java.lang.reflect.Method;
import java.text.ParseException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.Stack;

{{{MODULE_INCLUDE}}}

/*

The `ParserEvents` class allows defining hooks for certain parse events,
such as initialization of the parser instance, beginning of the parsing, etc.

Default implementation:

  class ParserEvents {
    public static void init() {
      // Parser is created.
    }

    public static void onParseBegin(String _string) {
      // Parsing is started.
    }

    public static void onParseEnd(Object _result) {
      // Parsing is completed.
    }
  }

*/

{{{PARSER_EVENTS_CLASS}}}

{{{TOKENIZER}}}

// --------------------------------------------
// Parser.

class StackEntry {
  public int symbol;
  public Object semanticValue;
  public YyLoc loc;

  public StackEntry(int symbol, Object semanticValue, YyLoc loc) {
    this.symbol = symbol;
    this.semanticValue = semanticValue;
    this.loc = loc;
  }
}

/**
 * Base class for the parser. Implements LR parsing algorithm.
 *
 * Should implement at least the following API:
 *
 * - parse(String StringToParse): object
 * - setTokenizer(Tokenizer tokenizer): void, or equivalent Tokenizer
 *   accessor property with a setter.
 */
public class {{{PARSER_NAME}}} {

  /**
   * Tokenizer instance.
   */
  public Tokenizer tokenizer = null;

  /**
   * Encoded grammar productions table.
   * Format of a record:
   * { <Non-Terminal Index>, <RHS.Length>}
   *
   * Non-terminal indices are 0-Last Non-terminal. LR-algorithm uses
   * length of RHS to pop symbols from the stack; this length is stored
   * as the second element of a record. The last element is an optional
   * name of the semantic action handler. The first record is always
   * a special marker {-1, -1} entry representing an augmented production.
   */
  private static int[][] mProductions = {
    {{{PRODUCTIONS}}}
  };

  /**
   * Cache for the handler methods.
   *
   * Example:
   *
   *   mProductionHandlerMethods[0] = Parser.class.getDeclaredMethod("_handler0");
   *   ...
   */
  private static final Method[] mProductionHandlerMethods = new Method[{{{PRODUCTION_METHODS_COUNT}}}];
  static {
    try {
      {{{PRODUCTION_HANDLER_METHODS}}}
    } catch (Exception ignore) {
      // Ignore since the methods are exact.
    }
  };

  /**
   * Actual parsing table. An array of records, where
   * index is a state number, and a value is a dictionary
   * from an encoded symbol (number) to parsing action.
   * The parsing action can be "Shift/s", "Reduce/r", a state
   * transition number, or "Accept/acc".
   *
   * Example:
   *
   *   mTable.add(
   *     new HashMap<Integer, String>() {{
   *       put(0, "1");
   *       put(3, "s2");
   *       put(4, "s3");
   *     }}
   *   );
   *   ...
   */
  private static List<Map<Integer, String>> mTable = new ArrayList<Map<Integer, String>>();
  static {
    {{{TABLE}}}
  };

  /**
   * Parsing stack. Stores instances of StackEntry.
   */
  Stack<StackEntry> mValueStack = null;

  /**
   * States stack.
   */
  Stack<Integer> mStatesStack = null;

  /**
   * __ holds a result value from a production
   * handler. In the grammar usually used as $$.
   */
  StackEntry __ = null;

  /**
   * Constructor.
   */
  public {{{PARSER_NAME}}}() {
    // A tokenizer instance, which is reused for all
    // `parse` method calls. The actual String is set
    // in the tokenizer.initString("...").
    tokenizer = new Tokenizer();

    // Run init hook to setup callbacks, etc.
    ParserEvents.init();
  }

  /**
   * Production handles. The handlers receive arguments as _1, _2, etc.
   * The result is always stored in __.
   *
   * In grammar:
   *
   * { $$ = (Integer)$1 + (Integer)$3 }
   *
   * Generated:
   *
   * public void _handler0() {
   *   // Prologue
   *   StackEntry _3 = mValueStack.pop();
   *   mValueStack.pop();
   *   StackEntry _1 = mValueStack.pop();
   *
   *   __.semanticValue = (Integer)(_1.semanticValue) + (Integer)(_3.semanticValue);
   * }
   */
  {{{PRODUCTION_HANDLERS}}}

  /**
   * Main parsing method which applies LR-algorithm.
   */
  public Object parse(String str) throws ParseException {
    // On parse begin hook.
    ParserEvents.onParseBegin(str);

    tokenizer.initString(str);

    // Initialize the parsing stack to the initial state 0.
    mValueStack = new Stack<StackEntry>();
    mStatesStack = new Stack<Integer>();
    mStatesStack.push(0);

    Token token = tokenizer.getNextToken();
    Token shiftedToken = null;

    do {
      if (token == null) {
        unexpectedEndOfInput();
      }

      int state = mStatesStack.peek();
      int column = token.type;

      if (!mTable.get(state).containsKey(column)) {
        unexpectedToken(token);
        break;
      }

      String entry = mTable.get(state).get(column);

      // ---------------------------------------------------
      // "Shift". Shift-entries always have 's' as their
      // first char, after which goes *next state number*, e.g. "s5".
      // On shift we push the token, and the next state on the stack.
      if (entry.charAt(0) == 's') {
        YyLoc loc = null;

        // Push token.
        mValueStack.push(new StackEntry(token.type, token.value, token.loc));

        // Push next state number: "s5" -> 5
        mStatesStack.push(Integer.valueOf(entry.substring(1)));

        shiftedToken = token;
        token = tokenizer.getNextToken();
      }

      // ---------------------------------------------------
      // "Reduce". Reduce-entries always have 'r' as their
      // first char, after which goes *production number* to
      // reduce by, e.g. "r3" - reduce by production 3 in the grammar.
      // On reduce, we pop of the stack number of symbols on the RHS
      // of the production, and their pushed state numbers, i.e.
      // total RHS * 2 symbols.
      else if (entry.charAt(0) == 'r') {
        // "r3" -> 3
        int productionNumber = Integer.valueOf(entry.substring(1));
        int[] production = mProductions[productionNumber];

        // The length of RHS is stored in the production[1].
        int rhsLength = production[1];
        if (rhsLength != 0) {
          while (rhsLength-- > 0) {
            // Pop the state number.
            mStatesStack.pop();
          }
        }

        int previousState = mStatesStack.peek();
        int symbolToReduceWith = production[0];

        __ = new StackEntry(symbolToReduceWith, null, null);

        // Execute the semantic action handler.
        this.tokenizer.yytext = shiftedToken != null ? shiftedToken.value : null;
        this.tokenizer.yyleng = shiftedToken != null ? shiftedToken.value.length() : 0;

        try {
          mProductionHandlerMethods[productionNumber].invoke(this);
        } catch (Exception e) {
          e.printStackTrace();
          throw new ParseException(e.getMessage(), 0);
        }

        // Then push LHS onto the stack.
        mValueStack.push(__);

        // And the next state number.
        int nextState = Integer.valueOf(
          mTable.get(previousState).get(symbolToReduceWith)
        );

        mStatesStack.push(nextState);
      }
      // ---------------------------------------------------
      // Accept. Pop starting production and its state number.
      else if (entry.charAt(0) == 'a') {
        // Pop state number.
        mStatesStack.pop();

        // Pop the parsed value.
        StackEntry parsed = mValueStack.pop();

        if (
          mStatesStack.size() != 1 ||
          mStatesStack.peek() != 0 ||
          tokenizer.hasMoreTokens()
        ) {
          unexpectedToken(token);
        }

        Object parsedValue = parsed.semanticValue;
        ParserEvents.onParseEnd(parsedValue);

        return parsedValue;
      }

    } while (tokenizer.hasMoreTokens() || mStatesStack.size() > 1);

    return null;
  }

  private void unexpectedToken(Token token) throws ParseException {
    if (token.type == Tokenizer.EOF_TOKEN.type) {
      unexpectedEndOfInput();
    }

    tokenizer.throwUnexpectedToken(
      token.value.charAt(0),
      token.loc.startLine,
      token.loc.startColumn
    );
  }

  private void unexpectedEndOfInput() throws ParseException {
    parseError("Unexpected end of input.");
  }

  private void parseError(String message) throws ParseException {
    throw new ParseException("Parse error: " + message, 0);
  }
}