Module Automata.DFASource

Mapping from target kernel positions to (source position, captures, usage).

For each position in the target state's kernel, records which position in the source state's kernel it came from, along with the set of captures and usages associated with that transition.

Sourcetype ('g, 'r, 'dfa, 'n) state = {
  1. index : 'dfa Fix.Indexing.index;
  2. branches : ('n, ('g, 'r) Spec.branch Fix.Indexing.index) Fix.Indexing.vector;
    (*

    Branch index for each position in the kernel.

    *)
  3. accepting : 'n Utils.Boolvector.t;
    (*

    Which kernel positions correspond to accepting NFA states.

    *)
  4. mutable transitions : ('g, 'r, 'dfa, 'n) transition list;
    (*

    Outgoing transitions, populated during determinization.

    *)
}

DFA state.

Each state has a kernel of NFA states ordered by branch priority, a vector of branch indices, and a boolean vector marking which kernel positions are accepting.

Sourceand ('g, 'r, 'dfa, 'src) transition =
  1. | Transition : {
    1. label : 'g Info.lr1 Utils.Misc.indexset;
      (*

      Set of LR(1) states that trigger this transition.

      *)
    2. target : ('g, 'r, 'dfa, 'tgt) state;
      (*

      The target DFA state.

      *)
    3. mapping : ('src, 'tgt) mapping;
      (*

      Maps each target kernel position to its source kernel position and the associated captures/usage.

      *)
    } -> ('g, 'r, 'dfa, 'src) transition

DFA transition with a label (set of LR1 states), a target state, and a mapping from target kernel positions back to source positions.

Sourcetype ('g, 'r, 'dfa) packed =
  1. | Packed : ('g, 'r, 'dfa, 'n) state -> ('g, 'r, 'dfa) packed

Erased-phantom packed state, used for vector storage.

Sourcetype ('g, 'r, 'dfa) t = {
  1. initial : 'dfa Fix.Indexing.index;
    (*

    Index of the initial state.

    *)
  2. states : ('dfa, ('g, 'r, 'dfa) packed) Fix.Indexing.vector;
    (*

    All DFA states indexed by their DFA index.

    *)
  3. domain : ('dfa, 'g Info.lr1 Utils.Misc.indexset) Fix.Indexing.vector;
    (*

    For each state, the set of LR(1) states for which there exists a reachable stack that can reach this state.

    *)
  4. kernels : ('dfa, ('g, 'r) NFA.t array) Fix.Indexing.vector;
    (*

    For each state, the array of NFA states in its kernel (ordered by priority).

    *)
}

Complete DFA with all states, transitions, and kernel information.

Sourceval pp : Cmon.t -> string list
Sourceval dump : 'a Kernel__Info.grammar -> ('a, 'b, 'c) t -> 'a Redgraph.graph -> Stdlib.out_channel -> unit
Sourcetype ('g, 'r) _t =
  1. | T : ('g, 'r, 'dfa) t -> ('g, 'r) _t

Erased-phantom existential wrapper for the DFA.

Sourceval determinize : 'g Info.grammar -> ('g, 'r) Spec.branches -> ('g, 's) stacks -> ('a, ('g, 'r) NFA.t) Fix.Indexing.Vector.t -> ('g, 'r) _t

Determinize NFA branches into a DFA using modified power set construction.

Takes the grammar, error pattern branches, stack topology, and the initial stack position. Returns a DFA where states are hash-consed by their kernel (ordered array of NFA states). Only transitions corresponding to reachable LR stacks are constructed.

Sourceval state_count : ('a, 'b, 'c) t -> 'c Fix__Indexing.cardinal