package zelus
Install
dune-project
Dependency
Authors
Maintainers
Sources
md5=437ae922f1fda392efca3e37e8b8bb4c
sha512=d591cdbeedb8f3a7f568d6d4994de572093822cb354b112886326219174311715a71a35de57a4c2070eae349f65f0c8f3d6c2f6a5a79a8187bbffc687cd108a6
doc/zelus.zlcompilerlibs/Zparser/Tables/index.html
Module Zparser.Tables
type token = tokenThe type of tokens.
val token2terminal : token -> inttoken2terminal maps a token to a terminal symbol, represented by its internal integer code.
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.