NDFA PRELIMINARY DESIGN

File:		ndfa.pd
Author:		course (walton@das.harvard.edu)
Version:	1


1. Goal

The NDFA package implements NDFAs, including functions
for building NDFAs, a function for printing an NDFA,
and a function for executing an NDFA with a given input
string.

2. Data Grammar

    state ::= ( character-transition,
		empty-transition )

    character-transition ::=
	( character-transition-label,
	  pointer-to-character-transition-target )

    empty-transition ::=
	( pointer-to-empty-transition-target )

    transition-label ::= character

    transition-target ::= state

    state_table ::= ( vector-of-states,
		      pointer-to-first-unused-state )

    ndfa ::= ( pointer-to-initial-state,
	       pointer-to-final-state )

Note: Inside a state, the pointers to target transitions
      are NULL if the transitions are unused.

Note: The maximum number of states needed is twice
      the number of characters in the RE, so this
      bounds the size of the state-table.

Note: The final state of an NDFA always has its
      empty-transition unused.

Note: The label of the character transition may be
      # or ?.

3. C++ Type Synopsis

    class state {
	char		character;	      // label
	state *		character_transition; // target
	state *		empty_transition; }   // target

    const int MAXSTATES = 200;

    class state_table {
	state		table [MAXSTATES];
	state *		next;	// First unused state.

    extern state_table the_state_table;

    class ndfa {
	state *		initial;
	state *		final; }

4. C++ NDFA Package User Function Summary 

4.1 Functions to Build NDFAs:

    Let n, n1, n2 be ndfa's for REs E, E1, E2,
    respectively. 

    C++ Function:				RE:

    ndfa single_character ( char ch );		ch
    ndfa concatenate ( ndfa n1, ndfa n2 );	E1E2
    ndfa alternate ( ndfa n1, ndfa n2 );	E1|E2
    ndfa star ( ndfa n );			E*
    ndfa plus ( ndfa n );			E+

4.2 Function to use NDFAs:

    Let:	ndfa n;

    bool n.run ( char * input_string,
		 bool trace = false );

4.3 User Functions on State Table:

    Let:	state_table t;

    Function to initialize state table:

	t.init ();

    Operator to print state table:

	some_ostream << t

5. C++ NDFA Package Internal Function Summary 

5.1 NDFA Constructor for Internal Use:

    ndfa ( state * initial, state * final );

5.2 Functions on State Table:

    Let:	state_table t;

    Function to allocate a state to table:

	state * t.next_unused_state ();

    Function to get index of state:

	int t.get_index ( state * s );

    Function to get state from index:

	state * t.get_state ( int index );

    Abbreviations to make code readable:

	Abbreviation
	    	Abbreviates

	new_state ()
		the_state_table.next_unused_state ()

	get_index ( s )
		the_state_table.get_index ( s )

	get_state ( i )
		the_state_table.get_state ( i )

5.3 Functions to Initialize State:

    Let:	state * s;

    Function to set both transitions to unused:

	void s->init ();

    Function to set empty transition:

	void s->on_empty_goto ( state * target);

    Function to set character transition:

	void s->on_character_goto
		( char c, state * target );

	Note: c may be '#' or '?'.

6. Example of Printouts:

6.1 Result of `cout << the_state_table' for RE `axb|ayb'

    State Table:
	0    a ---> 1
	1    # ---> 4
	2    a ---> 3
	3    # ---> 6
	4    x ---> 5
	5    # ---> 8
	6    y ---> 7
	7    # ---> 10
	8    b ---> 9
	9    # ---> 13
	10    b ---> 11
	11    # ---> 13
	12    # ---> 0    # ---> 2
	13

6.2 Result of `n.run ( "axb", true )' if n is the NDFA
    with initial state 12 and final state 13.

    Start Run with initial state 12 and final state 13
	Begin Step 1 at `a' and states 12:
	   12 == 0
	   12 == 2
	   0 --> 1
	   2 --> 3
	Begin Step 2 at `x' and states 1 3:
	   1 == 4
	   3 == 6
	   4 --> 5
	Begin Step 3 at `b' and states 5:
	   5 == 8
	   8 --> 9
	Begin Step 4 at end of string and states 9:
	   9 == 13
	Returning TRUE