package lrgrep

  1. Overview
  2. Docs
Detailed error messages for Menhir-generated parsers

Install 

dune-project
 Dependency

github.com Readme Changelog Edit opam file Versions (2)

Authors

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Maintainers

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Sources

lrgrep-0.9.tbz
sha256=e53de12e4c5cbe6bca00643593266b4f9fa2e3f6a138195eeff7a4329f5c1c75
sha512=7fd7c4d11506fea7cc11c9bbf5aea9142d905643553c0c90e1bb16b794106b0c14a266acf89ae91b6929008dc0ba6515f788642873e2e4ba6c3d49bd45d25127

doc/kernel/Kernel/Automata/Dataflow/index.html

Module Automata.DataflowSource

Multi-pass dataflow analysis on the DFA.

Computes liveness, definedness, register allocation, and priority chains via fixpoint iteration. The analysis proceeds in passes: 1. Reachability of branches from accepting states 2. Mark reachable transitions (usage tracking) 3. Dead-code analysis and unreachable clause warnings 4. Priority splits (which positions can distinguish clause precedence) 5. Priority chain construction via Order_chain 6. Accepted-before computation (for pruning priority changes) 7. Liveness analysis (which captures are needed at each state) 8. Definedness analysis (which captures have been produced) 9. Variable class computation (for register allocation) 10. Register allocation (naive greedy by variable class)

A pairing of source and target order chain elements for a transition.

Sourcetype 'n _var_classes = {
  1. domain : 'n Fix.Indexing.cardinal;
  2. mutable classes : 'n var Utils.Misc.indexset list;
}
Sourcetype var_classes =
  1. | V : 'n _var_classes -> var_classes
Sourcetype ('g, 'r, 'dfa) t = {
  1. pairings : ('dfa, (('g, 'r) Spec.branch Fix.Indexing.index * chain) list list) Fix.Indexing.vector;
    (*

    For each state and each outgoing transition, the priority chain pairings between source and target order chain elements.

    *)
  2. accepts : ('dfa, (('g, 'r) Spec.branch Fix.Indexing.index * priority) list) Fix.Indexing.vector;
    (*

    For each state, the list of accepted branches with their priorities.

    *)
  3. liveness : ('dfa, Regexp.Capture.set array) Fix.Indexing.vector;
    (*

    For each state and each kernel position, the set of captures that are live (needed) from this point onward.

    *)
  4. defined : ('dfa, Regexp.Capture.set array) Fix.Indexing.vector;
    (*

    For each state and each kernel position, the set of captures that have been defined along some path to this state.

    *)
  5. classes : ('dfa, var_classes) Fix.Indexing.vector;
    (*

    For each state, the variable classes used for register allocation.

    *)
  6. registers : ('dfa, Lrgrep_support.Register.t Regexp.Capture.map array) Fix.Indexing.vector;
    (*

    For each state and each kernel position, the mapping from captures to allocated registers.

    *)
  7. register_count : int;
    (*

    Total number of registers allocated across all states.

    *)
  8. accepted_before : ('dfa, ('g, 'r) Spec.branch Utils.Misc.indexset) Fix.Indexing.vector;
    (*

    For each state, the set of branches that have been accepted on some path to this state. Used for pruning priority remappings.

    *)
}

Results of the dataflow analysis.

Sourceval liveness : ('g, 'r, 'dfa) t -> ('g, 'r, 'dfa, 'n) DFA.state -> ('n, Regexp.Capture.set) Fix.Indexing.Vector.t
Sourceval defined : ('g, 'r, 'dfa) t -> ('g, 'r, 'dfa, 'n) DFA.state -> ('n, Regexp.Capture.set) Fix.Indexing.Vector.t
Sourceval registers : ('g, 'r, 'dfa) t -> ('g, 'r, 'dfa, 'n) DFA.state -> ('n, Lrgrep_support.Register.t Regexp.Capture.map) Fix.Indexing.Vector.t
Sourceval classes : ('g, 'r, 'dfa) t -> ('g, 'r, 'dfa, 'n) DFA.state -> 'n var Utils.Misc.indexset list
Sourcetype ('g, 'r, 'dfa, 'tgt) rev_mapping =
  1. | Rev_mapping : ('g, 'r, 'dfa, 'src) DFA.state * ('src, 'tgt) DFA.mapping -> ('g, 'r, 'dfa, 'tgt) rev_mapping

Reverse mapping: from a target state back to a source state and the associated kernel mapping. Used for backward dataflow analysis.

Sourcetype ('g, 'r, 'dfa) packed_rev_mapping =
  1. | Rev_packed : ('g, 'r, 'dfa, 'n) rev_mapping list -> ('g, 'r, 'dfa) packed_rev_mapping

Packed list of reverse mappings for a DFA state.

Sourceval dump : 'a Kernel__Info.grammar -> ('a, 'b, 'c) DFA.t -> ('a, 'b, 'c) t -> Stdlib.out_channel -> unit
Sourceval reverse_transitions : ('a, 'b, 'c) DFA.t -> ('c, ('a, 'b, 'c) packed_rev_mapping) Fix.Indexing.Vector.t

Reverse the DFA transition graph for backward analysis.

Sourceval make : ('g, 'r) Spec.branches -> ('g, 'r, 'dfa) DFA.t -> ('g, 'r, 'dfa) t

Run the full dataflow analysis pipeline on a DFA.

Executes 10 passes: reachability, usage marking, dead-code analysis, priority splits, priority chain construction, accepted-before, liveness, definedness, variable classes, and register allocation. Returns the complete analysis results.