geneseo.cs.compiler
Class LRParser

java.lang.Object
  |
  +--geneseo.cs.compiler.LRParser

All Implemented Interfaces:

Parser

Direct Known Subclasses:

MinimLLRParser

public abstract class LRParser

extends java.lang.Object

implements Parser

Represents general LR parsers. This class provides those features that all LR parsers have in common; subclasses for parsers for individual languages should provide language-specific features. This class is therefore an abstract base class that can be extended to provide complete parsers. In particular, this class provides a "parse" method, while subclasses have to provide the action and goto tables that drive it. Both tables are arrays of integers -- in the case of the goto table, these integers are simply parser state numbers. In the case of the action table, they also encode the kind of action, as follows:

• < 0: Error entries. The corresponding positive value will be passed to the subclass's error method to be used however the subclass sees fit.
• 0 - 9999: Shift entries. The integer gives the number of the state to enter after shifting.
• 10000 - 99999: Reduce entries. The integer less 10000 is the production number to reduce by.
• >= 100000: Accept entries.

To help subclass authors remember these codes, this class provides utility methods s(), r(), e(), and a(), which create shift, reduce, error, and accept entries, respectively.

Constructor Summary

protected

LRParser(int[][] actions, int[][] go) Initialize an LR parser from its action and goto tables.

Method Summary

protected static int	a() Construct a parse table entry for the "accept" action.
protected static int	e(int code) Construct a parse table entry for an "error" action.
protected abstract void	error(int code, TokenSeq input, java.util.Stack parseStack) Handle an error in an LR parser.
protected abstract int	leftSide(int production) Figures out the non-terminal on the left side of a production, given the production number.
ParseNode	parse(TokenSeq tokens) Parse a sequence of tokens.
java.lang.Object	popSymbol() Remove and return the top-most symbol from the parser's stack.
protected static int	r(int prod) Construct a parse table entry for a "reduce" action.
protected abstract ParseNode	reduce(int production) Reduce by a specified production during a parse.
protected static int	s(int state) Construct a parse table entry for a "shift" action.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LRParser

protected LRParser(int[][] actions,
                   int[][] go)

Initialize an LR parser from its action and goto tables.

Parameters:

actions - The action table.

go - The goto table.

Method Detail

s

protected static int s(int state)

Construct a parse table entry for a "shift" action.

Parameters:

state - The state to enter after shifting.

Returns:

An integer that encodes the shift in a parse table.

r

protected static int r(int prod)

Construct a parse table entry for a "reduce" action.

Parameters:

prod - The production number to reduce by.

Returns:

An integer that encodes this reduction in a parse table.

e

protected static int e(int code)

Construct a parse table entry for an "error" action.

Parameters:

code - A code for the specific error.

Returns:

An integer that encodes this error in a parse table.

a

protected static int a()

Construct a parse table entry for the "accept" action.

Returns:

An integer that encodes acceptance in a parse table.

parse

public ParseNode parse(TokenSeq tokens)
                throws CompilerException

Parse a sequence of tokens.

Specified by:

parse in interface Parser

Parameters:

tokens - The token sequence to parse.

Returns:

The root of a syntax tree for this sequence of tokens.

Throws:

CompilerException - If the token sequence doesn't represent a legal input to this parser.

popSymbol

public java.lang.Object popSymbol()
                           throws CompilerException

Remove and return the top-most symbol from the parser's stack.

Returns:

The top-most symbol. This may be any of several kinds of symbol, e.g., a token, a syntax tree node, etc., depending on where the parser is in a parse.

Throws:

CompilerException - If there is no symbol on the stack.

reduce

protected abstract ParseNode reduce(int production)
                             throws CompilerException

Reduce by a specified production during a parse. The "parse" method invokes this to reduce in a language-specific manner.

Parameters:

production - The number of the production by which to reduce.

Returns:

The root of the piece of syntax tree resulting from the reduction.

Throws:

CompilerException - If the parse stack doesn't have enough items on it to complete the reduction, or if the production number is invalid.

error

protected abstract void error(int code,
                              TokenSeq input,
                              java.util.Stack parseStack)
                       throws CompilerException

Handle an error in an LR parser. This can handle the error in any of a number of ways -- repair the stack, throw an exception, etc.

Parameters:

code - The error code from the parse table.

input - The sequence of tokens being processed when the error was detected.

parseStack - The parser's stack at the time of the error.

Throws:

CompilerException - If the error cannot be repaired.

leftSide

protected abstract int leftSide(int production)

Figures out the non-terminal on the left side of a production, given the production number.

Parameters:

production - The production number.

Returns:

The integer code for the left-hand side of the specified production.