parser.java

JDK1.4编译器后端

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * This file is part of Beaver Parser Generator.                       *
 * Copyright (C) 2003,2004 Alexander Demenchuk <[e-mail]>.  *
 * All rights reserved.                                                *
 * See the file "LICENSE" for the terms and conditions for copying,    *
 * distribution and modification of Beaver.                            *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

package beaver;

import java.io.IOException;

/**
 * Almost complete implementation of a LALR parser. Two components that it lacks to parse a concrete
 * grammar -- rule actions and parsing tables -- are provided by a generated subclass.
 */
public abstract class Parser
{
	static public class Exception extends java.lang.Exception
	{
		Exception(String msg)
		{
			super(msg);
		}
	}
	
	/**
	 * This class "lists" reportable events that might happen during parsing.
	 */
	static public class Events
	{
		public void scannerError(Scanner.Exception e)
		{
			System.err.print("Scanner Error:");
			if (e.line > 0)
			{
				System.err.print(e.line);
				System.err.print(',');
				System.err.print(e.column);
				System.err.print(':');
			}
			System.err.print(' ');
			System.err.println(e.getMessage());
		}
		public void syntaxError(Symbol token)
		{
			System.err.print(':');
			System.err.print(Symbol.getLine(token.start));
			System.err.print(',');
			System.err.print(Symbol.getColumn(token.start));
			System.err.print('-');
			System.err.print(Symbol.getLine(token.end));
			System.err.print(',');
			System.err.print(Symbol.getColumn(token.end));
			System.err.print(": Syntax Error: unexpected token ");
			if (token.value != null)
			{
				System.err.print('"');
				System.err.print(token.value);
				System.err.println('"');
			}
			else
			{
				System.err.print('#');
				System.err.println(token.id);
			}
		}
		public void unexpectedTokenRemoved(Symbol token)
		{
			System.err.print(':');
			System.err.print(Symbol.getLine(token.start));
			System.err.print(',');
			System.err.print(Symbol.getColumn(token.start));
			System.err.print('-');
			System.err.print(Symbol.getLine(token.end));
			System.err.print(',');
			System.err.print(Symbol.getColumn(token.end));
			System.err.print(": Recovered: removed unexpected token ");
			if (token.value != null)
			{
				System.err.print('"');
				System.err.print(token.value);
				System.err.println('"');
			}
			else
			{
				System.err.print('#');
				System.err.println(token.id);
			}
		}
		public void missingTokenInserted(Symbol token)
		{
			System.err.print(':');
			System.err.print(Symbol.getLine(token.start));
			System.err.print(',');
			System.err.print(Symbol.getColumn(token.start));
			System.err.print('-');
			System.err.print(Symbol.getLine(token.end));
			System.err.print(',');
			System.err.print(Symbol.getColumn(token.end));
			System.err.print(": Recovered: inserted missing token ");
			if (token.value != null)
			{
				System.err.print('"');
				System.err.print(token.value);
				System.err.println('"');
			}
			else
			{
				System.err.print('#');
				System.err.println(token.id);
			}
		}
		public void misspelledTokenReplaced(Symbol token)
		{
			System.err.print(':');
			System.err.print(Symbol.getLine(token.start));
			System.err.print(',');
			System.err.print(Symbol.getColumn(token.start));
			System.err.print('-');
			System.err.print(Symbol.getLine(token.end));
			System.err.print(',');
			System.err.print(Symbol.getColumn(token.end));
			System.err.print(": Recovered: replaced unexpected token with ");
			if (token.value != null)
			{
				System.err.print('"');
				System.err.print(token.value);
				System.err.println('"');
			}
			else
			{
				System.err.print('#');
				System.err.println(token.id);
			}
		}
		public void errorPhraseRemoved(Symbol error)
		{
			System.err.print(':');
			System.err.print(Symbol.getLine(error.start));
			System.err.print(',');
			System.err.print(Symbol.getColumn(error.start));
			System.err.print('-');
			System.err.print(Symbol.getLine(error.end));
			System.err.print(',');
			System.err.print(Symbol.getColumn(error.end));
			System.err.println(": Recovered: removed error phrase");
		}
	}
	
