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.

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.