automaton_t Derived Type

type, public :: automaton_t

This type contains an NFA graph, and the DFA graph that are derived from it.


Components

Type Visibility Attributes Name Initial
type(segment_t), public, allocatable :: all_segments(:)
type(dfa_graph_t), public :: dfa
type(nfa_state_set_t), public :: entry_set
integer(kind=int32), public :: initial_index = DFA_NOT_INIT
type(nfa_graph_t), public :: nfa
integer(kind=int32), public :: nfa_entry
integer(kind=int32), public :: nfa_exit
type(tree_t), public :: tree

Type-Bound Procedures

procedure, public :: construct => automaton__construct_dfa

  • private pure subroutine automaton__construct_dfa(self, curr_i, dst_i, symbol)

    This subroutine gets the destination index of DFA nodes from the current index with given symbol, adding a DFA node if necessary.

    Read more…

    Arguments

    Type IntentOptional Attributes Name
    class(automaton_t), intent(inout) :: self
    integer(kind=int32), intent(in) :: curr_i
    integer(kind=int32), intent(inout) :: dst_i
    character(len=*), intent(in) :: symbol

procedure, public :: destination => automaton__destination

  • private pure subroutine automaton__destination(self, curr, symbol, next, next_set)

    This subroutine gets the next DFA nodes index from current index and symbol, and stores the result in next and next_set.

    Arguments

    Type IntentOptional Attributes Name
    class(automaton_t), intent(in) :: self
    integer(kind=int32), intent(in) :: curr
    character(len=*), intent(in) :: symbol
    integer(kind=int32), intent(inout) :: next
    type(nfa_state_set_t), intent(inout) :: next_set

procedure, public :: epsilon_closure => automaton__epsilon_closure

procedure, public :: free => automaton__deallocate

procedure, public :: get_reachable => automaton__compute_reachable_state

  • private pure function automaton__compute_reachable_state(self, curr_i, symbol) result(state_set)

    This function calculates a set of possible NFA states from the current DFA state by the input character symbol.

    Read more…

    Arguments

    Type IntentOptional Attributes Name
    class(automaton_t), intent(in) :: self
    integer(kind=int32), intent(in) :: curr_i
    character(len=*), intent(in) :: symbol

    Return Value type(nfa_state_set_t)

procedure, public :: init => automaton__initialize

  • private pure subroutine automaton__initialize(self)

    This subroutine reads tree and tree_top variable, constructs the NFA graph, and then initializes the DFA graph.

    Arguments

    Type IntentOptional Attributes Name
    class(automaton_t), intent(inout) :: self

procedure, public :: move => automaton__move

  • private pure function automaton__move(self, curr, symbol) result(res)

    This function returns the dfa transition object, that contains the destination index and the corresponding set of transitionable NFA state.

    Arguments

    Type IntentOptional Attributes Name
    class(automaton_t), intent(in) :: self
    integer(kind=int32), intent(in) :: curr
    character(len=*), intent(in) :: symbol

    Return Value type(dfa_transition_t)

procedure, public :: preprocess => automaton__build_nfa

procedure, public :: print => automaton__print_info

  • private subroutine automaton__print_info(self)

    This subroutine provides the automata' summarized information.

    Arguments

    Type IntentOptional Attributes Name
    class(automaton_t), intent(in) :: self

procedure, public :: print_dfa => automaton__print_dfa

  • private subroutine automaton__print_dfa(self, uni)

    This subroutine prints DFA states and transitions to a given unit number.

    Arguments

    Type IntentOptional Attributes Name
    class(automaton_t), intent(in) :: self
    integer(kind=int32), intent(in) :: uni

procedure, public :: register_state => automaton__register_state

  • private pure subroutine automaton__register_state(self, state_set, res)

    This subroutine takes a nfa_state_set_t type argument as input and register the set as a DFA state node in the DFA graph.

    Read more…

    Arguments

    Type IntentOptional Attributes Name
    class(automaton_t), intent(inout) :: self
    type(nfa_state_set_t), intent(in) :: state_set
    integer(kind=int32), intent(inout) :: res

Source Code

   type, public :: automaton_t
      !! This type contains an NFA graph, and the DFA graph that are derived from it.
      type(tree_t)                 :: tree
      type(nfa_graph_t)            :: nfa
      type(dfa_graph_t)            :: dfa
      type(nfa_state_set_t)        :: entry_set
      type(segment_t), allocatable :: all_segments(:)
      integer(int32)               :: nfa_entry, nfa_exit
      integer(int32)               :: initial_index = DFA_NOT_INIT
   contains
      procedure :: preprocess      => automaton__build_nfa
      procedure :: init            => automaton__initialize
      procedure :: epsilon_closure => automaton__epsilon_closure
      procedure :: register_state  => automaton__register_state
      procedure :: construct       => automaton__construct_dfa
      procedure :: get_reachable   => automaton__compute_reachable_state
      procedure :: move            => automaton__move
      procedure :: destination     => automaton__destination
      procedure :: free            => automaton__deallocate
      procedure :: print           => automaton__print_info
      procedure :: print_dfa       => automaton__print_dfa
   end type automaton_t