<p>The lexical grammar of Java has a special case for the <code>&gt;</code> character. Normally, tokens are formed based on the longest-match rule, so that an input string of <code>&gt;&gt;</code> or <code>&gt;&gt;&gt;</code> would form a single token for a bitshift operator. However, this would result in an incorrect parse for types like <code>List&lt;List&lt;String&gt;&gt;</code> where the two consecutive <code>&gt;</code> characters should be treated as separate tokens. According to the JLS (<a href="https://docs.oracle.com/javase/specs/jls/se19/html/jls-3.html#jls-3.5" rel="nofollow noreferrer">§3.5</a>):</p>
<blockquote>
<p>If the input character <code>&gt;</code> appears in a type context (§4.11), that is, as part of a <em>Type</em> or an <em>UnannType</em> in the syntactic grammar (§4.1, §8.3), it is always reduced to the numerical comparison operator <code>&gt;</code>, even when it could be combined with an adjacent <code>&gt;</code> character to form a different operator.</p>
</blockquote>
<p>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.</p>
<p>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, <strong>how is this special case implemented in real parsers</strong>?</p>
<p>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.</p>

<syntax><implementation><parsing><java><lexing>
How do lexers/parsers distinguish between nested generics and bitshifts?
CC BY-SA 4.0
2023-10-15T14:27:49.677Z
Iconically, C++ had the same issue that had to be resolved by the standard: https://stackoverflow.com/questions/29331315/double-closing-angle-brackets-generates-syntax-error so maybe C++ compilers can be the source of some answers for this
kouta-kun
CC BY-SA 4.0
2023-10-15T14:48:23.513Z
My guess is that the scanner makes the larger token and later the parser checks for >> and >>> in certain contexts and effectively breaks them into individual tokens (i.e. treats them like multiple tokens).
Erik Eidt
CC BY-SA 4.0
2023-10-16T19:57:27.940Z
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.
Glenn Willen
CC BY-SA 4.0
2023-10-16T20:12:49.853Z
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]>]>`.
dan04
CC BY-SA 4.0
2023-10-16T20:15:55.577Z
@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.
dan04
CC BY-SA 4.0
2023-10-16T23:33:43.900Z
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
Flydog57
CC BY-SA 4.0
2023-10-17T13:18:40.080Z
It's 21st century already, we should have stopped using separate lexers long ago. For something like PEG or GLR this is not an issue at all.
SK-logic
CC BY-SA 4.0
2024-04-04T13:39:51.040Z
Lexer modes probably solves this problem pretty cleanly, imo?
CoffeeTableEspresso
CC BY-SA 4.0
2024-04-04T14:02:48.600Z
@CoffeeTableEspresso Sounds like you should write an answer.
kaya3
CC BY-SA 4.0
2024-10-02T14:29:17.470Z
@Flydog57 see https://github.com/dotnet/roslyn/blob/main/src/Compilers/CSharp/Portable/Parser/LanguageParser.cs and search for `SyntaxKind.GreaterThanToken`, there are only 43 occurrences and many of them are relevant to this question.
Eric Lippert
CC BY-SA 4.0
2024-10-15T10:46:11.433Z
When I implemented C# parser I just got rid of '>>' token and added special check for sift operator.
talex
CC BY-SA 4.0
2024-10-15T10:48:43.987Z
I remember I had more problem with optional type. Does `X?` is start of conditional operator or local variable declaration?
talex
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-10-15T18:38:18.677Z
2023-10-15T18:38:18.677Z
feldentm
CC BY-SA 4.0
2023-10-17T16:48:39.757Z
Indeed. This is much the same as how a symbol table can be used to enable single-pass compilation in languages like C.
Karl Knechtel
<p>The usual way to handle this is to NOT recognize things like <code>&gt;&gt;</code> and <code>&gt;=</code> 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 <code>&gt; /* comment */ &gt;</code> is not recognized as a right shift.</p>
<p>The commonly used tool <a href="https://en.wikipedia.org/wiki/Lex_(software)" rel="nofollow noreferrer">lex</a> has a very useful &quot;following context&quot; pattern that can be used for this to recognize <code>&gt;</code> characters that are immediately followed by a <code>&gt;</code> or <code>=</code> and mark them specially for the parser by using a different token.  So your lex rules might have something like</p>
<pre><code>&quot;&gt;&quot;/[&gt;=]    return GRT1;  /* greater-than which can start a shift or greater-or-equal */
&quot;&gt;&quot;         return GRT2;  /* stand-alone greater-than */
</code></pre>
<p>Then in the parser, it can recognize a <code>GRT1 GRT2</code> (or <code>GRT1 GRT1</code>) pair as a right-shift operand in any rule where that is legal.  Rules for type parameter lists can end with either a <code>GRT1</code> or a <code>GRT2</code>.</p>

CC BY-SA 4.0
2024-10-03T03:03:46.323Z
2024-10-03T03:03:46.323Z
Chris Dodd
# How do lexers/parsers distinguish between nested generics and bitshifts?
Posted by: username_0 on 2023-10-15
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>` where the two consecutive `>` characters should be treated as separate tokens. According to the JLS ([§3.5](https://docs.oracle.com/javase/specs/jls/se19/html/jls-3.html#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.
**Tags:** syntax implementation parsing java lexing
> **Comments:**
> **username_1**: Iconically, C++ had the same issue that had to be resolved by the standard: https://stackoverflow.com/questions/29331315/double-closing-angle-brackets-generates-syntax-error so maybe C++ compilers can be the source of some answers for this  
> **username_2**: My guess is that the scanner makes the larger token and later the parser checks for >> and >>> in certain contexts and effectively breaks them into individual tokens (i.e. treats them like multiple tokens).  
> **username_3**: 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.  
> **username_4**: 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]>]>`.  
> **username_4**: @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.  
> **username_5**: 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  
> **username_6**: It's 21st century already, we should have stopped using separate lexers long ago. For something like PEG or GLR this is not an issue at all.  
> **username_7**: Lexer modes probably solves this problem pretty cleanly, imo?  
> **username_0**: @CoffeeTableEspresso Sounds like you should write an answer.  
> **username_8**: @Flydog57 see https://github.com/dotnet/roslyn/blob/main/src/Compilers/CSharp/Portable/Parser/LanguageParser.cs and search for `SyntaxKind.GreaterThanToken`, there are only 43 occurrences and many of them are relevant to this question.  
> **username_9**: When I implemented C# parser I just got rid of '>>' token and added special check for sift operator.  
> **username_9**: I remember I had more problem with optional type. Does `X?` is start of conditional operator or local variable declaration?  
---
## 2 answers
### Answer by username_10 on 2023-10-15. Score: 8
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.
> **Comments:**
> **username_11** (2023-10-17): Indeed. This is much the same as how a symbol table can be used to enable single-pass compilation in languages like C.  
---
### Answer by username_12 on 2024-10-03. Score: 1
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.
---
