CODEWITHSUNDEEP
antlrantlr4lambda-calculus
Nick Rioux
Nick Rioux

Reputation: 982

Antlr4 Grammar for Function Application

I'm trying to write a simple lambda calculus grammar (show below). The issue I am having is that function application seems to be treated as right associative instead of left associative e.g. "f 1 2" is parsed as (f (1 2)) instead of ((f 1) 2). ANTLR has an assoc option for tokens, but I don't see how that helps here since there is no operator for function application. Does anyone see a solution?

LAMBDA : '\\';
DOT : '.';
OPEN_PAREN : '(';
CLOSE_PAREN : ')';
fragment ID_START : [A-Za-z+\-*/_];
fragment ID_BODY : ID_START | DIGIT;
fragment DIGIT : [0-9];
ID : ID_START ID_BODY*;
NUMBER : DIGIT+ (DOT DIGIT+)?;
WS : [ \t\r\n]+ -> skip;

parse : expr EOF;

expr : variable                     #VariableExpr
     | number                       #ConstantExpr
     | function_def                 #FunctionDefinition
     | expr expr                    #FunctionApplication
     | OPEN_PAREN expr CLOSE_PAREN  #ParenExpr
;
function_def : LAMBDA ID DOT expr;
number : NUMBER; 
variable : ID;

Thanks!

Upvotes: 2

Views: 973

Answers (1)

Terence Parr
Terence Parr

Reputation: 5962

this breaks 4.1's pattern matcher for left-recursion. cleaned up in main branch I believe. try downloading last master and build. CUrrently 4.1 generates:

expr[int _p] : ( {} variable | number | function_def | OPEN_PAREN expr CLOSE_PAREN ) ( {2 >= $_p}? expr )* ;

for that rule. expr ref in loop is expr[0] actually, which isn't right.

Upvotes: 2

Related Questions