SMIE's precedence grammars simply give to each token a pair of
precedences: the left-precedence and the right-precedence. We say
T1 < T2 if the right-precedence of token
T1 is less than
the left-precedence of token
T2. A good way to read this
< is as a kind of parenthesis: if we find
... T1 something
T2 ... then that should be parsed as
... T1 (something T2 ...
rather than as
... T1 something) T2 .... The latter
interpretation would be the case if we had
T1 > T2. If we have
T1 = T2, it means that token T2 follows token T1 in the same
syntactic construction, so typically we have
"begin" = "end".
Such pairs of precedences are sufficient to express left-associativity
or right-associativity of infix operators, nesting of tokens like
parentheses and many other cases.
This function takes a prec2 grammar table and returns an alist suitable for use in
smie-setup. The prec2 table is itself meant to be built by one of the functions below.
This function takes several prec2 tables and merges them into a new prec2 table.
This function builds a prec2 table from a table of precedences precs. precs should be a list, sorted by precedence (for example
"+"will come before
"*"), of elements of the form
...), where each op is a token that acts as an operator; assoc is their associativity, which can be either
nonassoc. All operators in a given element share the same precedence level and associativity.
This function lets you specify the grammar using a BNF notation. It accepts a bnf description of the grammar along with a set of conflict resolution rules resolvers, and returns a prec2 table.
bnf is a list of nonterminal definitions of the form
(nonterm rhs1 rhs2
...)where each rhs is a (non-empty) list of terminals (aka tokens) or non-terminals.
Not all grammars are accepted:
- An rhs cannot be an empty list (an empty list is never needed, since SMIE allows all non-terminals to match the empty string anyway).
- An rhs cannot have 2 consecutive non-terminals: each pair of non-terminals needs to be separated by a terminal (aka token). This is a fundamental limitation of operator precedence grammars.
Additionally, conflicts can occur:
- The returned prec2 table holds constraints between pairs of tokens, and for any given pair only one constraint can be present: T1 < T2, T1 = T2, or T1 > T2.
- A token can be an
opener(something similar to an open-paren), a
closer(like a close-paren), or
neitherof the two (e.g., an infix operator, or an inner token like
Precedence conflicts can be resolved via resolvers, which is a list of precs tables (see
smie-precs->prec2): for each precedence conflict, if those
precstables specify a particular constraint, then the conflict is resolved by using this constraint instead, else a conflict is reported and one of the conflicting constraints is picked arbitrarily and the others are simply ignored.