CODEWITHSUNDEEP
antlrantlr4
Knightz
Knightz

Reputation: 49

How to write Haskell-style function application in Antlr

I'm trying to write a Haskell-style language parser in ANTLR4, but I'm having some issues with function application. It parses as right associative rather than left associative

expression :
      unit #UnitExpression
    | IntegerLiteral #IntExpression
    | FloatLiteral #FloatExpression
    | CharLiteral #CharExpression
    | StringLiteral #StringExpression
    | LSquareParen (expression (Comma expression)*)? RSquareParen #ListExpression
    | LParen expression RParen #ParenExpression
    | LParen (expression (Comma expression)+) RParen #TupleExpression
    | expression operatorIdentifier expression #OperatorApplicationExpression
    | expression (expression)+ #FunctionApplicationExpression
    | variableIdentifier # VariableExpression
;

This is the relevant part of the grammar , the issue is that when I write something like f a b it parses as f (a b) rather than (f a) b

The actual example I was using was f "a" "b", which seemed even more confusing since String literals have higher precedence than function application.

I also tried rewriting to expression+ expression which didn't work because it's mutually left recursive apparently

How can I make this work?

Upvotes: 1

Views: 166

Answers (1)

Mike Cargal
Mike Cargal

Reputation: 6785

As @sepp2k pointed out, | expression expression will correct your issue.

ANTLR defaults to left associativity., but you were overriding that with the (expression)+ in trying to gather all the expressions.

Of course, this will give you a parse tree of (expr (expr (expr f) (expr "a")) (expr "b"))

enter image description here

but this is probably more in keeping with a Haskell approach to function application than just a list of expressions.

BTW, precedence only comes into play when operators are involved. Having StringLiteral before LSquareParen his no effect on precedence since there's no ambiguity in determining the correct parse tree to derive. You may find that your OperatorApplicationExpresion alternative gives "surprising" results as it will evaluate all operators left-to-right, so a + b * c will be evaluated as "(a + b) * c" and this violates arithmetic norms (maybe it's what you want however).

Upvotes: 2

Related Questions