17
$\begingroup$

The lexical grammar of Java has a special case for the 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, 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.

$\endgroup$
9
  • 6
    $\begingroup$ Iconically, C++ had the same issue that had to be resolved by the standard: stackoverflow.com/questions/29331315/… so maybe C++ compilers can be the source of some answers for this $\endgroup$
    – kouta-kun
    Oct 15, 2023 at 14:27
  • 3
    $\begingroup$ Frankly, this part of the grammar is a disaster, and if you can do it in a way that's not syntactically ambiguous you'll probably be happier. $\endgroup$ Oct 16, 2023 at 19:57
  • 2
    $\begingroup$ Yeah, if you're developing a new language, you might want to consider a different syntax for parameterized types, like List[List[String]] or List<[List<[String]>]>. $\endgroup$
    – dan04
    Oct 16, 2023 at 20:12
  • 5
    $\begingroup$ @kouta-kun: I've heard that when this issue was discussed at the C++11 ISO meetings, all the major compiler vendors admitted to special-casing >> after a template type in order to give sensible error messages. So Bjarne suggested a simple way to implement the new syntax: Just remove the error. $\endgroup$
    – dan04
    Oct 16, 2023 at 20:15
  • 1
    $\begingroup$ The Roslyn parser for C# (the current parser) is open source. It would be easy to look up. I remember when generics for C# were introduced (in C# 2.0, in 2005), the language folks made a big thing out of the fact that they didn't have the restrictions that C++ had at the time $\endgroup$
    – Flydog57
    Oct 16, 2023 at 23:33

2 Answers 2

7
$\begingroup$

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
  }
.
$\endgroup$
1
  • $\begingroup$ Unary AddExpr on the right hand side looks odd, I think it's because later on there is MulExpr = {("*" | "/" | "%") Unary}. (so the AddExpr is either empty, or starts with a binop). So it seems like it'll work, but I couldn't think of a reason for why it would be done that way, and none of my LL(1) grammars work that way. $\endgroup$
    – user1030
    Oct 15, 2023 at 15:13
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Indeed. This is much the same as how a symbol table can be used to enable single-pass compilation in languages like C. $\endgroup$ Oct 17, 2023 at 16:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .