= Operator precedence
:toc:
:stem: latexmath

== A mechanism for operator precedence

We adapt a mechanism to provide a grammar with a specification for operator precedence, as described in the article [Safe Specification of Operator Precedence Rules](https://link.springer.com/chapter/10.1007%2F978-3-319-02654-1_8).

The theory is as follows:

* Each production may optionally have a **left** precedence, a **right** precedence, or both. A precedence is always represented by a non-negative number. +
Additionnaly, we define an **expression node** E associated with the precedence mechanism.

* Each production with a _left_ precedence should have the form 𝐴 → 𝐸𝛼, where 𝐸 →* 𝐴.
* Each production with a _right_ precedence should have the form 𝐵 → 𝛽𝐸, where 𝐸 →* 𝐵.
* Then if we have a production 𝐴 → 𝐸𝛼 with left precedence 𝑙, and 𝐵 → 𝛽𝐸 with right precedence 𝑟, there are two competing (left) derivation chains : 
+
--
. 𝐸 →* 𝑥𝐵 → 𝑥𝛽𝐸 →* 𝑥𝑣𝐸 →* 𝑥𝑣𝐴𝜂 → 𝑥𝑣𝐸𝛼𝜂 →* 𝑥𝑣𝐸𝛼𝜂
. 𝐸 →* 𝐴𝜂 → 𝐸𝛼𝜂 →* 𝑥𝐵𝛼𝜂 → 𝑥𝛽𝐸𝛼𝜂 →* 𝑥𝑣𝐸𝛼𝜂 →* 𝑥𝑣𝐸𝛼𝜂
--
+
Then
+
** If 𝑙 > 𝑟, the derivation chain (2) is forbidden.
** If 𝑙 < 𝑟, the derivation chain (1) is forbidden.

=== Safety

The original article affirms that this mechanism is _safe_. That is, any sentence that is accepted by the grammar _without precedence annotations_, is also accepted in the grammar with precedence annotations.

This can also resolve pretty complicated precedence cases. The example given is the grammar

[source]
--
E → E + E
E → if E
E → INT
--

In which the sentence `INT + if INT + INT` should be parsed as `INT + \((if (INT + INT))`. This is achieved by setting

* 𝑙 = 2, 𝑟 = 3 for `E → E + E`
* 𝑟 = 1 for `E → if E`

== In the parser generator

Assume we are computing the closure of a state 𝑠. In the usual LR(-) algorithm, each item 𝑋 → 𝛾•𝐴𝛿 generates any other item 𝐴 → •𝛼.

With precedence annotations however, some of those generations may be forbidden.

When generating the LR(0) table, we extend each item 𝑋 → 𝛾•𝛿 with annotations [ 𝑙, 𝑟 ], where 𝑙 = _ (resp. 𝑟 = _) if it contains no left (resp. right) annotations.

The rules for generating states for those items are then as follows :

1.  **(state equality)** Two states are equal (ignoring lookaheads) if they contain the same items, precedence annotations included.
2.  **(starting state)** If 𝑠₀ is the starting state for node 𝑆, then for any production 𝑆 → 𝜎, 𝑠₀ contains the item 𝑆 → 𝜎 [ _, _ ].
3.  **(transition)** If 𝑠 is a state containing some items 𝑋 → 𝜉₁𝑦•𝜉₂ [ 𝑙, 𝑟 ], then there exists a state 𝑠' obtained by following the symbol 𝑦 from 𝑠, such that 𝑠' contains all items 𝑋 → 𝜉₁𝑦•𝜉₂ [ 𝑙, 𝑟 ].
4.  **(closure)** Let 𝐴 → 𝛾𝐵𝛿 [ 𝑙, 𝑟 ]$ and 𝐵 → 𝛽 [ 𝑙', 𝑟' ] be two productions of the grammar. +
Let 𝑠 be a state containing the item 𝐴 → 𝑦∙𝐵𝛿 [ 𝑙'', 𝑟'' ]. +
Then if _all_ of the following is true :
+
--
..  If 𝑦 ⇒* 𝜀, 𝑟' ≠ _ and 𝑙 ≠ _, then 𝑙 ≤ r'.
..  If 𝑦 ⇒* 𝜀, 𝑙' ≠ _ and 𝑙'' ≠ _, then 𝑙'' ≤ 𝑙'.
..  If 𝛿 ⇒* 𝜀, 𝑙' ≠ _ and 𝑟 ≠ _, then 𝑟 ≤ 𝑙'.
..  If 𝛿 ⇒* 𝜀, 𝑟' ≠ _ and 𝑟'' ≠ _, then 𝑟'' ≤ 𝑟'.
--
+
Then 𝑠 contains an item 𝐵 → ∙𝛽 [ 𝐿, 𝑅 ], where 𝐿, 𝑅 are the smallest possible annotations (considering _ to be like -∞) such that
+
** If 𝑦 ⇒* 𝜀, 𝐿 ≥ 𝑙'' and 𝑅 ≥ 𝑙.
** If 𝛿 ⇒* 𝜀, 𝑅 ≥ 𝑟'' and 𝐿 ≥ 𝑟.

WARNING: This method does not requires that productions subscribe to the model described in the first part. Hupholding these garantees is left to the person writing the annotations.
