org.stekikun.dolmen.codegen

Class DecisionTree

java.lang.Object

org.stekikun.dolmen.codegen.DecisionTree

Direct Known Subclasses:

DecisionTree.Impossible, DecisionTree.Return, DecisionTree.Split, DecisionTree.Switch, DecisionTree.Table

public abstract class DecisionTree
extends Object

An instance of DecisionTree describes the transition table for a lexer Automata cell, i.e. the shifting action to take with respect to the next character read from the input stream.

The point of DecisionTree is that it provides several implementations of how these transition tables can be encoded, giving different trade-offs depending on the shape of the transition table. The method compile(TreeMap) is used to build a "good" decision tree from a raw transition table.

Author:

Stéphane Lescuyer

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DecisionTree.Impossible A specific implementation of DecisionTree to represents empty transition tables
static class	DecisionTree.Kind The different kinds of available implementations of DecisionTree
static class	DecisionTree.Return An implementation of DecisionTree which maps some specific shifting action to all possible characters.
static class	DecisionTree.Split An implementation of DecisionTree which represents a binary choice with respect to some DecisionTree.Split.pivot character: every character below or equal to the DecisionTree.Split.pivot is mapped to the result of a recursive decision tree DecisionTree.Split.left every character higher than the DecisionTree.Split.pivot is mapped to the result of a recursive decision tree DecisionTree.Split.right This implementation is used as an internal node to implement binary decision trees.
static class	DecisionTree.Switch An implementation of DecisionTree which represents the transition table as a switch mapping some character sets to DFA.TransActions.
static class	DecisionTree.Table An implementation of DecisionTree which represents the transitions from a contiguous set of characters, starting at character DecisionTree.Table.base, as an array of actions.

Field Summary

Fields

Modifier and Type	Field and Description
static DecisionTree.Impossible	IMPOSSIBLE The decision tree for the empty transition table

Constructor Summary

Constructors

Constructor and Description
DecisionTree()

Method Summary

Modifier and Type	Method and Description
static DecisionTree	compile(TreeMap<CSet,DFA.TransActions> partition)
abstract CSet	getDomain()
abstract DecisionTree.Kind	getKind()
static void	main(String[] args) Functional tests of decision trees and compile(TreeMap)
static DecisionTree.Return	ret(DFA.TransActions transActions)
static DecisionTree	simplify(DecisionTree tree) This method tries to simplify the given tree in order to obtain an equivalent decision tree by removing useless parts.
static DecisionTree	split(char pivot, DecisionTree left, DecisionTree right)
static DecisionTree	switchTable(TreeMap<CSet,DFA.TransActions> table)
static DecisionTree	tabulated(char base, @NonNull DFA.TransActions[] table)
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

IMPOSSIBLE

public static final DecisionTree.Impossible IMPOSSIBLE

The decision tree for the empty transition table

Constructor Detail

DecisionTree

public DecisionTree()

Method Detail

getDomain

public abstract CSet getDomain()

Returns:

the domain set for which this transition table is defined, i.e. the characters which are mapped to some shifting action

getKind

public abstract DecisionTree.Kind getKind()

Returns:

what kind of decision tree this is

ret

public static final DecisionTree.Return ret(DFA.TransActions transActions)

Parameters:

transActions -

Returns:

a decision tree that takes transActions in response to any character

split

public static final DecisionTree split(char pivot,
                                       DecisionTree left,
                                       DecisionTree right)

Parameters:

pivot -

left -

right -

Returns:

the decision tree which maps characters to left or right depending on their position relative to pivot

switchTable

public static final DecisionTree switchTable(TreeMap<CSet,DFA.TransActions> table)

Parameters:

table -

Returns:

a decision tree expressing the given table as a switch between character sets

tabulated

public static final DecisionTree tabulated(char base,
                                           @NonNull DFA.TransActions[] table)

Parameters:

base -

table -

Returns:

a decision tree expressing the transition table of all characters between base and base + table.length, as given by table

toString

public String toString()

Overrides:

toString in class Object

simplify

public static DecisionTree simplify(DecisionTree tree)

This method tries to simplify the given tree in order to obtain an equivalent decision tree by removing useless parts.

Parameters:

tree -

Returns:

an optimized decision tree equivalent to tree

compile

public static DecisionTree compile(TreeMap<CSet,DFA.TransActions> partition)

Parameters:

partition - a transition table for a lexer's automaton cell, mapping sets of characters to the associated shifting action

Returns:

a decision tree that encodes the given transition table partition in a hopefully concise and efficient way

main

public static void main(String[] args)

Functional tests of decision trees and compile(TreeMap)

Parameters:

args -