How to write Haskell-style function application in Antlr

user_6272977 0
Viewed 78

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?

antlr4 antlr
1 Answers

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

user_737640
Related