13

Are there any programming (or scripting) language (or some domain specific language) having two binary operators opl and opr of same precedence with opl being left-associative and opr being right-associative?

(I cannot find such an example, but I am trying to code some parser general enough to handle that weird case)

How would expressions of the form x opl y opr z or x opr y opl z be parsed? And more generally with even more operands?

5
  • 4
    If it hurts, don't do that. Feb 22, 2016 at 9:09
  • 1
    In Haskell, you can define your own infix operators with their own precedences, and you get an error in this case; if you have x <@ y @> z with <@ being left-associative and @> being right-associative, GHC gives you a "Precedence parsing error": "cannot mix ‘<@’ [infixl 0] and ‘@>’ [infixr 0] in the same infix expression" (where I defined these operators at level 0 for the example). Feb 22, 2016 at 9:37
  • @AntalSpector-Zabusky: That would be a great answer! Feb 22, 2016 at 9:38
  • @AntalSpector-Zabusky: Same in Swift. I think you can actually define the operators, but in an expression you must use all left associative or all right associative operators with the same precedence. So you can use x leftop y leftop z, or x rightop y rightop z, but not x leftop y rightop z.
    – gnasher729
    Feb 22, 2016 at 9:52
  • @BasileStarynkevitch: As you wish! Since you mentioned "flexible parsers", I included a couple of more obscure languages that have very flexible parsers (ever wanted if_then_else_ or [1;2;3] to be defined in libraries?). Feb 22, 2016 at 10:47

2 Answers 2

11

Here are three languages that let you define your own operators, which do two and a half different things! Haskell and Coq both disallow these sorts of shenanigans – but differently – while Agda allows this sort of mixing of associativities.


First, in Haskell, you simply aren't allowed to do this. You can define your own operators and give them the precedence (from 0–9) and associativity of your choice. However, the Haskell Report disallows you from mixing associativities:

Consecutive unparenthesized operators with the same precedence must both be either left or right associative to avoid a syntax error. [Haskell 2010 Report, Ch. 3]

So, in GHC, if we define a left-associative (infixl) operator <@ and right-associative operator @> at the same precedence level – let's say 0 – then evaluating x <@ y @> z gives the error

Precedence parsing error
    cannot mix ‘<@’ [infixl 0] and ‘@>’ [infixr 0] in the same infix expression

(In fact, you can also declare an operator to be infix but non-associative, like ==, so that x == y == z is a syntax error!)


On the other hand, there's the dependently-typed language/theorem prover Agda (which, admittedly, is considerably less mainstream). Agda has some of the most malleable syntax of any language I know, supporting mixfix operators: the standard library contains the function

if_then_else_ : ∀ {a} {A : Set a} → Bool → A → A → A

which, when called, is written

if b then t else f

with the arguments filling in the underscores! I mention this because this means that it has to support incredibly flexible parsing. Naturally, Agda also has fixity declarations (although its precedence levels range over arbitrary natural numbers, and are typically in 0–100), and Agda does permit you to mix operators of the same precedence but different fixities. I can't, however, find information about this in the documentation, so I had to experiment.

Let's reuse our <@ and @> from above. In the two simple cases, we have

  • x <@ y @> z parsing as x <@ (y @> z); and
  • x @> y <@ z parsing as (x @> y) <@ z.

I think what Agda does is group the line into "left associative" and "right associative" chunks, and – unless I'm thinking about things wrong – the right-associative chunk gets "priority" in grabbing the adjacent arguments. So that gives us

a <@ b <@ c @> d @> e @> f <@ g

parsing as

(((a <@ b) <@ (c @> (d @> (e @> f)))) <@ g

or

Parse tree of <code>(((a <@ b) <@ (c @> (d</code> @> (e @> f)))) <@ g

However, despite my experiments, I guessed wrong the first time I wrote that out, which might be instructive :-)

(And Agda, like Haskell, has non-associative operators, which correctly give parse errors, so it would be possible for mixed associativities to result in a parse error too.)


Finally, there's the theorem-prover/dependently-typed language Coq, which has even more flexible syntax than Agda because its syntax extensions are actually implemented by giving specifications for the new syntactic constructs and then rewriting them into the core language (vaguely macro-like, I suppose). In Coq, the list syntax [1; 2; 3] is an optional import from the standard library. New syntaxes can even bind variables!

Once again, in Coq, we can define our own infix operators and give them precedence levels (from 0–99, mostly) and associativities. However, in Coq, each precedence level can only have one associativity. So if we define <@ as left-associative and then try to define @> as right-associative at the same level – say, 50 – we get

Error: Level 50 is already declared left associative while it is now expected to be right associative

Most operators in Coq are on levels that are divisible by 10; if I've had associativity issues (these level associativities are global), I've generally just bumped the level by one in either direction (usually up).

6
  • 2
    (Gee, what an odd selection of languages. Can you tell I study programming language theory? :-P) Feb 22, 2016 at 10:45
  • Thanks a big lot for your detailed answer. BTW, how did you draw the picture (with what tool? graphviz?) Feb 22, 2016 at 11:03
  • BTW, why "fixity" instead of "precedence"? Feb 22, 2016 at 11:10
  • @BasileStarynkevitch: That depends on where you mean. If you mean in the Coq section, that was just a mistake :-) (And one that's now fixed!) Feb 22, 2016 at 11:15
  • 1
    @BasileStarynkevitch: Also, I missed your question about the picture! I drew that with the LaTeX package qtree, and rendered it in LaTeXit, a LaTeX snippet renderer for Macs. The relevant source code was \ttfamily \Tree[.<@ [.<@ [.<@ a b ] [.@> c [.@> d [.@> e f ]]]] g ]. Mar 8, 2016 at 21:04
2

Since they were popularised by Douglas Crockford, Pratt Parsers (or Top-Down Operator Precedence parsers) have started to become more common. These parsers work from a table of operator precedence and associativity, rather than having the rules built into a fixed grammar, so they're helpful for languages that allow users to define their own operators.

They having a parse function that works by first parsing the leftmost term of an expression, then recursively binding new operators and right hand terms as long as they bind appropriately. Left-associative operators will bind right hand terms that have precedence up to and including the same precedence, while right-associative operators only bind up to their precedence level, but not including it. I believe this results in the same parse tree as for Agda, quoted above.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.