Parameter Make.T

type state

The type of automaton states.

val number : state -> int

States are numbered.

type token

The type of tokens. These can be thought of as real tokens, that is, tokens returned by the lexer. They carry a semantic value. This type does not include the error pseudo-token.

type terminal

The type of terminal symbols. These can be thought of as integer codes. They do not carry a semantic value. This type does include the error pseudo-token.

type nonterminal

The type of nonterminal symbols.

type semantic_value

The type of semantic values.

val token2terminal : token -> terminal

A token is conceptually a pair of a (non-error) terminal symbol and a semantic value. The function token2terminal is the first the pair projection.

val token2value : token -> semantic_value

A token is conceptually a pair of a (non-error) terminal symbol and a semantic value. The function token2value is the second the pair projection.

val error_terminal : terminal

The terminal symbol associated with the error token.

val error_value : semantic_value

The semantic value associated with the error token.

val foreach_terminal : (terminal -> 'a -> 'a) -> 'a -> 'a

foreach_terminal iterates over all terminal symbols.

type production

The type of productions.

val production_index : production -> int

production_index maps a production to its integer index.

val find_production : int -> production

find_production maps a production index to a production. Its argument must be a valid index; use with care.

val default_reduction : state -> ('env -> production -> 'answer) -> ('env -> 'answer) -> 'env -> 'answer

If a state s has a default reduction on production prod, then, upon entering s, the automaton should reduce prod without consulting the lookahead token.

default_reduction s determines whether the state s has a default reduction. Instead of returning a value of a sum type -- say, either DefRed prod or NoDefRed -- it accepts two continuations, and invokes just one of them.

val action : state -> terminal -> semantic_value -> ('env -> bool -> terminal -> semantic_value -> state -> 'answer) -> ('env -> production -> 'answer) -> ('env -> 'answer) -> 'env -> 'answer

An LR automaton can normally take three kinds of actions: shift, reduce, or fail. (Acceptance is a particular case of reduction: it consists in reducing a start production.)

There are two variants of the shift action. shift/discard s instructs the automaton to discard the current token, request a new one from the lexer, and move to state s. shift/nodiscard s instructs it to move to state s without requesting a new token. This instruction should be used when s has a default reduction on #.

The function action provides access to the automaton's action table. It maps a pair of a state and a terminal symbol to an action.

Instead of returning a value of a sum type -- one of shift/discard, shift/nodiscard, reduce, or fail -- this function accepts three continuations, and invokes just one them.

The parameters of the function action are as follows:

  • the first two parameters, a state and a terminal symbol, are used to look up the action table;
  • the next parameter is the semantic value associated with the above terminal symbol; it is not used, only passed along to the shift continuation, as explained below;
  • the shift continuation expects an environment; a flag that tells whether to discard the current token; the terminal symbol that is being shifted; its semantic value; and the target state of the transition;
  • the reduce continuation expects an environment and a production;
  • the fail continuation expects an environment;
  • the last parameter is the environment; it is not used, only passed along to the selected continuation.
val maybe_shift_t : state -> terminal -> state option

maybe_shift_t s t determines whether there exists a transition out of the state s, labeled with the terminal symbol t, to some state s'. If so, it returns Some s'. Otherwise, it returns None.

val may_reduce_prod : state -> terminal -> production -> bool

may_reduce_prod s t prod determines whether in the state s, with lookahead symbol t, the automaton reduces production prod. This test accounts for the possible existence of a default reduction.

val goto_nt : state -> nonterminal -> state

The function goto_nt provides access to the automaton's goto table. It maps a pair of a state s and a nonterminal symbol nt to a state. The function call goto_nt s nt is permitted ONLY if the state s has an outgoing transition labeled nt. Otherwise, its result is undefined.

val goto_prod : state -> production -> state

The function goto_prod also provides access to the goto table. It maps a pair of a production prod and a state s to a state. The call goto_prod prod s is permitted ONLY if the state s has an outgoing transition labeled with the nonterminal symbol lhs prod.

val maybe_goto_nt : state -> nonterminal -> state option

The function maybe_goto_nt serves the same purpose as goto_nt. Compared to goto_nt, it involves an additional dynamic check, so it CAN be called even the state s has no outgoing transition labeled nt.

val lhs : production -> nonterminal

lhs prod returns the left-hand side of production prod, a nonterminal symbol.

val is_start : production -> bool

is_start prod tells whether the production prod is a start production.

exception Error

A semantic action can raise the exception Error.

By convention, a semantic action is responsible for:

1. fetching whatever semantic values and positions it needs off the stack;

2. popping an appropriate number of cells off the stack, as dictated by the length of the right-hand side of the production;

3. computing a new semantic value, as well as new start and end positions;

4. pushing a new stack cell, which contains the three values computed in step 3;

5. returning the new stack computed in steps 2 and 4.

val semantic_action : production -> semantic_action

The function semantic_action maps a production to its semantic action.

val may_reduce : state -> production -> bool

may_reduce state prod tests whether the state state is capable of reducing the production prod. This function is currently costly and is not used by the core LR engine. It is used in the implementation of certain functions, such as force_reduction, which allow the engine to be driven programmatically.

val log : bool

If the flag log is false, then the logging functions are not called. If it is true, then they are called.

module Log : EngineTypes.LOG with type state := state and type terminal := terminal and type production := production

The logging hooks required by the LR engine.