org.metasyntactic.math.automata
Class CanonicalParseTable

java.lang.Object
  |
  +--org.metasyntactic.math.automata.LRParseTable
        |
        +--org.metasyntactic.math.automata.CanonicalParseTable
All Implemented Interfaces:
FiniteAutomata, java.io.Serializable

public class CanonicalParseTable
extends LRParseTable

A canonical parse table implements the strongest form of LR parsing. However, this comes at a very high price. To be able to construct a parser that can follow every language constructed from the LR set we must use a huge amount of space. For example, the canonical LR parse table for java uses ~ 10,000 states. However, the equivalent LALR parse table would only use ~ 500 states. The price of LALR parsing, however, is that only a subset of the LR languages can be parsed.

Humorous fact: The initial grammars for the Fortran, C, and Java languages could not be parsed by an LALR parse table and had to have canonical parse tables to parse it.

On a serious note. With the current state of computers where space is no longer such a large consideration, it is not unadvisable to replace LALR parsers with canonical parsers. This is certainly true if the time needed to produce the table (for example inside a program which s dynamically changing its grammar) is at a premium.

See Also:
Serialized Form

Nested Class Summary
protected static class CanonicalParseTable.CPTState
           
 
Nested classes inherited from class org.metasyntactic.math.automata.LRParseTable
LRParseTable.Accept, LRParseTable.Action, LRParseTable.Error, LRParseTable.Reduce, LRParseTable.Shift, LRParseTable.StateAndSymbol
 
Field Summary
 
Fields inherited from class org.metasyntactic.math.automata.LRParseTable
actions, characterClasses, gotos, nonterminals, productionToNum, startState, states, terminals
 
Constructor Summary
protected CanonicalParseTable()
          Constructor for subclasses only
  CanonicalParseTable(ContextFreeGrammar G)
          Creates a new CLR Parse table from this CFG! Don't pass in an augmented grammar!
 
Method Summary
static void main(java.lang.String[] args)
           
 
Methods inherited from class org.metasyntactic.math.automata.LRParseTable
accept, accept, addAccept, addAcceptListener, addError, addErrorListener, addGoto, addProduction, addReduce, addReduceListener, addShift, addShiftListener, addState, getLargeTable, newToString, removeAcceptListener, removeErrorListener, removeReduceListener, removeShiftListener, setStartState, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

CanonicalParseTable

protected CanonicalParseTable()
Constructor for subclasses only


CanonicalParseTable

public CanonicalParseTable(ContextFreeGrammar G)
                    throws ParseTableConflict
Creates a new CLR Parse table from this CFG! Don't pass in an augmented grammar!

Throws:
java.lang.IllegalArgumentException - If the ContextFreeGrammar passed in is already augmented.
ParseTableConflict
Method Detail

main

public static void main(java.lang.String[] args)