Distinguishing between type aliases and variable names in templates

[luan-xiaokun]

Problem to be solved

C++ style template is supported in my language, the problem is that the template argument can be either a type or an expression, but parse rules for type and expression overlap, i.e. for an identifier we cannot know it is a type alias or a variable / function name, unless we have some semantic information. Currently, writing something like ('<' templates+=(Type | Expression) '>')? raises error about their common prefix ID.

Existing approaches

Such problem can be solved by the lexer hack method, which requires a context-free lexer, information from the semantic table is fed back to the lexer, but I don't think this is a proper solution for Langium since this approach may require hacking Chevrotain if I understand it correctly.

A second approach mentioned in the wiki is to allow multiple attempts to parse the tokens, and when the parser fails it backtracks to try the alternative rules. I'm not sure if this method is applicable to Langium, any comments on this approach are welcome.

The last method does not differentiate between type names and variable names at the parsing time, whether the identifier is a type or an expression is determined by the semantic analysis that follows, and this approach is adopted by Clang. As far as I can understand, I think this approach suites the Langium framework the best, but it requries creating a new set of parse rules to mix expressions and types, and these rules are only used in the template related parse rules. I haven't tried it because I'm still figuring how to write such rules.

The question

Which solution do you think is the most appropriate in the Langium framework? Or is there a better solution?

[msujew]

Hey @luan-xiaokun,

The last method does not differentiate between type names and variable names at the parsing time, whether the identifier is a type or an expression is determined by the semantic analysis that follows, and this approach is adopted by Clang. As far as I can understand, I think this approach suites the Langium framework the best, but it requries creating a new set of parse rules to mix expressions and types, and these rules are only used in the template related parse rules.

I believe so as well. While we recently added support for custom lexers (#721), I'm worried that the lexer hack won't turn out as expected. The Clang approach is definitely the one that is best suited for Langium, and the implementation is fairly straightforward (although verbose).

I imagine your type syntax and expression syntax to use something like this for referencing:

Type: ... | TypeRef;
TypeRef: value=[TypeDefinition:ID];
Expression: ... | VarRef;
VarRef: value=[VarDefinition:ID];

Given that Langium informs you of the common ID prefix, this would make sense. For a new TypeOrExpression syntax you could use extend your exisisting syntax similar to this:

TypeOrExpression: ... | TypeOrVarRef;
TypeOrVarRef: value=[TypeOrVar:ID];
// We create a special type that allows us to reference both types
type TypeOrVar = TypeDefinition | VarDefinition;

This basically moves TypeDefinition and VarDefinition in the same scope, allowing to parse a single ID for references to both types.

[luan-xiaokun]

Thanks for your reply, and glad to here that I'm on the right track.

and the implementation is fairly straightforward (although verbose)

Yes, it is verbose, and a little more complex than I expected. Basically, this is because my definition for type looks like

Type: (... ('(' Type (',' Type)* ')') | TypeRef) (something for list type)* (something for union type)*;

so the merging process will be a bit more complicated. Currently, I'm trying to replace TupleType | TypeRef with Expression. I hope that I can rule out invalid combinations such as expr | int at the type checking or validation phase. If I can finally make it, I'm willing to share it in this discussion.