How do lexers/parsers distinguish between nested generics and bitshifts?

Question

The lexical grammar of Java has a special case for the > character. Normally, tokens are formed based on the longest-match rule, so that an input string of >> or >>> would form a single token for a bitshift operator. However, this would result in an incorrect parse for types like List<List<String>> where the two consecutive > characters should be treated as separate tokens. According to the JLS (§3.5):

If the input character > appears in a type context (§4.11), that is, as part of a Type or an UnannType in the syntactic grammar (§4.1, §8.3), it is always reduced to the numerical comparison operator >, even when it could be combined with an adjacent > character to form a different operator.

Read literally, this means the lexer would need to know the grammatical context in order to decide which tokens to emit; but this context is normally not determined until parsing, i.e. after lexing is complete.

Of course, the specification only defines the rules for what source texts form valid Java programs and what those programs mean; a Java compiler could implement the spec in various different ways. But this kind of special case seems difficult to handle without hand-crafting an ad-hoc solution, whereas hand-crafted hacks presumably aren't applicable when using parser generators or other frameworks based on formal grammars. So, how is this special case implemented in real parsers?

While this question is written about Java, the same ambiguity could occur in other languages which share Java's generic syntax, so answers about parsers for other languages are also welcome.

Answer 1

In the Coco/R example parser for C# 2.0 (not Java, but the same issue is encountered), >> is not a token. Coco/R is an LL(1) parser, but various non-LL(1) constructs can be parsed using semantic predicates. That is for example also how the age old "generics vs less-than"-problem is solved in that grammar (and also in C# specification itself for that matter).

Making >> not a token is enough to fix the "nested generics problem", though it creates some minor inconvenience for parsing the right-shift operator, which is parsed as two > tokens with a semantic predicate to ensure that that production is only used for two directly-adjacent > (not two > separated by some whitespace):

bool IsShift() {
  Token pt = Peek(1);
  return (la.kind == _ltlt) ||
         ( la.kind == _gt &&
           pt.kind == _gt &&
           (la.pos + la.val.Length == pt.pos)
         );
}

ShiftExpr
= AddExpr
  { IF (IsShift())
    ("<<" | ">" ">") Unary AddExpr
  }
.

Answer 2

There is actually no reason to assume that a file is tokenized until the end before parsing begins. There are frameworks allowing you to generate parsers and tokenizers that use tokens streams that will only tokenize the lookahead. Usually, there is some sort of channel concept that can be used to let the parser or the lexer itself switch the entire set of tokenization rules, i.e. use a different automaton.

The reference to parser combinators is particularly interesting as it is very easy to get right there as long as you don't do backtrack over the switching points and have a token stream that shares position and does itself not backtrack.

Answer 3

The usual way to handle this is to NOT recognize things like >> and >= as single tokens in the lexer and instead defer combining them until the parser. This requires a little bit of extra work to ensure that something like > /* comment */ > is not recognized as a right shift.

The commonly used tool lex has a very useful "following context" pattern that can be used for this to recognize > characters that are immediately followed by a > or = and mark them specially for the parser by using a different token. So your lex rules might have something like

">"/[>=]    return GRT1;  /* greater-than which can start a shift or greater-or-equal */
">"         return GRT2;  /* stand-alone greater-than */

Then in the parser, it can recognize a GRT1 GRT2 (or GRT1 GRT1) pair as a right-shift operand in any rule where that is legal. Rules for type parameter lists can end with either a GRT1 or a GRT2.