org.metasyntactic.math.automata
Class LRParseTable

java.lang.Object
  |
  +--org.metasyntactic.math.automata.LRParseTable

All Implemented Interfaces:

FiniteAutomata, java.io.Serializable

Direct Known Subclasses:

CanonicalParseTable, LookAheadParseTable, SimpleParseTable

public abstract class LRParseTable

extends java.lang.Object

implements FiniteAutomata

This class presents an efficient, bottom up technique that can be used to parse a large class of context-free grammars. The technique is called LR(k) parsing; the "L" is for left-to-right scanning of the input, the "R" for constructing a rightmost derivation in reverse, and the k for number of input symbols of lookaead that are used in making parsing decisions. When (k) is ommitted, k is assumed to be 1. LR parsing is attractive for a variety of reasons.

• LR parsers can be constructed to recognize virtually all programming language constructs for which context free grammars can be written
• The LR parsing method is the most general nonbacktracking shift-reduce parsing method known, yet it can be implemented as efficiently as other shift-reduce methods
• The class of grammars that can be parsed using LR methods is a proper superset of the class of grammars that can be parsed with predictive parsers.
• An LR parser can detect syntactic errors as soon as it is possible to do so on a left-to-right scan of the input

Currently, error-handling is not fully implemented. If a parse of input tokens results in the parse table being in an invalid state, a general ParseException is thrown. In the future this will be replaced with a robust error handling mechanism.

See Also:

Serialized Form

Nested Class Summary

static class	LRParseTable.Accept If action[am, ai] = accept, parsing is complete
static class	LRParseTable.Action Action is the parsing table entry for state sm and input ai, which can have one of four values: shift s, where s is a state, reduce by a grammar production A → B, accept, and error.
static class	LRParseTable.Error
class	LRParseTable.Reduce If action[am, ai] = reduce A → Β, then the parser executes a reduce move.
static class	LRParseTable.Shift If action[am, ai] = shift s, the parser executes a shift move.
protected static class	LRParseTable.StateAndSymbol This class merely serves as a struct to allow a state and a symbol to be used as an index in a mapping

Field Summary

protected java.util.Map	actions
protected java.util.Map	characterClasses
protected java.util.Map	gotos
protected java.util.Set	nonterminals
protected java.util.Map	productionToNum
protected java.lang.Object	startState Subclass Parse tables must set this variable
protected java.util.Set	states
protected java.util.Set	terminals

Constructor Summary

protected	LRParseTable() So that subclasses can call it
protected	LRParseTable(java.util.Map characterClasses)

Method Summary

boolean	accept(java.util.Iterator w)
boolean	accept(java.util.Iterator w, java.util.Map symbolToClasses)
void	addAccept(java.lang.Object state, java.lang.Object terminal)
void	addAcceptListener(AcceptListener listener) Registers AcceptListener to receive events.
void	addError(java.lang.Object state, java.lang.Object nonterminal, ParseException parseException)
void	addErrorListener(ErrorListener listener) Registers ErrorListener to receive events.
void	addGoto(java.lang.Object state, java.lang.Object nonterminal, java.lang.Object endState)
protected void	addProduction(Production prod)
void	addReduce(java.lang.Object state, java.lang.Object terminal, Production production)
void	addReduceListener(ReduceListener listener) Registers ReduceListener to receive events.
void	addShift(java.lang.Object state, java.lang.Object terminal, java.lang.Object endState)
void	addShiftListener(ShiftListener listener) Registers ShiftListener to receive events.
protected void	addState(java.lang.Object state)
java.lang.Object[][]	getLargeTable()
java.lang.String	newToString()
void	removeAcceptListener(AcceptListener listener) Removes AcceptListener from the list of listeners.
void	removeErrorListener(ErrorListener listener) Removes errorListener from the list of listeners.
void	removeReduceListener(ReduceListener listener) Removes ReduceListener from the list of listeners.
void	removeShiftListener(ShiftListener listener) Removes ShiftListener from the list of listeners.
protected void	setStartState(java.lang.Object startState)
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

actions

protected java.util.Map actions

gotos

protected java.util.Map gotos

states

protected java.util.Set states

terminals

protected java.util.Set terminals

nonterminals

protected java.util.Set nonterminals

characterClasses

protected java.util.Map characterClasses

startState

protected java.lang.Object startState

Subclass Parse tables must set this variable

productionToNum

protected java.util.Map productionToNum

Constructor Detail

LRParseTable

protected LRParseTable()

So that subclasses can call it

LRParseTable

protected LRParseTable(java.util.Map characterClasses)

Method Detail

setStartState

protected void setStartState(java.lang.Object startState)

addState

protected void addState(java.lang.Object state)

addProduction

protected void addProduction(Production prod)

addShift

public void addShift(java.lang.Object state,
                     java.lang.Object terminal,
                     java.lang.Object endState)
              throws ShiftReduceConflict

ShiftReduceConflict

addReduce

public void addReduce(java.lang.Object state,
                      java.lang.Object terminal,
                      Production production)
               throws ShiftReduceConflict,
                      ReduceReduceConflict

ShiftReduceConflict

ReduceReduceConflict

addAccept

public void addAccept(java.lang.Object state,
                      java.lang.Object terminal)

addGoto

public void addGoto(java.lang.Object state,
                    java.lang.Object nonterminal,
                    java.lang.Object endState)

addError

public void addError(java.lang.Object state,
                     java.lang.Object nonterminal,
                     ParseException parseException)

accept

public boolean accept(java.util.Iterator w)
               throws ParseException

Specified by:

accept in interface FiniteAutomata

Parameters:

w - A string over some alphabet Σ

Returns:

true if this machine accepts w

Throws:

ParseException - if along the way of testing for acceptance, an exception occurred over the format of w

accept

public boolean accept(java.util.Iterator w,
                      java.util.Map symbolToClasses)
               throws ParseException

ParseException

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

newToString

public java.lang.String newToString()

getLargeTable

public java.lang.Object[][] getLargeTable()

addShiftListener

public void addShiftListener(ShiftListener listener)

Registers ShiftListener to receive events.

Parameters:

listener - The listener to register.

removeShiftListener

public void removeShiftListener(ShiftListener listener)

Removes ShiftListener from the list of listeners.

Parameters:

listener - The listener to remove.

addReduceListener

public void addReduceListener(ReduceListener listener)

Registers ReduceListener to receive events.

Parameters:

listener - The listener to register.

removeReduceListener

public void removeReduceListener(ReduceListener listener)

Removes ReduceListener from the list of listeners.

Parameters:

listener - The listener to remove.

addAcceptListener

public void addAcceptListener(AcceptListener listener)

Registers AcceptListener to receive events.

Parameters:

listener - The listener to register.

removeAcceptListener

public void removeAcceptListener(AcceptListener listener)

Removes AcceptListener from the list of listeners.

Parameters:

listener - The listener to remove.

addErrorListener

public void addErrorListener(ErrorListener listener)

Registers ErrorListener to receive events.

Parameters:

listener - The listener to register.

removeErrorListener

public void removeErrorListener(ErrorListener listener)

Removes errorListener from the list of listeners.

Parameters:

listener - The listener to remove.