COMMENT @%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	Copyright (c) Geoworks 1997.  All rights reserved.

PROJECT:	GEOS
MODULE:		NDPDA (Non Deterministic Push Down Automata) library
FILE:		ndpda.def

AUTHOR:		Chris Thomas, Jan 03, 1997

REVISION HISTORY:
	Name	Date		Description
	----	----		-----------
	cthomas	1/03/97   	Initial revision

DESCRIPTION:

	Public interface of the Non Deterministic Push Down Automata
	library.

	This library provides an engine for interpreting a
	non-deterministic push-down automaton, complete with
	states, inputs, stack tokens, and built-in action primitives
	that can be executed when making a transition.  Inputs,
	Tokens, and actions can be extended by the client application.

	The non-deterministic behavior of the state machine is
	handled by creating a new 'fork' for every applicable
	transition, each fork following a different transition.
	When input arrives at the PDA, each fork receives the input,
	and applies all applicable transitions.

	Note that in the worst case, non-deterministic state machines
	can require space exponential in the length of the input,
	so this implementation is not recommended for machines
	with a large branching factor.
	
	$Id: ndpda.def,v 1.1 97/04/04 14:27:09 newdeal Exp $

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@

SetDef	_ndpda

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;;		NDPDA Types
;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;
;;; States are identified by the offset of their structure within
;;; a memory block
;;;

NDPDAState	type	nptr ; nptr.NDPDATransition, but swat doesn't grok this
	NDPDAS_DEAD	equ	0xffff		; Moving to this state
						; terminates a fork

;;;
;;; Inputs to the NDFSM are 16-bit values
;;;

NDPDAInput	type	word
	NDPDAI_LAMBDA_LO	equ	0xffff
	NDPDAI_LAMBDA_HI	equ	0x0000

;;;
;;; Stack tokens are 16 bit values.  When comparing against the token
;;; on the top of the stack, the logical NOT of a token is taken
;;; to mean that the token should not match the top of the stack.
;;; Therefore, only the lower 15 bits are used to represent tokens,
;;; and the 16th bit is used to indicate a negated token.
;;;

NDPDAStackToken	etype	word, 0, 1
	NDPDAST_EMPTY		enum	NDPDAStackToken, 0x7fff
		; Stack is empty

	NDPDAST_WILDCARD	enum	NDPDAStackToken, 0
		; always matches

	NDPDAST_NOT_EMPTY	equ	<not NDPDAST_EMPTY> ; Stack not empty

;;;
;;; Each active fork maintains its own set of local variables, which the
;;; transition actions can use to store and look up data as they
;;; traverse the FSM.  Variables are referenced by NDPDAVariable,
;;; which can be arbitrary word values.
;;;

NDPDAVariable	type	word

;;;
;;; Forks may be assigned 'labels', which can be used later by the
;;; KILL action to kill a set of forks.
;;;

NDPDALabel	type	word
	NDPDAL_MY_LABEL	equ	0		; kill forks with same label
						; as current fork

;;;
;;; The actions themselves are 16-bit opcodes, followed by any arguments
;;; the opcode takes.  These are the built-in action opcodes, but
;;; they can be extended by the application.  All opcodes in an action
;;; are executed before the FSM advances to the next state.
;;;
;;; All of the arguments to the built-in opcodes are word-sized,
;;; but applications are free to use any data type as an argument
;;; in their own opcodes.
;;;
;;; Most action opcodes operate only on the current fork making
;;; the transition.  Exceptions are noted in the description.
;;;


