lr_parser.java

《java virtual machine》是研究jvm的一本书

   *  we begin to discard tokens in attempt to get past the point of error
   *  to a point where we can continue parsing.  After each token, we attempt 
   *  to "parse ahead" though the buffered lookahead tokens.  The "parse ahead"
   *  process simulates that actual parse, but does not modify the real 
   *  parser's configuration, nor execute any actions. If we can  parse all 
   *  the stored tokens without error, then the recovery is considered a 
   *  success.  Once a successful recovery point is determined, we do an
   *  actual parse over the stored input -- modifying the real parse 
   *  configuration and executing all actions.  Finally, we return the the 
   *  normal parser to continue with the overall parse.
   *
   * @param debug should we produce debugging messages as we parse.
   */
  protected boolean error_recovery(boolean debug)
    throws java.lang.Exception
    {
      if (debug) debug_message("# Attempting error recovery");

      /* first pop the stack back into a state that can shift on error and 
	 do that shift (if that fails, we fail) */
      if (!find_recovery_config(debug))
	{
	  if (debug) debug_message("# Error recovery fails");
	  return false;
	}

      /* read ahead to create lookahead we can parse multiple times */
      read_lookahead();

      /* repeatedly try to parse forward until we make it the required dist */
      for (;;)
	{
	  /* try to parse forward, if it makes it, bail out of loop */
	  if (debug) debug_message("# Trying to parse ahead");
	  if (try_parse_ahead(debug))
	    {
	      break;
	    }

	  /* if we are now at EOF, we have failed */
	  if (lookahead[0].sym == EOF_sym()) 
	    {
	      if (debug) debug_message("# Error recovery fails at EOF");
	      return false;
	    }

	  /* otherwise, we consume another token and try again */
	  if (debug) 
	  debug_message("# Consuming token #" + cur_err_token().sym);
	  restart_lookahead();
	}

      /* we have consumed to a point where we can parse forward */
      if (debug) debug_message("# Parse-ahead ok, going back to normal parse");

      /* do the real parse (including actions) across the lookahead */
      parse_lookahead(debug);

      /* we have success */
      return true;
    }

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Determine if we can shift under the special error symbol out of the 
   *  state currently on the top of the (real) parse stack. 
   */
  protected boolean shift_under_error()
    {
      /* is there a shift under error symbol */
      return get_action(((symbol)stack.peek()).parse_state, error_sym()) > 0;
    }

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Put the (real) parse stack into error recovery configuration by 
   *  popping the stack down to a state that can shift on the special 
   *  error symbol, then doing the shift.  If no suitable state exists on 
   *  the stack we return false 
   *
   * @param debug should we produce debugging messages as we parse.
   */
  protected boolean find_recovery_config(boolean debug)
    {
      token error_token;
      int act;

      if (debug) debug_message("# Finding recovery state on stack");

      /* pop down until we can shift under error token */
      while (!shift_under_error())
	{
	  /* pop the stack */
	  if (debug) 
	    debug_message("# Pop stack by one, state was # " +
	                  ((symbol)stack.peek()).parse_state);
          stack.pop();	
	  tos--;

	  /* if we have hit bottom, we fail */
	  if (stack.empty()) 
	    {
	      if (debug) debug_message("# No recovery state found on stack");
	      return false;
	    }
	}

      /* state on top of the stack can shift under error, find the shift */
      act = get_action(((symbol)stack.peek()).parse_state, error_sym());
      if (debug) 
	{
	  debug_message("# Recover state found (#" + 
			((symbol)stack.peek()).parse_state + ")");
	  debug_message("# Shifting on error to state #" + (act-1));
	}

      /* build and shift a special error token */
      error_token = new token(error_sym());
      error_token.parse_state = act-1;
      stack.push(error_token);
      tos++;

      return true;
    }

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Lookahead tokens used for attempting error recovery "parse aheads". */
  protected token lookahead[];

  /** Position in lookahead input buffer used for "parse ahead". */
  protected int lookahead_pos;

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Read from input to establish our buffer of "parse ahead" lookahead 
   *  symbols. 
   */
  protected void read_lookahead() throws java.lang.Exception
    {
      /* create the lookahead array */
      lookahead = new token[error_sync_size()];

      /* fill in the array */
      for (int i = 0; i < error_sync_size(); i++)
	{
	  lookahead[i] = cur_token;
	  cur_token = scan();
	}

      /* start at the beginning */
      lookahead_pos = 0;
    }

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Return the current lookahead in our error "parse ahead" buffer. */
  protected token cur_err_token() { return lookahead[lookahead_pos]; }

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Advance to next "parse ahead" input symbol. Return true if we have 
   *  input to advance to, false otherwise. 
   */
  protected boolean advance_lookahead()
    {
      /* advance the input location */
      lookahead_pos++;

      /* return true if we didn't go off the end */
      return lookahead_pos < error_sync_size();
    }

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Reset the parse ahead input to one token past where we started error 
   *  recovery (this consumes one new token from the real input). 
   */
  protected void restart_lookahead() throws java.lang.Exception
    {
      /* move all the existing input over */
      for (int i = 1; i < error_sync_size(); i++)
	lookahead[i-1] = lookahead[i];

      /* read a new token into the last spot */
      cur_token = scan();
      lookahead[error_sync_size()-1] = cur_token;

      /* reset our internal position marker */
      lookahead_pos = 0;
    }

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Do a simulated parse forward (a "parse ahead") from the current 
   *  stack configuration using stored lookahead input and a virtual parse
   *  stack.  Return true if we make it all the way through the stored 
   *  lookahead input without error. This basically simulates the action of 
   *  parse() using only our saved "parse ahead" input, and not executing any 
   *  actions.
   *
   * @param debug should we produce debugging messages as we parse.
   */
  protected boolean try_parse_ahead(boolean debug)
    throws java.lang.Exception
    {
      int act;
      short lhs, rhs_size;

      /* create a virtual stack from the real parse stack */
      virtual_parse_stack vstack = new virtual_parse_stack(stack);

      /* parse until we fail or get past the lookahead input */
      for (;;)
	{
	  /* look up the action from the current state (on top of stack) */
	  act = get_action(vstack.top(), cur_err_token().sym);

	  /* if its an error, we fail */
	  if (act == 0) return false;

	  /* > 0 encodes a shift */
	  if (act > 0)
	    {
	      /* push the new state on the stack */
	      vstack.push(act-1);

	      if (debug) debug_message("# Parse-ahead shifts token #" + 
		       cur_err_token().sym + " into state #" + (act-1));

	      /* advance simulated input, if we run off the end, we are done */
	      if (!advance_lookahead()) return true;
	    }
	  /* < 0 encodes a reduce */
	  else
	    {
	      /* if this is a reduce with the start production we are done */
	      if ((-act)-1 == start_production()) 
		{
		  if (debug) debug_message("# Parse-ahead accepts");
		  return true;
		}

	      /* get the lhs symbol and the rhs size */
	      lhs = production_tab[(-act)-1][0];
	      rhs_size = production_tab[(-act)-1][1];

	      /* pop handle off the stack */
	      for (int i = 0; i < rhs_size; i++)
		vstack.pop();

	      if (debug) 
		debug_message("# Parse-ahead reduces: handle size = " + 
	          rhs_size + " lhs = #" + lhs + " from state #" + vstack.top());

	      /* look up goto and push it onto the stack */
	      vstack.push(get_reduce(vstack.top(), lhs));
	      if (debug) 
		debug_message("# Goto state #" + vstack.top());
	    }
	}
    }

  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

  /** Parse forward using stored lookahead symbols.  In this case we have
   *  already verified that parsing will make it through the stored lookahead
   *  symbols and we are now getting back to the point at which we can hand
   *  control back to the normal parser.  Consequently, this version of the
   *  parser performs all actions and modifies the real parse configuration.  
   *  This returns once we have consumed all the stored input or we accept.
   *
   * @param debug should we produce debugging messages as we parse.
   */
  protected void parse_lookahead(boolean debug)
    throws java.lang.Exception
    {
      /* the current action code */
      int act;

      /* the symbol/stack element returned by a reduce */
      symbol lhs_sym;

      /* information about production being reduced with */
      short handle_size, lhs_sym_num;

      /* restart the saved input at the beginning */
      lookahead_pos = 0;

      if (debug) 
	{
	  debug_message("# Reparsing saved input with actions");
	  debug_message("# Current token is #" + cur_err_token().sym);
	  debug_message("# Current state is #" + 
			((symbol)stack.peek()).parse_state);
	}

      /* continue until we accept or have read all lookahead input */
      while(!_done_parsing)
	{
	  /* current state is always on the top of the stack */

	  /* look up action out of the current state with the current input */
	  act = 
	    get_action(((symbol)stack.peek()).parse_state, cur_err_token().sym);

	  /* decode the action -- > 0 encodes shift */
	  if (act > 0)
	    {
	      /* shift to the encoded state by pushing it on the stack */
	      cur_err_token().parse_state = act-1;
	      if (debug) debug_shift(cur_err_token());
	      stack.push(cur_err_token());
	      tos++;

	      /* advance to the next token, if there is none, we are done */
	      if (!advance_lookahead()) 
		{
		  if (debug) debug_message("# Completed reparse");

		  /* scan next token so we can continue parse */
		  cur_token = scan();

		  /* go back to normal parser */
		  return;
		}
	      
	      if (debug) 
		debug_message("# Current token is #" + cur_err_token().sym);
	    }
	  /* if its less than zero, then it encodes a reduce action */
	  else if (act < 0)
	    {
	      /* perform the action for the reduce */
	      lhs_sym = do_action((-act)-1, this, stack, tos);

	      /* look up information about the production */
	      lhs_sym_num = production_tab[(-act)-1][0];
	      handle_size = production_tab[(-act)-1][1];

	      if (debug) debug_reduce((-act)-1, lhs_sym_num, handle_size);

	      /* pop the handle off the stack */
	      for (int i = 0; i < handle_size; i++)
		{
		  stack.pop();
		  tos--;
		}
	      
	      /* look up the state to go to from the one popped back to */
	      act = get_reduce(((symbol)stack.peek()).parse_state, lhs_sym_num);

	      /* shift to that state */
	      lhs_sym.parse_state = act;
	      stack.push(lhs_sym);
	      tos++;
	       
	      if (debug) debug_message("# Goto state #" + act);

	    }
	  /* finally if the entry is zero, we have an error 
	     (shouldn't happen here, but...)*/
	  else if (act == 0)
	    {
	      report_fatal_error("Syntax error", null);
	      return;
	    }
	}
    }

  /*-----------------------------------------------------------*/

};