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/Machine/index.html

Module Automata.MachineSource

Sourcetype ('g, 'r) label = {
  1. filter : 'g Info.lr1 Utils.Misc.indexset;
    (*

    The set of LR(1) states that allow this transition to be taken.

    *)
  2. captures : (Regexp.Capture.t * Lrgrep_support.Register.t) list;
    (*

    Variables to capture and the register in which to store them when the transition is taken.

    *)
  3. clear : Lrgrep_support.Register.set;
    (*

    Registers to clear when the transition is taken (for captures that go out of scope or are undefined).

    *)
  4. moves : Lrgrep_support.Register.t Lrgrep_support.Register.map;
    (*

    Register-to-register transfers when taking this transition. Keys are source registers, values are target registers.

    *)
  5. priority : (('g, 'r) Spec.branch Fix.Indexing.index * priority * priority) list;
    (*

    Dynamic priority remappings for clause precedence. An element (c, p1, p2) means that a match of clause c at priority p1 in the source state corresponds to a match at priority p2 in the target state.

    *)
}

Bytecode representation of the automaton for code generation.

The machine is a sparse transition table with a register transfer language. Transitions carry labels with filters, captures, register moves, clears, and dynamic priority remappings.

Sourceval label_compare : ('a, 'b) label -> ('a, 'b) label -> int
Sourcetype ('g, 'r, 'st, 'tr) t = {
  1. initial : 'st Fix.Indexing.index option;
    (*

    Index of the initial state, or None if there are no viable patterns.

    *)
  2. source : ('tr, 'st Fix.Indexing.index) Fix.Indexing.vector;
    (*

    For each transition, the source state index.

    *)
  3. target : ('tr, 'st Fix.Indexing.index) Fix.Indexing.vector;
    (*

    For each transition, the target state index.

    *)
  4. label : ('tr, ('g, 'r) label) Fix.Indexing.vector;
    (*

    For each transition, its label (filter, captures, moves, clear, priority).

    *)
  5. unhandled : ('st, 'g Info.lr1 Utils.Misc.indexset) Fix.Indexing.vector;
    (*

    For each state, the set of LR(1) states for which stacks can reach this state but no transition is defined. These should be rejected at runtime.

    *)
  6. outgoing : ('st, 'tr Utils.Misc.indexset) Fix.Indexing.vector;
    (*

    For each state, the set of outgoing transition indices.

    *)
  7. accepting : ('st, (('g, 'r) Spec.branch Fix.Indexing.index * priority * Lrgrep_support.Register.t Regexp.Capture.map) list) Fix.Indexing.vector;
    (*

    For each state, the list of clauses accepted when reaching that state. Each clause comes with a priority level and a register mapping indicating where captured variables can be found. The first matching clause wins.

    *)
  8. branches : ('st, (('g, 'r) Spec.branch Fix.Indexing.index * bool * Lrgrep_support.Register.t Regexp.Capture.map) list) Fix.Indexing.vector;
    (*

    For each state, the list of clauses being recognized in that state. Each entry is (branch index, is_accepting, register mapping).

    *)
  9. register_count : int;
    (*

    Total number of registers used across all states.

    *)
  10. partial_captures : Regexp.Capture.set;
    (*

    Set of captures that may be only partially defined (some paths define them, others don't).

    *)
}

The machine representation for code generation.

A sparse transition table with register transfer operations. Parameterized by:

  • 'g is the grammar (input)
  • 'r is the set of rules (input)
  • 'st is the set of states (output)
  • 'tr is the set of transitions (output)
Sourcetype ('g, 'r) _t =
  1. | T : ('g, 'r, 'st, 'tr) t -> ('g, 'r) _t
Sourceval dump : 'a Kernel__Info.grammar -> ('a, 'b, 'c, 'd) t -> Stdlib.out_channel -> unit
Sourceval minimize : ('g, 'r) Spec.branches -> ('g, 'r, 'dfa) DFA.t -> ('g, 'r, 'dfa) Dataflow.t -> ('g, 'r) _t

Minimize the DFA and produce the final machine representation.

Converts the DFA with dataflow analysis results into a compact machine with sparse transition tables and register transfer language. Uses a refinement of Valmari's algorithm with custom decomposition:

  • States are refined by accepted actions (clauses and priorities)
  • Transitions are grouped by LR(1) filter and by register operations Returns None for the initial state if no patterns are viable.
Sourceval states : ('a, 'b, 'c, 'd) t -> 'c Fix__Indexing.cardinal