org.sc3d.apt.sss.v3
Class NDFA

java.lang.Object
  org.sc3d.apt.sss.v3.NDFA

public class NDFA
extends java.lang.Object

Represents a non-determinstic finite automaton for parsing a particular grammar. Any Grammar can be converted into an NDFA using the 'make()' method. Unless your requirements are unusual, you probably don't need to use NDFAs directly, as Parser wraps it all up for you.

Ingredients

An NDFA consists of:

• a set of states, one of which is the initial state and one the final State, and
• a set of transitions between the states, each representing a step in a depth-first construction of a parse-tree.

Parsing using an NDFA

Every sentence of the grammar corresponds to sequence of transitions that leads from the initial state to the final state. If the construction steps represented by the transitions are performed in order, the effect is to construct the parse-tree of the sentence. Alternatively, reading only the 'shift' steps (see below) lists the Tokens of the sentence in order.

Thus to parse a sentence it suffices to find a suitable path from the initial to the final state. To resolve ambiguity in the grammar, the transitions from each state are ordered from most preferred to least preferred.

Depth-first construction of a Tree

For the purposes of this class, a depth-first construction of a Tree is one in which every non-terminal is constructed before its child Trees, and in which children are constructed in left-to-right order. Thus at an intermediate stage of the construction there may be many Trees, and the right-hand Tree at each level may not yet have all of its children.

Each step in a depth-first construction takes such a list of Trees and applies a simple modification to it. The effect of all the steps together is to turn an empty list into a list containing exactly one tree, which is the final parse-tree.

In addition to no-op transitions, which do nothing, there are three kinds of Transition:

• A shift transition adds a Tree.Terminal to the list.
• An open transition adds an empty Tree.NonTerminal to the list. The NonTerminal is empty in the sense that its 'length' field is zero.
• A reduce transition takes the right-hand few Trees and wraps them up as a Tree.Production, which it then adds as a child to the preceding Tree.NonTerminal.

Those shift transitions which construct Tree.Brackets provide an NDFA for parsing the contents of the brackets.

Representation

States are represented by instances of NDFA.State, and transitions are represented by instances of NDFA.Transition. Every State knows the Transitions that lead from it, and every Transition knows the State it leads to. It is therefore possible to follow paths through an NDFA forwards only. Every NDFA knows its initial and final States, but States do not know to which NDFA they belong. It is therefore possible for NDFAs to share States.

The various different kinds of Transition are all represented by instances of Transition, and are distinguished according to which fields are set to non-null values. For example, a Transition is a no-op if all of its fields (apart from 'to') are 'null'.

Nested Class Summary

static class	NDFA.State Represents a state of an NDFA.
static class	NDFA.Transition Represents a transition of an NDFA.

Field Summary

NDFA.State	finalState The final State of this NDFA.
NDFA.State	initialState The initial State of this NDFA.

Constructor Summary

NDFA(NDFA.State initialState, NDFA.State finalState)
Constructs an NDFA, given its initial and final States.

Method Summary

static NDFA	make(NDFA.State init, NDFA.State fin, Grammar grammar) Constructs and returns an NDFA representing 'grammar'.
static NDFA	makeProduction(NDFA.State init, NDFA.State fin, Grammar.Production production) Constructs and returns an NDFA representing 'production'.
java.lang.String	toString() Returns a String representation of this NDFA, including all States reachable from 'this.initialState'.

Methods inherited from class java.lang.Object

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

Field Detail

initialState

public final NDFA.State initialState

The initial State of this NDFA.

finalState

public final NDFA.State finalState

The final State of this NDFA.

Constructor Detail

NDFA

public NDFA(NDFA.State initialState,
            NDFA.State finalState)

Constructs an NDFA, given its initial and final States. See also 'make()# and 'makeProduction()'.

Method Detail

make

public static NDFA make(NDFA.State init,
                        NDFA.State fin,
                        Grammar grammar)

Constructs and returns an NDFA representing 'grammar'. If 'grammar' is a Grammar.Terminal, the NDFA will be just a single shift transition. If 'grammar' is a Grammar.NonTerminal, then the NDFA will consist of one open transition followed by the parallel composition of parts constructed using 'makeProduction()' joined up with some no-op transitions.

The returned NDFA will have the property that any two different paths with the same start and end points both contain shift transitions. In particular, every cycle includes at least one shift transition.

The initial and final States for the new NDFA are passed as arguments. All other States are freshly constructed. If you want the initial and/or final States freshly constructed, just pass 'new State()'. Outgoing transitions are added to the initial State and for repeatable NonTerminals also to the final State.

Parameters:

init - the desired initial State.

fin - the desired final State.

grammar - the Grammar to represent.

makeProduction

public static NDFA makeProduction(NDFA.State init,
                                  NDFA.State fin,
                                  Grammar.Production production)

Constructs and returns an NDFA representing 'production'. The NDFA will consist of a chain of parts constructed using 'make()' followed by a reduce transition.

The returned NDFA will has the property that any two different paths with the same start and end points both contain shift transitions. In particular, every cycle includes at least one shift transition.

The initial and final States for the new NDFA are passed as arguments. All other States are freshly constructed. If you want the initial and/or final States freshly constructed, just pass 'new State()'. Outgoing transitions are added to the initial State but not to the final State.

Parameters:

init - the desired initial State.

fin - the desired final State.

production - the Grammar.Production to represent.

toString

public java.lang.String toString()

Returns a String representation of this NDFA, including all States reachable from 'this.initialState'.

Overrides:

toString in class java.lang.Object