NDPDAActionOpcode	etype	word
	NDPDAAO_END		enum	NDPDAActionOpcode
	;
	; Args: none
	;
	; End of action.  PDA continues with next state.

	NDPDAAO_CALLSTATE	enum	NDPDAActionOpcode
	;
	; Args: nextState, N, state1, state2, ... stateN
	;
	; after NDPDAAO_END, PDA continues at nextState.
	; state1..stateN are pushed onto an internal state stack,
	; much like a return address is pushed in a conventional
	; function call.  The value of NDPDAT_nextState is ignored.
	;
	; If N==0, then the nextState of the transition is pushed
	; as the single return state.

	NDPDAAO_RETURNSTATE	enum	NDPDAActionOpcode
	;
	; Args: N
	;
	; All states pushed by the most recent NDPDAAO_CALLSTATE
	; are popped, and the FSM advances to the N'th of them.
	;

	NDPDAAO_PUSHTOKEN	enum	NDPDAActionOpcode
	;
	; Args: token
	;
	; Token is pushed onto the PDA stack
	;

	NDPDAAO_POPTOKEN	enum	NDPDAActionOpcode
	;
	; Args: none
	;
	; Token is popped from the PDA stack.  Does nothing if
	; stack is empty.
	;

	NDPDAAO_LABEL		enum	NDPDAActionOpcode
		NDPDA_NULL_LABEL	equ	0
	;
	; Args: word:label
	;
	; Assigns a numeric label to the current fork of the FSM,
	; to be used by the KILL opcode.  NULL_LABEL is the equivalent
	; of having no label.
	;

	NDPDAAO_KILL		enum	NDPDAActionOpcode
		NDPDA_SELF_LABEL	equ	0
	;
	; Args: word:label
	;
	; After the current input has been processed by all forks,
	; any fork assigned the label is terminated.  Use
	; SELF_LABEL to kill forks with the same label as the current fork.
	;

	NDPDAAO_RECORD		enum	NDPDAActionOpcode
	;
	; Args: variable
	;
	; The current input word is stored at the end of a local
	; variable belonging to the current fork.  If there is no
	; current input (as in a lambda transition), then nothing
	; is stored.
	;

	NDPDAAO_RESETVAR	enum	NDPDAActionOpcode
	;
	; Args: variable
	;
	; Resets a fork's local variable to zero length
	;

	NDPDAAO_UNGET		enum	NDPDAActionOpcode
	;
	; Args: none
	;
	; Puts the current input word back into the input stream, to
	; be processed again by the next state.
	;

	NDPDAAO_GOTO		enum	NDPDAActionOpcode
	;
	; Args: action
	;
	; Continues processing the action at ACTION
	;

	NDPDAAO_FIRST_UNUSED_BUILT_IN	enum	NDPDAActionOpcode
	NDPDAAO_LAST_BUILT_IN		enum	NDPDAActionOpcode, 0x3f
	NDPDAAO_FIRST_APP_DEFINED	equ	0x40
	;
	; Applications may define their own opcodes starting after
	; NDPDAAO_FIRST_BUILT_IN
	;

;;;
;;; Actions are given by an offset to the instruction sequence that
;;; executes the action
;;;

NDPDAAction	type	nptr ; nptr.word, but swat doesn't grok
	NDPDAA_NONE	equ	0xffff		; when no action desired

;;;
;;; If the input and token on top of the stack match a transition,
;;; the fork takes the specified action, and moves to the next state.
;;;
;;; To negate an input range (input matches if it is not in
;;; inclusive range), swap lo and hi
;;;
;;; For lambda transitions (no input requred to move to next state),
;;; use NDPDAI_LAMBDA_LO/HI for inputLo/Hi
;;;

NDPDATransition	struct
	NDPDAT_inputLo	NDPDAInput			NDPDAI_LAMBDA_LO
	NDPDAT_inputHi	NDPDAInput			NDPDAI_LAMBDA_HI
		; range of inputs (inclusive) for this transition

	NDPDAT_stackTop	NDPDAStackToken			NDPDAST_WILDCARD
		; Token on stack to match

	NDPDAT_nextState nptr.NDPDATransition		NDPDAS_DEAD
		; State to move to

	NDPDAT_action	nptr.NDPDAActionOpcode		NDPDAA_NONE
		; action to take on transition

		NDPDA_EOT	equ	0
	NDPDAT_nextTransition nptr.NDPDATransition	NDPDA_EOT
		; location of next transition in state.
		; (NDPDA_EOT if end of transitions for this state)

NDPDATransition	ends

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;;		NDPDA Primitives
;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

StartLibrary	ndpda

global	NDPDACallState:far
global	NDPDADerefAppData:far
global	NDPDAFinish:far
global	NDPDAForkEnum:far
global	NDPDAGetInput:far
global	NDPDAGetVar:far
global	NDPDAGotoState:far
global	NDPDAGrowVar:far
global	NDPDAInit:far
global	NDPDAKill:far
global	NDPDAPeekToken:far
global	NDPDAPopToken:far
global	NDPDAProcessInput:far
global	NDPDAPushToken:far
global	NDPDAResizeVar:far
global	NDPDAReturnState:far
global	NDPDASetLabel:far
global	NDPDAStart:far
global	NDPDAUngetInput:far

EndLibrary	ndpda
