Package org.metasyntactic.math.automata

Interface Summary
FiniteAutomata FORMAL DEFINITION OF A FINITE AUTOMATA
RegularExpression FORMAL DEFINITION OF A REGULAR EXPRESSION
 

Class Summary
AbstractFiniteAutomata Abstract class implementing base functionality for a finite state machine, such as a NondeterministicFiniteAutomata or a DeterministicFiniteAutomata.
AbstractRegularExpression Class implementing base funcitonality for a RegularExpression.
AbstractRegularExpression.NFAState Convenience class used in the implementations of toNondeterministicFiniteAutomata()
AugmentedGrammar If G is a grammar with start symbol S, then G', the augmented grammar for G, is G with a new Start symbol S' and production S' → S.
Blank  
CanonicalParseTable A canonical parse table implements the strongest form of LR parsing.
CanonicalParseTable.CPTState  
ChomskyNormalForm  
Concatenation Class representing the Regular Expression R1∩R2.
ContextFreeGrammar Context-free grammars are a more powerful method of describing languages.
ContextFreeGrammar.CFGSymbol  
DeterministicFiniteAutomata FORMAL DEFINITION OF A DETERMINISTIC FINITE AUTOMATON
Empty Class representing the Regular Expression ε.
EmptyStack Class represting the special PushdownAutomata stack character $
Epsilon Class representing the special FiniteAutomata character ε
GeneralizedNondeterministicFiniteAutomata Generalized nondeterministic finite automata (GNFA) are simply nondeterministic finite automata wherein the transition arrows may have any regular expressions as labels, instead of only members of the alphabet or ε.
Hash  
Language  
LexicalSpecification  
LookAheadParseTable The LALR method is often used in practise because the tables obtained by it are considerably smaller than the CanonicalParseTable, yet most common syntactic constructs of programming languages can be expressed conveniently by an LALR grammar.
LR0Item An LR(0) item (item for short) of a grammar G is a production of G with a dot at some position of the right side.
LR1Item An LR(1) item (item for short) of a grammar G is a production of G with a dot at some position of the right side.
LRParseTable This class presents an efficient, bottom up technique that can be used to parse a large class of context-free grammars.
LRParseTable.Accept If action[am, ai] = accept, parsing is complete
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.
LRParseTable.Error  
LRParseTable.Shift If action[am, ai] = shift s, the parser executes a shift move.
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
LRParseTableFactory  
NondeterministicFiniteAutomata FORMAL DEFINITION OF A NONDETERMINISTIC FINITE AUTOMATAON
NondeterministicFiniteAutomata.DFAState Used to compress DFA states in toDeterministicFiniteAutomata
Null Class representing the Regular Expression ∅.
Production A grammar naturally describes the hierarchical structure of many programming language contructs.
PushdownAutomata FORMAL DEFINATION OF A PUSHDOWN AUTOMATON
RegularExpressionFactory A factory class for returning any of the 3 regular expression atoms.
SimpleParseTable  
Star Class representing the Regular Expression R*.
Symbol Class representing the Regular Expression ∅.
TransitionFunction We use something clled a transition function, frequently denoted δ, to define the rules for moving.
TuringMachine FORMAL DEFINITION OF A TURING MACHINE
Union Class representing the Regular Expression R1∪R2.
 

Exception Summary
ParseTableConflict  
ReduceReduceConflict There are context-free grammars for which shift-reducing parsing cannot be used.
ShiftReduceConflict There are context-free grammars for which shift-reducing parsing cannot be used.