bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/grammar/input/GrammarParser.java

   1 package org.simantics.scl.compiler.parser.grammar.input;
   2
   3 import java.io.DataInputStream;
   4 import java.io.IOException;
   5 import java.util.ArrayList;
   6 import java.util.Arrays;
   7 import java.util.Collections;
   8
   9 public abstract class GrammarParser {
  10     public static final boolean TRACE = true;
  11
  12     private static final int INITIAL_CAPACITY = 16;
  13     private static final int STATE_COUNT = 19;
  14     private static final int TERMINAL_COUNT = 16;
  15     private static final int NONTERMINAL_COUNT = 6;
  16     private static final int PRODUCT_COUNT = 8;
  17
  18     private static final int[] ACTION_ROW_ID = new int[STATE_COUNT];
  19     private static final int[] ACTION_COLUMN_ID = new int[TERMINAL_COUNT];
  20     private static final short[] ACTION_TABLE = new short[56];
  21     private static final int[] ERROR_TABLE = new int[10];
  22     private static final int[] GOTO_ROW_ID = new int[STATE_COUNT];
  23     private static final int[] GOTO_COLUMN_ID = new int[NONTERMINAL_COUNT];
  24     private static final short[] GOTO_TABLE = new short[12];
  25     private static final int[] PRODUCT_LHS = new int[PRODUCT_COUNT];
  26
  27     private static final short STATE_MASK = (short)0x0fff;
  28     private static final short REDUCE_MASK = (short)0x8000;
  29     private static final short POP_MASK = (short)0x4000;
  30     private static final short PUSH_MASK = (short)0x2000;
  31     private static final short ERROR_ACTION = (short)0xffff;
  32     private static final short ACCEPT_ACTION = (short)0xfffe;
  33
  34     public static final String[] TERMINAL_NAMES = new String[] {
  35         "NONTERMINAL",
  36         "EQUALS",
  37         "BAR",
  38         "SEMICOLON",
  39         "INITIAL",
  40         "HASH",
  41         "TERMINAL",
  42         "COMMA",
  43         "SHIFT",
  44         "REDUCE",
  45         "STAR",
  46         "PLUS",
  47         "OPTIONAL",
  48         "LPAREN",
  49         "RPAREN",
  50         "EOF"
  51     };
  52
  53     public static final String[] NONTERMINAL_NAMES = new String[] {
  54         "file",
  55         "declaration",
  56         "prod",
  57         "regexps",
  58         "regexp",
  59         "init$1"
  60     };
  61
  62     static {
  63         try {
  64             DataInputStream input = new DataInputStream(GrammarParser.class.getResourceAsStream("GrammarParser.dat"));
  65             for(int i=0;i<ACTION_ROW_ID.length;++i)
  66                 ACTION_ROW_ID[i] = input.readInt();
  67             for(int i=0;i<ACTION_COLUMN_ID.length;++i)
  68                 ACTION_COLUMN_ID[i] = input.readInt();
  69             for(int i=0;i<ACTION_TABLE.length;++i)
  70                 ACTION_TABLE[i] = input.readShort();
  71             for(int i=0;i<ERROR_TABLE.length;++i)
  72                 ERROR_TABLE[i] = input.readInt();
  73             for(int i=0;i<GOTO_ROW_ID.length;++i)
  74                 GOTO_ROW_ID[i] = input.readInt();
  75             for(int i=0;i<GOTO_COLUMN_ID.length;++i)
  76                 GOTO_COLUMN_ID[i] = input.readInt();
  77             for(int i=0;i<GOTO_TABLE.length;++i)
  78                 GOTO_TABLE[i] = input.readShort();
  79             for(int i=0;i<PRODUCT_LHS.length;++i)
  80                 PRODUCT_LHS[i] = input.readInt();
  81             input.close();
  82         } catch(IOException e) {
  83             e.printStackTrace();
  84         }
  85     }
  86
  87     private static short getAction(int state, int symbol) {
  88         int id = TERMINAL_COUNT*state + symbol;
  89         if( ((ERROR_TABLE[id>>5] >> (id&31))&1) != 0 )
  90             return ERROR_ACTION;
  91         return ACTION_TABLE[ACTION_ROW_ID[state] + ACTION_COLUMN_ID[symbol]];
  92     }
  93
  94     private static short getGoto(int state, int symbol) {
  95         return GOTO_TABLE[GOTO_ROW_ID[state] + GOTO_COLUMN_ID[symbol]];
  96     }
  97
  98     protected abstract Token nextToken();
  99
 100     private Object[] symbolStack = new Object[INITIAL_CAPACITY];
 101     private int symbolStackLength = 0;
 102
 103     private int[] stateStack = new int[INITIAL_CAPACITY];
 104     private int[] symbolStackPositionStack = new int[INITIAL_CAPACITY];
 105     private int stateStackLength = 0;
 106
 107     // For reduce
 108     private int reductionLength;
 109
 110     protected int length() {
 111         return reductionLength;
 112     }
 113
 114     protected Object get(int i) {
 115         if(i < 0 || i >= reductionLength)
 116             throw new IndexOutOfBoundsException();
 117         return symbolStack[symbolStackLength+i];
 118     }
 119
 120     private String parseErrorDescription(int state, Token token, int tokenId) {
 121         StringBuilder b = new StringBuilder();
 122         b.append("Unexpected token '").append(token)
 123          .append("' (").append(TERMINAL_NAMES[tokenId])
 124          .append("). Expected one of ");
 125         ArrayList<String> possibleTerminals = new ArrayList<String>();
 126         for(int i=0;i<TERMINAL_COUNT;++i)
 127             if(getAction(state, i) != ERROR_ACTION)
 128                 possibleTerminals.add(TERMINAL_NAMES[i]);
 129         Collections.sort(possibleTerminals);
 130         for(int i=0;i<possibleTerminals.size();++i) {
 131             if(i > 0)
 132                 b.append(", ");
 133             b.append(possibleTerminals.get(i));
 134         }
 135         b.append('.');
 136         return b.toString();
 137     }
 138
 139     protected abstract RuntimeException syntaxError(Token token, String description);
 140
 141     private static String describeAction(boolean isGoto, int action) {
 142         if(action == ERROR_ACTION)
 143             return "ERROR";
 144         if(action == ACCEPT_ACTION)
 145             return "ACCEPT";
 146         StringBuilder b = new StringBuilder();
 147         if(isGoto)
 148             b.append("GOTO ");
 149         else {
 150             if((action & REDUCE_MASK) != 0) {
 151                 action ^= REDUCE_MASK;
 152                 b.append("REDUCE");
 153             }
 154             else
 155                 b.append("SHIFT");
 156         }
 157         if((action & POP_MASK) != 0) {
 158             action ^= POP_MASK;
 159             b.append(" POP");
 160         }
 161         if((action & PUSH_MASK) != 0) {
 162             action ^= PUSH_MASK;
 163             b.append(" PUSH");
 164         }
 165         b.append(' ').append(action);
 166         return b.toString();
 167     }
 168
 169     private void printState(int state) {
 170         System.out.print("state=" + state + ":");
 171         for(int i=symbolStackLength-1,j=stateStackLength-1;i>=0;--i) {
 172             Object s = symbolStack[i];
 173             if(s instanceof Token)
 174                 System.out.print(" " + TERMINAL_NAMES[((Token)s).id]);
 175             else if(s == null)
 176                 System.out.print(" null");
 177             else
 178                 System.out.print(" " + s.getClass().getSimpleName());
 179             while(j>=0 && symbolStackPositionStack[j]==i)
 180                 System.out.print(" (" + stateStack[j--] + ")");
 181         }
 182         System.out.println();
 183     }
 184
 185     private Object parse(int state) {
 186         while(true) {
 187             Token token = nextToken();
 188             int tokenId = token.id;
 189             if(TRACE)
 190                 System.out.println("---> token " + TERMINAL_NAMES[tokenId] + " \"" + token.text + "\" <---");
 191             while(true) {
 192                 if(TRACE)
 193                     printState(state);
 194                 short action = getAction(state, tokenId);
 195                 if(TRACE)
 196                     System.out.println("    -> action=" + describeAction(false, action));
 197                 //System.out.println(STATE_DESCRIPTIONS[state]);
 198                 if((action & REDUCE_MASK) != 0) {
 199                     if(action == ACCEPT_ACTION)
 200                         return symbolStack[symbolStackLength-1];
 201                     if(action == ERROR_ACTION)
 202                         throw syntaxError(token, parseErrorDescription(state, token, tokenId));
 203                     int popAmount = (action >>> 13)&3;
 204                     if(TRACE) {
 205                         if(popAmount > 0)
 206                             System.out.println("    POP " + popAmount);
 207                     }
 208                     stateStackLength -= popAmount;
 209                     action &= STATE_MASK;
 210
 211                     int reductionBegin = symbolStackPositionStack[--stateStackLength];
 212
 213                     reductionLength = symbolStackLength-reductionBegin;
 214                     symbolStackLength = reductionBegin;
 215
 216                     if(symbolStackLength == symbolStack.length)
 217                         symbolStack = Arrays.copyOf(symbolStack, symbolStackLength*2);
 218                     Object symbol = reduce(action);
 219                     postReduce(symbol);
 220                     symbolStack[symbolStackLength] = symbol;
 221
 222                     state = stateStack[stateStackLength];
 223                     if(TRACE) {
 224                         ++symbolStackLength;
 225                         printState(state);
 226                         --symbolStackLength;
 227                         System.out.println("    nonterminal=" + NONTERMINAL_NAMES[PRODUCT_LHS[action]]);
 228                     }
 229                     action = getGoto(state, PRODUCT_LHS[action]);
 230                     if(TRACE)
 231                         System.out.println("    -> action=" + describeAction(true, action));
 232
 233                     // Pop state
 234                     if((action & POP_MASK) != 0) {
 235                         --stateStackLength;
 236                     }
 237                     // Push state
 238                     if((action & PUSH_MASK) != 0) {
 239                         if(stateStackLength == stateStack.length) {
 240                             stateStack = Arrays.copyOf(stateStack, stateStackLength*2);
 241                             symbolStackPositionStack = Arrays.copyOf(symbolStackPositionStack, stateStackLength*2);
 242                         }
 243                         symbolStackPositionStack[stateStackLength] = symbolStackLength;
 244                         stateStack[stateStackLength++] = state;
 245                     }
 246                     state = action & STATE_MASK;
 247                     ++symbolStackLength;
 248                 }
 249                 else {
 250                     // Pop state
 251                     if((action & POP_MASK) != 0) {
 252                         --stateStackLength;
 253                     }
 254                     // Push state
 255                     if((action & PUSH_MASK) != 0) {
 256                         if(stateStackLength == stateStack.length) {
 257                             stateStack = Arrays.copyOf(stateStack, stateStackLength*2);
 258                             symbolStackPositionStack = Arrays.copyOf(symbolStackPositionStack, stateStackLength*2);
 259                         }
 260                         symbolStackPositionStack[stateStackLength] = symbolStackLength;
 261                         stateStack[stateStackLength++] = state;
 262                     }
 263
 264                     // New state
 265                     state = action & STATE_MASK;
 266
 267                     // Push symbol
 268                     if(symbolStackLength == symbolStack.length)
 269                         symbolStack = Arrays.copyOf(symbolStack, symbolStackLength*2);
 270                     symbolStack[symbolStackLength++] = token;
 271                     break;
 272                 }
 273             }
 274         }
 275     }
 276
 277     public Object parseFile() {
 278         return parse(0);
 279     }
 280
 281
 282     protected Object reduce(int productionId) {
 283         try {
 284         switch(productionId) {
 285         case 0:
 286             return reduceFile();
 287         case 1:
 288             return reduceProduction();
 289         case 2:
 290             return reduceInitial();
 291         case 3:
 292             return reduceProductionRhs();
 293         case 4:
 294             return reduceConcatenation();
 295         case 5:
 296             return reduceTerminal();
 297         case 6:
 298             return reduceUnion();
 299
 300         default:
 301             throw new RuntimeException("Internal parser error.");
 302         }
 303         } catch(RuntimeException e) {
 304             StringBuilder b = new StringBuilder();
 305             b.append("Failed to reduce");
 306             for(int i=0;i<length();++i) {
 307                 Object obj = get(i);
 308                 b.append("\n    (").append(i).append(") \"").append(obj).append('\"');
 309                 if(obj instanceof Token)
 310                     b.append(" (").append(TERMINAL_NAMES[((Token)obj).id]).append(")");
 311                 else
 312                     b.append(" [").append(obj.getClass().getSimpleName()).append("]");
 313             }
 314             throw new RuntimeException(b.toString(), e);
 315         }
 316     }
 317
 318     /**
 319      * file ::= declaration declaration&#42;
 320      */
 321     protected abstract Object reduceFile();
 322     /**
 323      * declaration ::= NONTERMINAL EQUALS prod (BAR prod)&#42; SEMICOLON
 324      */
 325     protected abstract Object reduceProduction();
 326     /**
 327      * declaration ::= INITIAL NONTERMINAL SEMICOLON
 328      */
 329     protected abstract Object reduceInitial();
 330     /**
 331      * prod ::= regexps HASH (TERMINAL COMMA (SHIFT | REDUCE))&#42; TERMINAL
 332      */
 333     protected abstract Object reduceProductionRhs();
 334     /**
 335      * regexps ::= (regexp (regexp | STAR | PLUS | OPTIONAL)&#42;)?
 336      */
 337     protected abstract Object reduceConcatenation();
 338     /**
 339      * regexp ::= NONTERMINAL | INITIAL | TERMINAL | SHIFT | REDUCE
 340      */
 341     protected abstract Object reduceTerminal();
 342     /**
 343      * regexp ::= LPAREN regexps (BAR regexps)&#42; RPAREN
 344      */
 345     protected abstract Object reduceUnion();
 346
 347     protected void postReduce(Object reduced) {
 348     }
 349
 350 }