Are there well known algorithms for deducing the "return types" of parser rules?

Question

Given a grammar and the attached action code, are there any standard solution for deducing what type each production needs to result in (and consequently, what type the invoking production should expect to get from it)?

I'm thinking of an OO program and action code that employs something like c#'s var syntax (but I'm not looking for something that is c# specific).

This would be fairly simple if it were not for function overloading and recursive grammars.

The issue arises with cases like this:

Foo ::= 
    Bar Baz { return Fig(Bar, Baz); }
    Foo Pit { return Pop(Foo, Pit); } // typeof(foo) = fn(typeof(Foo))

Answer 1

If you are writing code in a functional language it is easy; standard Hindley-Milner type inference works great. Do not do this. In my EBNF parser generator (never released but source code available on request), which supports Icon, c, and Standard ML, I actually implemented the idea you are asking about for the Standard ML back end: all the types were inferred. The resulting grammars were nearly impossible to debug.

If you throw overloading into the mix, the results are only going to be harder to debug. (That's right! This just in! Harder than impossible! Greater than infinity! Past my bedtime!) If you really want to try it yourself you're welcome to my code. (You don't; there's a reason I never released it.)

Answer 2

The return value of a grammar action is really no different from a local variable, so you should be able to use C# type inference to do the job. See this paper for some insight into how C# type inference is implemented.

The standard way of doing type inference is the Hindley-Milner algorithm, but that will not handle overloading out-of-the-box.

Note that even parser generators for type-inferencing languages don't typically infer the types of grammar actions. For example, ocamlyacc requires type annotations. The Happy parser generator for Haskell can infer types, but seems to discourage the practice. This might indicate that inferring types in grammars is difficult, a bad idea, or both.

[UPDATE] Very much pwned by Norman Ramsey, who has the benefit of bitter experience.