= 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.