Are there well-known algorithms for inferring the "return types" of parser rules?
Given the grammar and the accompanying action code, is there any standard solution for inferring what type each production should cast to (and thus what type of calling production should be expected from it)?
I mean an OO program and action code that uses something like C # var
syntax (but I'm not looking for something that is a C # spec).
This would be pretty easy if it weren't for function overloading and recursive grammars.
The problem arises in such cases:
Foo ::=
Bar Baz { return Fig(Bar, Baz); }
Foo Pit { return Pop(Foo, Pit); } // typeof(foo) = fn(typeof(Foo))
source to share
If you are writing code in a functional language, this is easy; standard output like Hindley-Milner works fine. Don't do this . In my EBNF parser generator (never released, but source code available upon request) that supports icons, c and standard ML, I actually implemented the idea you are asking about completing standard ML: all types have been inferred. The resulting grammars were nearly impossible to debug.
If you move the overload into the mix, the results are harder to debug . (It's true! It's simple! No better than impossible! More than infinite! Past my dream!) If you really want to try it yourself, you can code my code . (You don't, there is a reason I never released it.)
source to share
The return value of a grammar action is really no different from a local variable, so you can use C # type inference to do the job. See this document for an understanding of how C # type inference is done.
The standard way to do type inference is the Hindley-Milner algorithm , but this will not handle overloading of off-the-shelf.
Note that even parser generators for text input languages do not usually invoke grammar action types. For example ocamlyacc requires type annotations. The Happy parser generator for Haskell can infer types , but seems to hinder practice. This could indicate that grammars are hard to type, a bad idea, or both.
[UPDATE] Norman Ramsey, who has a bitter experience, pokes a lot.
source to share