package lrgrep

  1. Overview
  2. Docs
Analyse the stack of a Menhir-generated LR parser using regular expressions

Install 

dune-project
 Dependency

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

Authors

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

Maintainers

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

Sources

lrgrep-0.3.tbz
sha256=84a1874d0c063da371e19c84243aac7c40bfcb9aaf204251e0eb0d1f077f2cde
sha512=5a16ff42a196fd741bc64a1bdd45b4dca0098633e73aa665829a44625ec15382891c3643fa210dbe3704336eab095d4024e093e37ae5313810f6754de6119d55

doc/lrgrep.runtime/Lrgrep_runtime/index.html

Module Lrgrep_runtimeSource

The Runtime library is used by the generated programs. It defines a compact representation for the automaton in the form of simple bytecoded instructions and a sparse index.

Sourcetype lr1 = int

At runtime, an lr1 state is just an integer

Sourcetype clause = int

For the interpreter, a clause is also represented by an integer. When a clause matches, its id is returned and it is the duty of the (generated) client program to map it to a semantic action.

Sourcetype register = int

Registers are also named by small integers.

Sourcetype priority = int
Sourcemodule Sparse_table : sig ... end

A sparse table stores many partial mapping from 0..k-1 to 0..v-1 (the set of keys and values) and is directly serialized to a string.

Sourcetype program_code = string

The code of a program is a sequence of serialized program_instruction

Sourcetype program_counter = int

A program_counter is an offset in the program_code string. By construction it always point at the beginning of an instruction (otherwise, it is invalid).

Sourcetype program_instruction =
  1. | Store of register
    (*

    Store r stores the state at the top of the parser stack in register r.

    *)
  2. | Move of register * register
    (*

    Move (src, dst) sets register dst to the value in register src.

    *)
  3. | Swap of register * register
    (*

    Swap (r1, r2) exchanges the values of register r1 and r2.

    *)
  4. | Clear of register
  5. | Yield of program_counter
    (*

    Jump and consume input: Yield pc stops the current interpretation to consume one state of the input stack. After consuming, execution should resume at pc.

    *)
  6. | Accept of clause * priority * register option array
    (*

    When reaching Accept (clause, priority, captures), the matcher found that clause number clause is matching at priority level priority. Add it to the set of matching candidates. If clause already match, replace the match if priority is less than or equal to the previous level. Resume execution. captures defines the variables captured in the clause definition: None if it is unbound, Some reg if it is bound to the value stored in register reg.

    *)
  7. | Match of Sparse_table.row
    (*

    Match sidx lookup the sparse table for a cell matching the state at the top of the parser stack at index sidx. If the lookup is successful, it returns the pc should jump to. If unsuccesful, execution continue on next instruction.

    *)
  8. | Priority of clause * priority * priority
    (*

    Priority (clause, p1, p2) remaps the priority of a previous match. If clause matched at priority p1, it should now be considered a match at priority p2.

    *)
  9. | Halt
    (*

    Program is finished, there will be no more matches.

    *)

The instructions of the bytecode language of the matcher

The type of values stored in a register. All registers are initialized with Empty, and Clear set a register back to empty. Value x represents the capture of semantic value x. Initial is a place holder that represents the initial frame of the parser's stack. There is no semantic value associated to it, but one can still refer to the position, which will be the initial position of the file being parsed.

Sourcetype 'a register_value =
  1. | Empty
  2. | Location of Lexing.position * Lexing.position
  3. | Value of 'a
Sourcetype 'a register_values = 'a register_value array

program_step program pc decodes the instruction at address !pc and increases pc.

Sourcetype program = {
  1. registers : int;
  2. initial : program_counter;
  3. table : Sparse_table.t;
  4. code : program_code;
}

All the elements composing an error matching program.

Sourcemodule type Parser = sig ... end

A minimal module type mimicking Menhir incremental interface, suitable to run a matching program.

Sourcetype 'element candidate = clause * 'element register_values

A matching candidate. An lrgrep program found that a clause matches with the a set of register values. However this might not be the clause with the highest priority. The action is not executed immediately and the candidate is saved for later. 'element is the type of stack elements (semantic values) of the parser.

Sourcemodule Interpreter (P : Parser) : sig ... end

Instantiate an interpreter for a parser representation