Next: SMIE Grammar, Previous: SMIE setup, Up: SMIE
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(
assoc op...)
, where each op is a token that acts as an operator; assoc is their associativity, which can be eitherleft
,right
,assoc
, ornonassoc
. 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), acloser
(like a close-paren), orneither
of the two (e.g., an infix operator, or an inner token like"else"
).Precedence conflicts can be resolved via resolvers, which is a list of precs tables (see
smie-precs->prec2
): for each precedence conflict, if thoseprecs
tables 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.