	/**
	 * This class wrapps a Scanner and provides a token "accumulator" for a parsing simulation.
	 * <p>If a source we parse does not have syntax errors the only way this warpper affects a 
	 * parser is via an extra indirection when it delivers next token. When though parser needs
	 * to recover from a syntax error this wrapper accumulates tokens shifted by a forward parsing
	 * simulation and later feeds them to a recovered parser</p>
	 */
	private class TokenStream
	{
		private Scanner  scanner;
		private Symbol[] buffer;
		private int      n_marked;
		private int      n_read;
		private int      n_written;
		
		TokenStream(Scanner scanner)
		{
			this.scanner = scanner;
		}

        TokenStream(Scanner scanner, Symbol first_symbol)
        {
            this(scanner);
            mark(1);
            buffer[0] = first_symbol;
            n_written++;
        }
        
		Symbol nextToken() throws IOException
		{
			if (buffer != null)
			{				
				if (n_read < n_written)
					return buffer[n_read++];
				
				if (n_written < n_marked)
				{
					n_read++;
					return buffer[n_written++] = readToken();
				}
				buffer = null;
			}
			return readToken();
		}

		/**
		 * Prepare a stream to accumulate tokens.
		 * 
		 * @param size number of shifted tokens to accumulate
		 */
		void mark(int size)
		{
			buffer = new Symbol[(n_marked = size) + 1];
			n_read = n_written = 0;
		}
		
		/**
		 * Prepare accumulated tokens to be reread by a next simulation run
		 * or by a recovered parser.
		 */
		void reset()
		{
			n_read = 0;
		}

		/**
		 * Checks whether a simulation filled the token accumulator. 
		 * 
		 * @return true if accumulator is full
		 */
		boolean isFull()
		{
			return n_read == n_marked;
		}
        
		/**
		 * Insert two tokens at the beginning of a stream 
		 * 
		 * @param token to be inserted
		 */
		void insert(Symbol t0, Symbol t1)
		{
			System.arraycopy(buffer, 0, buffer, 2, n_written);
			buffer[0] = t0;
			buffer[1] = t1;
			n_written += 2;
		}
		
		/**
		 * Removes a token from the accumulator.
		 * 
		 * @param i index of a token in the accumulator.
		 * @return removed token
		 */
		Symbol remove(int i)
		{
			Symbol token = buffer[i];
			int last = n_written - 1;
			while (i < last)
			{
				buffer[i] = buffer[++i];
			}
			n_written = last;
			return token;
		}
		
		/**
		 * Reads next recognized token from the scanner. If scanner fails to recognize a token and
		 * throws an exception it will be reported via Parser.scannerError().
		 * <p>It is expected that scanner is capable of returning at least an EOF token after the
		 * exception.</p>
		 * 
		 * @param src scanner
		 * @return next recognized token
		 * @throws IOException
		 *             as thrown by a scanner
		 */
		private Symbol readToken() throws IOException
		{
			while (true)
			{
				try
				{
					return scanner.nextToken();
				}
				catch (Scanner.Exception e)
				{
					report.scannerError(e);
				}
			}
		}
	}

	/**
	 * Simulator is a stripped (of action code) version of a parser that will try to parse ahead
	 * token stream after a syntax error. The simulation is considered successful if 3 tokens were
	 * shifted successfully. If during simulation this parser enconters an error it drops the first
	 * token it tried to use and restarts the simulated parsing.
	 * <p>
	 * Note: Without a special "error" rule present in a grammar, which a parser will try to shift
	 * at the beginning of an error recovery, simulation continues without removing anything from
	 * the original states stack. This often will lead to cases when no parsing ahead will recover
	 * the parser from a syntax error.
	 * </p>
	 */
	private class Simulator
	{
		private short[] states;
		private int top, min_top;

		boolean parse(TokenStream in) throws IOException
		{
			initStack();
			do {
				Symbol token = in.nextToken();
				while (true)
				{
					short act = tables.findParserAction(states[top], token.id);
					if (act > 0)
					{
						shift(act);
						break;
					}
					else if (act == accept_action_id)
					{
						return true;
					}
					else if (act < 0)
					{
						short nt_id = reduce(~act);

						act = tables.findNextState(states[top], nt_id);
						if (act > 0)
							shift(act);
						else
							return act == accept_action_id;
					}
					else // act == 0, i.e. this is an error
					{
						return false;
					}
				}
			}
			while (!in.isFull());
			return true;
		}