src/java.xml/share/classes/com/sun/java_cup/internal/runtime/lr_parser.java
changeset 47359 e1a6c0168741
parent 47216 71c04702a3d5
child 47712 bde0215f1f70
equal deleted inserted replaced
47358:d07d5f7cab35 47359:e1a6c0168741
     1 /*
     1 /*
     2  * Copyright (c) 2003, 2005, Oracle and/or its affiliates. All rights reserved.
     2  * Copyright (c) 2003, 2017, Oracle and/or its affiliates. All rights reserved.
     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     4  *
     4  *
     5  * This code is free software; you can redistribute it and/or modify it
     5  * This code is free software; you can redistribute it and/or modify it
     6  * under the terms of the GNU General Public License version 2 only, as
     6  * under the terms of the GNU General Public License version 2 only, as
     7  * published by the Free Software Foundation.  Oracle designates this
     7  * published by the Free Software Foundation.  Oracle designates this
   270   protected Symbol cur_token;
   270   protected Symbol cur_token;
   271 
   271 
   272   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   272   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   273 
   273 
   274   /** The parse stack itself. */
   274   /** The parse stack itself. */
   275   protected Stack stack = new Stack();
   275   protected Stack<Symbol> stack = new Stack<>();
   276 
   276 
   277   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   277   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   278 
   278 
   279   /** Direct reference to the production table. */
   279   /** Direct reference to the production table. */
   280   protected short[][] production_tab;
   280   protected short[][] production_tab;
   320    * @param top       the index of the top element of the parse stack.
   320    * @param top       the index of the top element of the parse stack.
   321    */
   321    */
   322   public abstract Symbol do_action(
   322   public abstract Symbol do_action(
   323     int       act_num,
   323     int       act_num,
   324     lr_parser parser,
   324     lr_parser parser,
   325     Stack     stack,
   325     Stack<Symbol>     stack,
   326     int       top)
   326     int       top)
   327     throws java.lang.Exception;
   327     throws java.lang.Exception;
   328 
   328 
   329   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   329   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   330 
   330 
   569             throw new Error("Symbol recycling detected (fix your scanner).");
   569             throw new Error("Symbol recycling detected (fix your scanner).");
   570 
   570 
   571           /* current state is always on the top of the stack */
   571           /* current state is always on the top of the stack */
   572 
   572 
   573           /* look up action out of the current state with the current input */
   573           /* look up action out of the current state with the current input */
   574           act = get_action(((Symbol)stack.peek()).parse_state, cur_token.sym);
   574           act = get_action((stack.peek()).parse_state, cur_token.sym);
   575 
   575 
   576           /* decode the action -- > 0 encodes shift */
   576           /* decode the action -- > 0 encodes shift */
   577           if (act > 0)
   577           if (act > 0)
   578             {
   578             {
   579               /* shift to the encoded state by pushing it on the stack */
   579               /* shift to the encoded state by pushing it on the stack */
   601                   stack.pop();
   601                   stack.pop();
   602                   tos--;
   602                   tos--;
   603                 }
   603                 }
   604 
   604 
   605               /* look up the state to go to from the one popped back to */
   605               /* look up the state to go to from the one popped back to */
   606               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
   606               act = get_reduce((stack.peek()).parse_state, lhs_sym_num);
   607 
   607 
   608               /* shift to that state */
   608               /* shift to that state */
   609               lhs_sym.parse_state = act;
   609               lhs_sym.parse_state = act;
   610               lhs_sym.used_by_parser = true;
   610               lhs_sym.used_by_parser = true;
   611               stack.push(lhs_sym);
   611               stack.push(lhs_sym);
   624                   unrecovered_syntax_error(cur_token);
   624                   unrecovered_syntax_error(cur_token);
   625 
   625 
   626                   /* just in case that wasn't fatal enough, end parse */
   626                   /* just in case that wasn't fatal enough, end parse */
   627                   done_parsing();
   627                   done_parsing();
   628                 } else {
   628                 } else {
   629                   lhs_sym = (Symbol)stack.peek();
   629                   lhs_sym = stack.peek();
   630                 }
   630                 }
   631             }
   631             }
   632         }
   632         }
   633       return lhs_sym;
   633       return lhs_sym;
   634     }
   634     }
   659       debug_message("============ Parse Stack Dump ============");
   659       debug_message("============ Parse Stack Dump ============");
   660 
   660 
   661       /* dump the stack */
   661       /* dump the stack */
   662       for (int i=0; i<stack.size(); i++)
   662       for (int i=0; i<stack.size(); i++)
   663         {
   663         {
   664           debug_message("Symbol: " + ((Symbol)stack.elementAt(i)).sym +
   664           debug_message("Symbol: " + (stack.get(i)).sym +
   665                         " State: " + ((Symbol)stack.elementAt(i)).parse_state);
   665                         " State: " + (stack.get(i)).parse_state);
   666         }
   666         }
   667       debug_message("==========================================");
   667       debug_message("==========================================");
   668     }
   668     }
   669 
   669 
   670   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   670   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   696   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   696   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   697 
   697 
   698   /** Do debug output for stack state. [CSA]
   698   /** Do debug output for stack state. [CSA]
   699    */
   699    */
   700   public void debug_stack() {
   700   public void debug_stack() {
   701       StringBuffer sb=new StringBuffer("## STACK:");
   701       StringBuilder sb=new StringBuilder("## STACK:");
   702       for (int i=0; i<stack.size(); i++) {
   702       for (int i=0; i<stack.size(); i++) {
   703           Symbol s = (Symbol) stack.elementAt(i);
   703           Symbol s = stack.get(i);
   704           sb.append(" <state "+s.parse_state+", sym "+s.sym+">");
   704           sb.append(" <state "+s.parse_state+", sym "+s.sym+">");
   705           if ((i%3)==2 || (i==(stack.size()-1))) {
   705           if ((i%3)==2 || (i==(stack.size()-1))) {
   706               debug_message(sb.toString());
   706               debug_message(sb.toString());
   707               sb = new StringBuffer("         ");
   707               sb = new StringBuilder("         ");
   708           }
   708           }
   709       }
   709       }
   710   }
   710   }
   711 
   711 
   712   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   712   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   760 
   760 
   761           /* current state is always on the top of the stack */
   761           /* current state is always on the top of the stack */
   762           //debug_stack();
   762           //debug_stack();
   763 
   763 
   764           /* look up action out of the current state with the current input */
   764           /* look up action out of the current state with the current input */
   765           act = get_action(((Symbol)stack.peek()).parse_state, cur_token.sym);
   765           act = get_action((stack.peek()).parse_state, cur_token.sym);
   766 
   766 
   767           /* decode the action -- > 0 encodes shift */
   767           /* decode the action -- > 0 encodes shift */
   768           if (act > 0)
   768           if (act > 0)
   769             {
   769             {
   770               /* shift to the encoded state by pushing it on the stack */
   770               /* shift to the encoded state by pushing it on the stack */
   796                   stack.pop();
   796                   stack.pop();
   797                   tos--;
   797                   tos--;
   798                 }
   798                 }
   799 
   799 
   800               /* look up the state to go to from the one popped back to */
   800               /* look up the state to go to from the one popped back to */
   801               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
   801               act = get_reduce((stack.peek()).parse_state, lhs_sym_num);
   802               debug_message("# Reduce rule: top state " +
   802               debug_message("# Reduce rule: top state " +
   803                              ((Symbol)stack.peek()).parse_state +
   803                              (stack.peek()).parse_state +
   804                              ", lhs sym " + lhs_sym_num + " -> state " + act);
   804                              ", lhs sym " + lhs_sym_num + " -> state " + act);
   805 
   805 
   806               /* shift to that state */
   806               /* shift to that state */
   807               lhs_sym.parse_state = act;
   807               lhs_sym.parse_state = act;
   808               lhs_sym.used_by_parser = true;
   808               lhs_sym.used_by_parser = true;
   824                   unrecovered_syntax_error(cur_token);
   824                   unrecovered_syntax_error(cur_token);
   825 
   825 
   826                   /* just in case that wasn't fatal enough, end parse */
   826                   /* just in case that wasn't fatal enough, end parse */
   827                   done_parsing();
   827                   done_parsing();
   828                 } else {
   828                 } else {
   829                   lhs_sym = (Symbol)stack.peek();
   829                   lhs_sym = stack.peek();
   830                 }
   830                 }
   831             }
   831             }
   832         }
   832         }
   833       return lhs_sym;
   833       return lhs_sym;
   834     }
   834     }
   914    *  state currently on the top of the (real) parse stack.
   914    *  state currently on the top of the (real) parse stack.
   915    */
   915    */
   916   protected boolean shift_under_error()
   916   protected boolean shift_under_error()
   917     {
   917     {
   918       /* is there a shift under error Symbol */
   918       /* is there a shift under error Symbol */
   919       return get_action(((Symbol)stack.peek()).parse_state, error_sym()) > 0;
   919       return get_action((stack.peek()).parse_state, error_sym()) > 0;
   920     }
   920     }
   921 
   921 
   922   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   922   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
   923 
   923 
   924   /** Put the (real) parse stack into error recovery configuration by
   924   /** Put the (real) parse stack into error recovery configuration by
   934       int act;
   934       int act;
   935 
   935 
   936       if (debug) debug_message("# Finding recovery state on stack");
   936       if (debug) debug_message("# Finding recovery state on stack");
   937 
   937 
   938       /* Remember the right-position of the top symbol on the stack */
   938       /* Remember the right-position of the top symbol on the stack */
   939       int right_pos = ((Symbol)stack.peek()).right;
   939       int right_pos = (stack.peek()).right;
   940       int left_pos  = ((Symbol)stack.peek()).left;
   940       int left_pos  = (stack.peek()).left;
   941 
   941 
   942       /* pop down until we can shift under error Symbol */
   942       /* pop down until we can shift under error Symbol */
   943       while (!shift_under_error())
   943       while (!shift_under_error())
   944         {
   944         {
   945           /* pop the stack */
   945           /* pop the stack */
   946           if (debug)
   946           if (debug)
   947             debug_message("# Pop stack by one, state was # " +
   947             debug_message("# Pop stack by one, state was # " +
   948                           ((Symbol)stack.peek()).parse_state);
   948                           (stack.peek()).parse_state);
   949           left_pos = ((Symbol)stack.pop()).left;
   949           left_pos = ((Symbol)stack.pop()).left;
   950           tos--;
   950           tos--;
   951 
   951 
   952           /* if we have hit bottom, we fail */
   952           /* if we have hit bottom, we fail */
   953           if (stack.empty())
   953           if (stack.empty())
   956               return false;
   956               return false;
   957             }
   957             }
   958         }
   958         }
   959 
   959 
   960       /* state on top of the stack can shift under error, find the shift */
   960       /* state on top of the stack can shift under error, find the shift */
   961       act = get_action(((Symbol)stack.peek()).parse_state, error_sym());
   961       act = get_action((stack.peek()).parse_state, error_sym());
   962       if (debug)
   962       if (debug)
   963         {
   963         {
   964           debug_message("# Recover state found (#" +
   964           debug_message("# Recover state found (#" +
   965                         ((Symbol)stack.peek()).parse_state + ")");
   965                         (stack.peek()).parse_state + ")");
   966           debug_message("# Shifting on error to state #" + (act-1));
   966           debug_message("# Shifting on error to state #" + (act-1));
   967         }
   967         }
   968 
   968 
   969       /* build and shift a special error Symbol */
   969       /* build and shift a special error Symbol */
   970       error_token = new Symbol(error_sym(), left_pos, right_pos);
   970       error_token = new Symbol(error_sym(), left_pos, right_pos);
  1143       if (debug)
  1143       if (debug)
  1144         {
  1144         {
  1145           debug_message("# Reparsing saved input with actions");
  1145           debug_message("# Reparsing saved input with actions");
  1146           debug_message("# Current Symbol is #" + cur_err_token().sym);
  1146           debug_message("# Current Symbol is #" + cur_err_token().sym);
  1147           debug_message("# Current state is #" +
  1147           debug_message("# Current state is #" +
  1148                         ((Symbol)stack.peek()).parse_state);
  1148                         (stack.peek()).parse_state);
  1149         }
  1149         }
  1150 
  1150 
  1151       /* continue until we accept or have read all lookahead input */
  1151       /* continue until we accept or have read all lookahead input */
  1152       while(!_done_parsing)
  1152       while(!_done_parsing)
  1153         {
  1153         {
  1154           /* current state is always on the top of the stack */
  1154           /* current state is always on the top of the stack */
  1155 
  1155 
  1156           /* look up action out of the current state with the current input */
  1156           /* look up action out of the current state with the current input */
  1157           act =
  1157           act =
  1158             get_action(((Symbol)stack.peek()).parse_state, cur_err_token().sym);
  1158             get_action((stack.peek()).parse_state, cur_err_token().sym);
  1159 
  1159 
  1160           /* decode the action -- > 0 encodes shift */
  1160           /* decode the action -- > 0 encodes shift */
  1161           if (act > 0)
  1161           if (act > 0)
  1162             {
  1162             {
  1163               /* shift to the encoded state by pushing it on the stack */
  1163               /* shift to the encoded state by pushing it on the stack */
  1203                   stack.pop();
  1203                   stack.pop();
  1204                   tos--;
  1204                   tos--;
  1205                 }
  1205                 }
  1206 
  1206 
  1207               /* look up the state to go to from the one popped back to */
  1207               /* look up the state to go to from the one popped back to */
  1208               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
  1208               act = get_reduce((stack.peek()).parse_state, lhs_sym_num);
  1209 
  1209 
  1210               /* shift to that state */
  1210               /* shift to that state */
  1211               lhs_sym.parse_state = act;
  1211               lhs_sym.parse_state = act;
  1212               lhs_sym.used_by_parser = true;
  1212               lhs_sym.used_by_parser = true;
  1213               stack.push(lhs_sym);
  1213               stack.push(lhs_sym);
  1232 
  1232 
  1233   /** Utility function: unpacks parse tables from strings */
  1233   /** Utility function: unpacks parse tables from strings */
  1234   protected static short[][] unpackFromStrings(String[] sa)
  1234   protected static short[][] unpackFromStrings(String[] sa)
  1235     {
  1235     {
  1236       // Concatanate initialization strings.
  1236       // Concatanate initialization strings.
  1237       StringBuffer sb = new StringBuffer(sa[0]);
  1237       StringBuilder sb = new StringBuilder(sa[0]);
  1238       for (int i=1; i<sa.length; i++)
  1238       for (int i=1; i<sa.length; i++)
  1239         sb.append(sa[i]);
  1239         sb.append(sa[i]);
  1240       int n=0; // location in initialization string
  1240       int n=0; // location in initialization string
  1241       int size1 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
  1241       int size1 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
  1242       short[][] result = new short[size1][];
  1242       short[][] result = new short[size1][];