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)