package ocamlformat-mlx-lib
Install
dune-project
Dependency
Authors
Maintainers
Sources
sha256=af4e7ed7e84bd681e1058c3573e255427aa3c3a9952c115f1c2441295766d14c
sha512=48a153ad33283a95b3d5a54cd04e8a26feb5d394b291a45aa01f77e376bcfc94a2b6350b3f3611a3d2511f25b0f69f6d2d694d7ace81004ed7e6850ac6947b4c
doc/ocamlformat-mlx-lib.parser_extended/Ocamlformat_parser_extended/Parser/Tables/index.html
Module Parser.TablesSource
terminal_count is the number of terminal symbols, without #.
token2terminal maps a token to a terminal symbol, represented by its internal integer code.
error_terminal is the integer code of the special token error.
Traditionally, an LR automaton is described by two tables, namely, an action table and a goto table. See, for instance, the Dragon book.
The action table is a two-dimensional matrix that maps a state and a lookahead token to an action. An action is one of: shift to a certain state, reduce a certain production, accept, or fail.
The goto table is a two-dimensional matrix that maps a state and a non-terminal symbol to either a state or undefined. By construction, this table is sparse: its undefined entries are never looked up. A compression technique is free to overlap them with other entries.
In Menhir, things are slightly different. If a state has a default reduction on token #, then that reduction must be performed without consulting the lookahead token. As a result, we must first determine whether that is the case, before we can obtain a lookahead token and use it as an index in the action table.
Thus, Menhir's tables are as follows.
The default reduction table, a one-dimensional table, maps a state to either ``no default reduction'' (encoded as: 0) or ``by default, reduce prod'' (encoded as: 1 + prod). The action table is looked up only when there is no default reduction.
Menhir follows Dencker, Dürre and Heuft, who point out that, although the action table is not sparse by nature (i.e., the error entries are significant), it can be made sparse by first factoring out a binary error matrix, then replacing the error entries in the action table with undefined entries. Thus:
The error bitmap, a two-dimensional table, maps a state and a terminal symbol to either "fail" (encoded as: 0) or "do not fail" (encoded as: 1). The action table is looked up only in the latter case.
The function error offers read access to the error bitmap.
The error bitmap does not contain a column for the # pseudo-terminal. Thus, its width is terminal_count.
The action table, a two-dimensional table, maps a state and a terminal to one of ``shift to state s and discard the current token'' (encoded as: s | 10), ``shift to state s without discarding the current token'' (encoded as: es | 11), or ``reduce prod'' (encoded as: prod | 01).
Like the error bitmap, the action table does not contain a column for the # pseudo-terminal.
A one-dimensional table, lhs, maps a production to its left-hand side (a non-terminal symbol).
The goto table, a two-dimensional table, maps a state and a non-terminal symbol to either undefined (encoded as: 0) or a new state s (encoded as: 1 + s)..
start is the number of start productions. A production prod is a start production if and only if prod < start holds. This is also the number of start symbols. A nonterminal symbol nt is a start symbol if and only if nt < start holds.
val semantic_action :
((int, Obj.t, token) MenhirLib.EngineTypes.env ->
(int, Obj.t) MenhirLib.EngineTypes.stack)
arrayThe semantic action table, a one-dimensional table, maps productions to semantic actions. The calling convention for semantic actions is described in EngineTypes. This table contains ONLY NON-START PRODUCTIONS, so the indexing is off by start. Be careful.
The exception Error can be raised by semantic actions, caught by the engine, and raised again by the engine for the final user to observe.
trace indicates whether a trace should be generated. Generating a trace requires two extra tables, which respectively map a terminal symbol and a production to a string.