Class CanonicalParseTable

All Implemented Interfaces:

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


protected CanonicalParseTable()
Constructor for subclasses only


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

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


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