[antlr-interest] Function Expressions

[John B. Brodie]

Greetings!

On Wed, 2011-05-04 at 12:27 -0400, Jeff Hair wrote:
> Hello all,
> 
> I have a simple C/JavaScript-style grammar for my interpreter project. Right
> now, functions can be called via identifier(), or identifier(param1,
> param2). This works fine for simple cases, but in my language functions are
> first-class objects. I'm in the process of redoing my identifier logic for
> properties, arrays, and function calls. I've gotten the first two working.
> 
> I'm trying to allow expressions to be callable as functions, so I can do
> stuff like createFunction()(), where createFunction would be a function that
> returns a function. Another example would be (1 + 1)(). Obviously that
> should throw an error, but it should be a permissible language construct.
> JavaScript allows this.
> 
> The func.g file in my gist is a pared down version of the language grammar,
> with only the relevant rules in it. Understandably, it fails with the
> following errors:
> 
> [java] error(210):  The following sets of rules are mutually left-recursive
> [boolNegation, unary, add, mult, relation, term, expression]
> [java] error(206): /home/user/955488/func.g:66:2: Alternative 1: after
> matching input such as IDENT '(' decision cannot predict what comes next due
> to recursion overflow to relation from expression
> [java] error(201): /home/user/955488/func.g:66:2: The following alternatives
> can never be matched: 2
> 
> https://gist.github.com/955488 demonstrates the issue. I've stripped out
> everything except the expression rules. The gist can be cloned as a git repo
> and then built via Ant + Ivy.
> 
> I understand why it's failing. There's a conflict between the IDENT
> expression and IDENT '(' ')' for function calls. What I'm trying to figure
> out is how to allow both identifiers and function calls. If I figure that
> out, it should give me the rest of what I need. Any help would be
> appreciated.
> 

I think that basically you want Application (I come from the lambda
calculus and function invocation is called Application therein) to be a
post-fix operator.

If you look at grammars for Java or C or other C-like languages you will
see (I believe) that indexing into an array and/or projecting a field
out of a tuple (record) and probably others-like-them are post-fix
operators.

So I would recommend the following (tested, but not using your
incomplete gist framework) --- replacing your term rule with:

//Expressions
primary
   : IDENT
   | '('! expression ')'!
   | INTEGER
   | DOUBLE
   | BOOLEAN
   ;

term
   : (primary -> primary) ( suffix[$term.tree] -> suffix )*
   ;

suffix [CommonTree term] :
   ( x='(' modifiers? ')' -> ^(APPLICATION[$x,"A"] {$term} modifiers?) )
 | ( x='[' modifiers  ']' -> ^(INDEXING[$x,"I"] {$term} modifiers) )
 | ( x='.' (p=IDENT|p=INTEGER) -> ^(PROJECTION[$x,"P"] {$term} $p) )
 ;

modifiers : expression (','! expression)* ;



with an appropriate tokens{} section defining  the APPLICATION;
INDEXING; and PROJECTION imaginary tokens.

the above is a little complicated in order to get the imaginary token
representing the suffix operator to be a tree root.

note that the stuff in the []'s after the imaginary token name is for
error reporting and/or tree pretty printing. keep the $x but change the
string to suite your need.

hope this helps
   -jbb