How do parsers handle generic type parameters?

user_3968575 0
Viewed 424

I'm writing a recursive decent parser for an imaginary programming language. It's a C-style language with common operators like ==, <, >, <=, and >=, and it also features generic functions (like those in C#).

In languages like C#, to call a generic function, you write:

someFunction<T>(x);

My question is, how does the parser differentiate the generic parameters from comparison operators (< and >).

From my perspective, the code above could have either of these two meanings:

  • call 'someFunction' with a generic parameter 'T', and with a regular parameter 'x'
  • evaluate the expression '(someFunction < T) > x', treating 'someFunction', 'T', and 'x' as regular variables

How would the parser know which interpretation is intended?

programming-languages recursive-descent parsing generics c#
1 Answers

You're 100% correct that the generic function call syntax is ambiguous in many languages which include the feature.

Not all languages use an ambiguous syntax. In Java, there is no ambiguity because the type arguments are placed before the method name, and must be preceded by a .: SomeClass.<ArgType>genericMethod(). Other possibilities include using a different symbol for type brackets, such as [], ::<> or !. (Scala, Rust and D respectively. Scala uses parentheses for array subscripts.)

But many languages do use the C++/C# syntax, which is ambiguous. Every language has its own disambiguation rule, and as far as I know there is no cross-language consensus on how to do it. In particular:

  • C++ requires the compiler to figure out whether the function/method/class name is (or might be) templated. (ADL makes this a bit tricky, and in C++18 the rules changed to include a case where a non-templated function/method name might still be interpreted as though it were templated.)

  • C# requires the compiler to find the end of the angle-bracketed template arguments, if possible, and then examine the next input token; if the next token is an open parenthesis or one of a set of tokens which can not syntactically follow a > (for example, a semicolon), then the template arguments are handled as such; if there is no matching > or the matching > is followed by something like 42, then it is handled as a comparison.

As far as I can see, a recursive descent parser which used the C# definition would need to be able to backtrack. The C++ definition, on the other hand, requires that name resolution be interwoven into syntax analysis, which is a different ugliness.

You are, as far as I can see, free to come up with your own different solution. I do encourage you to fully and clearly document it if you expect other people to use your language. (I couldn't find such documentation for typescript, for example, which I don't use.) If I were designing a language with generics, I think I'd go for an unambiguous syntax. But that's just me.

user_15662210
Related