automaton__compute_reachable_state Function

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

Uses

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

It scans through the NFA states and finds the set of reachable states by the given input symbol, excluding ε-transitions.

Type Bound

automaton_t

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)


Source Code

   pure function automaton__compute_reachable_state(self, curr_i, symbol) result(state_set)
      use :: forgex_segment_m, only: operator(.in.), operator(/=)
      use :: forgex_nfa_node_m, only: nfa_state_node_t, nfa_transition_t
      use :: forgex_lazy_dfa_node_m, only: dfa_transition_t
      use :: forgex_cube_m, only: cube_t, operator(.in.)
      implicit none
      class(automaton_t), intent(in) :: self
      integer(int32),     intent(in) :: curr_i      ! current index of dfa
      character(*),       intent(in) :: symbol

      type(nfa_state_set_t)  :: state_set    ! RESULT variable
      type(nfa_state_set_t)  :: current_set
      integer                :: i, j, k

      ! temporary variables ... to increase the cache hit rate
      ! type(nfa_state_node_t) :: n_node       ! This variable simulates a pointer.
      ! type(segment_t), allocatable :: segs(:)
      ! type(nfa_transition_t)       :: n_tra
      ! type(cube_t) :: cube
      integer :: dst

      call init_state_set(state_set, self%nfa%top)

      current_set = self%dfa%nodes(curr_i)%nfa_set

      ! Scan the entire NFA states.
      outer: do i = 1, self%nfa%top

         ! If the i-th element of current state set is true, process the i-th NFA node.
         if (check_nfa_state(current_set, i)) then

            if (.not. allocated(self%nfa%graph(i)%forward)) cycle

            ! Scan the all transitions belong to the NFA state node.
            middle: do j = 1, self%nfa%graph(i)%forward_top

               dst = self%nfa%graph(i)%forward(j)%dst

               ! If it has a destination,
               if (dst /= NFA_NULL_TRANSITION) then

                     ! If the symbol is in the cube on the transition forward(j).
                     if (symbol .in. self%nfa%graph(i)%forward(j)%c) then
      
                        ! Add the index of the NFA state node to `state_set` of type(nfa_state_set_t).
                        call add_nfa_state(state_set, dst)

                     end if

               end if

            end do middle

         end if
      end do outer

   end function automaton__compute_reachable_state