package sedlex

  1. Overview
  2. Docs
An OCaml lexer generator for Unicode

Install 

dune-project
 Dependency

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

Authors

  1. Alain Frisch
  2. H
    https://github.com/ocaml-community/sedlex/graphs/contributors

Maintainers

  1. Alain Frisch

Sources

sedlex-3.8.1.tbz
sha256=b8efae9d2a9a39c2ca2c43a2684f3fb686a8775329f7f9b07c3e3d8a2b7682d6
sha512=ae6ac8282b9e899a510745d64a817d06d908bc61f29530568323eb4145b3db38cf61a82575e2b4c15825f570f2b270ab885c3d27adedbbbe7cdad12510de6d80

doc/sedlex.compiler/Sedlex_compiler/Sedlex/index.html

Module Sedlex_compiler.SedlexSource

Regexp combinators

Regular expressions are built from combinators and compiled to a DFA.

Sourcetype regexp

Abstract type of regular expressions.

Sourceval chars : Cset.t -> regexp

chars cset matches a single code point in cset.

Sourceval seq : regexp -> regexp -> regexp

seq r1 r2 matches r1 followed by r2 (concatenation).

Sourceval alt : regexp -> regexp -> regexp

alt r1 r2 matches r1 or r2 (alternation). When both operands are simple chars regexps, their character sets are merged into one.

Sourceval rep : regexp -> regexp

rep r matches zero or more repetitions of r (Kleene star).

Sourceval plus : regexp -> regexp

plus r matches one or more repetitions of r.

Sourceval repeat : regexp -> int -> int -> regexp

repeat r n m matches between n and m repetitions of r (bounded repetition). Requires 0 <= n <= m.

Sourceval eps : regexp

The empty regexp — matches the empty string (epsilon).

Sourceval compl : regexp -> regexp option

If the argument is a single chars regexp, returns a regexp which matches the complement set. Otherwise returns None.

Sourceval subtract : regexp -> regexp -> regexp option

If each argument is a single chars regexp, returns a regexp which matches the set (arg1 - arg2). Otherwise returns None.

Sourceval intersection : regexp -> regexp -> regexp option

If each argument is a single chars regexp, returns a regexp which matches the intersection set. Otherwise returns None.

Tagged DFA for as bindings

Named sub-match bindings (e.g. Star any as x) are implemented using tagged transitions in the DFA. Each as binding introduces up to two tags that record the start and end positions of the sub-match in the lexbuf's memory cells at runtime. When one boundary can be computed from a known offset, only one tag is needed (bind_start_only / bind_end_only); when both boundaries are known, no tags are needed at all.

Or-patterns (p1 as x) | (p2 as x) additionally use discriminator cells: integer values that record which branch was taken, so the PPX can extract the correct positions at match time.

Sourcetype tag_op =
  1. | Set_position of {
    1. dst : int;
    }
    (*

    Set_position {dst}: record the current lexbuf position in memory cell dst.

    *)
  2. | Set_value of {
    1. dst : int;
    2. value : int;
    }
    (*

    Set_value {dst; value}: record integer value in memory cell dst (used for or-pattern discriminators).

    *)
  3. | Copy of {
    1. dst : int;
    2. src : int;
    }
    (*

    Copy {dst; src}: copy the contents of cell src into cell dst. Emitted when determinization must preserve a position that a parallel NFA path is about to overwrite.

    *)

Tag operations emitted on DFA transitions.

Sourceval op_dest : tag_op -> int

op_dest op is the memory cell written by op.

Sourceval bind : regexp -> regexp * int * int

bind r wraps r with start/end tag epsilon nodes. Returns (wrapped_regexp, start_tag, end_tag) where start_tag and end_tag are the allocated memory cell indices.

Sourceval new_disc_cell : unit -> int

Allocate a fresh memory cell for an or-pattern discriminator.

Sourceval bind_disc : regexp -> int -> int -> regexp

bind_disc r cell value appends an epsilon node that sets cell to value after r matches. Used to tag each branch of an or-pattern so the PPX can tell which branch matched.

Sourceval bind_start_only : regexp -> regexp * int

Like bind, but only wraps with a start tag (no end tag). Used when the end position can be computed from a known offset.

Sourceval bind_end_only : regexp -> regexp * int

Like bind, but only wraps with an end tag (no start tag). Used when the start position can be computed from a known offset.

Sourceval reset_tags : unit -> unit

Reset the tag counter. Called before compiling each match%sedlex block.

DFA compilation

Sourcetype accept = {
  1. rule : int;
    (*

    The lowest-numbered, hence highest-priority, accepting rule, matching the first-match semantics of match%sedlex.

    *)
  2. final_ops : tag_op list;
    (*

    Tag operations to execute when entering the state, just before Sedlexing.mark: they materialize the accepting configuration into the cells read by the binding extraction code.

    *)
}

What an accepting state accepts.

Sourcetype dfa_state = {
  1. trans : (Cset.t * int * tag_op list) array;
    (*

    Each transition: (character set, target state, tag operations to execute when this transition fires). The operations form a parallel move: a Copy reads its source as it was before any operation of the same list executed, and no two operations write the same cell. They execute before the character of the transition is consumed. A character set is either Cset.eof or does not contain end of input, and the target of a Cset.eof transition has no transitions: end of input is read once.

    *)
  2. accept : accept option;
    (*

    None for non-accepting states.

    *)
}
Sourcetype dfa = dfa_state array

DFA states, indexed by state number. State 0 is the initial state.

Sourcetype compiled = {
  1. dfa : dfa;
  2. num_tags : int;
    (*

    Total number of memory cells needed at runtime. When num_tags = 0, no memory is allocated (pattern has no as bindings).

    *)
}

Result of compile.

Sourceval compile : regexp array -> compiled

compile rules determinizes the NFA for an array of regexp rules using subset construction. Returns the DFA and the total number of memory cells needed for as bindings. State 0 is always the initial state.

High-level compilation from IR

compile_ir takes an array of Ir.t patterns, handles tag allocation (including Start_plus/End_minus optimizations), discriminator insertion for or-patterns, and DFA construction. Returns the DFA and all information needed to generate binding extraction code.

Sourcetype pos_expr =
  1. | Tag of {
    1. tag : int;
    2. offset : int;
    }
    (*

    Read memory cell tag and add offset.

    *)
  2. | Start_plus of int
    (*

    Position is n code points from the token start.

    *)
  3. | End_minus of int
    (*

    Position is n code points before the token end.

    *)

How to compute a sub-match boundary position at runtime.

Sourcetype compiled_binding = {
  1. name : string;
  2. start_pos : pos_expr;
  3. end_pos : pos_expr;
  4. disc : (int * int) list;
    (*

    Discriminator conditions: (cell, value) pairs. Empty for simple (non-or) bindings. For or-patterns, branches with different positions have distinct values; branches with identical positions share a value.

    *)
}

Information about a single binding in the compiled output.

Sourcetype compiled_ir = {
  1. dfa : dfa;
  2. num_tags : int;
  3. bindings : compiled_binding list array;
    (*

    bindings.(i) is the list of binding info for rule i.

    *)
}

Result of compile_ir.

Sourceval compile_ir : Ir.t array -> compiled_ir

compile_ir rules compiles an array of IR patterns into a tagged DFA. Raises Assert_failure if invariant checking fails.

Sourceval dfa_to_dot : dfa -> string

dfa_to_dot dfa returns a Graphviz DOT representation of the DFA, including state labels, accepting state markers, transition character sets, and tag operations on edges.