### Author:  [@osa1](https://discuss.ocaml.org/u/osa1)
#### Post date: [January 21, 2025, 1:17pm UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/1 "2025-01-21T13:17:33Z")
A common parsing problem in languages that use angle brackets for generics is that you can’t tokenize “\>\>” as the right shift operator as in type context it would need to be parsed as two closing angle brackets.
However when you tokenize “\>\>” as two angle brackets, in expression context, when matching two "\>"s to parse a right shift operator, you have to make sure the two "\>"s are next to each other so that you parse `x >> y` as expected without also parsing `x > > y` as a right shift.
I’m looking at existing LR(1)/LALR(1) parser generators to see if/how they handle this and I’m wondering if Menhir has a solution to this problem.
So far the only solution that I’m aware of that can be used in LR(1) and LALR(1) parser generators is that the parser can pass a set of expected token types to the lexer.
(I think this only works when you don’t have any LR(1) states that (1) expect both “\>\>” and “\>” (2) can reduce to a type or expression, which probably holds for most grammars)
However I’m not aware of any parser generators that actually do this. tree-sitter does this, but it’s not LR(1).
I’m curious if Menhir allows this. If not, how would I handle this case in Menhir?
---
### Author:  [@WardBrian](https://discuss.ocaml.org/u/WardBrian)
#### Post date: [January 21, 2025, 9:35pm UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/2 "2025-01-21T21:35:21Z")
> [@osa1](#):
>
> I’m curious if Menhir allows this
If by “this”, you mean
> [@osa1](#):
>
> the parser can pass a set of expected token types to the lexer.
Then I believe this is the kind of thing you could do using the [“incremental” API menhir provides](https://gallium.inria.fr/~fpottier/menhir/manual.html#sec59)
* * *
Alternatively, I think you could implement
> [@osa1](#):
>
> you have to make sure the two "\>"s are next to each other so that you parse `x >> y` as expected without also parsing `x > > y` as a right shift.
using `$startpos`
E.g. your parse rule for x \>\> y could look like
```auto
rshift_expr:
| e1=expr RABRACK RABRACK e2=expr
{
let p1 = $startpos($2) in
let p2 = $startpos($3) in
if p1.pos_cnum + 1 <> p2.pos_cnum then raise ...
}
```
---
### Author:  [@Chimrod](https://discuss.ocaml.org/u/Chimrod)
#### Post date: [January 22, 2025, 8:15am UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/3 "2025-01-22T08:15:39Z")
I think this should managed in the lexer, not in the parser. You should have two distinct tokens for `>>` and `>` and the rules in menhir would only describe how thoses token compose together.
OCamllex use the rule of the longest match by default, and will be able do identify the two constructions without any effort:
> If several regular expressions match a prefix of the input, the “longest match” rule applies: the regular expression that matches the longest prefix of the input is selected. In case of tie, the regular expression that occurs earlier in the rule is selected.
---
### Author:  [@osa1](https://discuss.ocaml.org/u/osa1)
#### Post date: [January 22, 2025, 8:32am UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/4 "2025-01-22T08:32:03Z")
You can’t handle this in the lexer without extra information from the parser (such as a set of expected tokens passed by the parser to the lexer) as the lexer has no way of knowing whether two "\>"s need to be combined as one token or not.
Longest match rule will always combine, which is not the right lexing in type context when you have `T1>`.
---
### Author:  [@silene](https://discuss.ocaml.org/u/silene)
#### Post date: [January 22, 2025, 10:28am UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/5 "2025-01-22T10:28:24Z")
> So far the only solution that I’m aware of that can be used in LR(1) and LALR(1) parser generators is that the parser can pass a set of expected token types to the lexer.
There is a different solution, which is not that uncommon. Instead of having a token for `>>`, you have a token for `>` when it is immediately followed by some other `>`. Let us call `RANGLE` the normal `>` token, and `RRANGLE` when it is followed. In other words, the `>>` operator produces the sequence of tokens `RRANGLE RANGLE`. Then, the rule for expressions is
```plaintext
expr ::= expr RRANGLE RANGLE expr
```
while the rule for types is
```plaintext
type ::= ident LANGLE type (RANGLE | RRANGLE)
```
Notice how the grammar is properly LR(1).
---
### Author:  [@osa1](https://discuss.ocaml.org/u/osa1)
#### Post date: [January 22, 2025, 11:23am UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/6 "2025-01-22T11:23:52Z")
As I explain in my original post, generating two tokens instead of one does not solve the issue by itself. The parser then needs to distinguish two `RANGLE`s next to each other from two `RANGLE`s with whitespace in between, to be able to parse `x >> y` as expected without also parsing `x > > y` as a right shift.
My question was whether Menhir allows checking whitespace between two tokens. If not, what would be the way in Menhir to handle this.
---
### Author:  [@silene](https://discuss.ocaml.org/u/silene)
#### Post date: [January 22, 2025, 12:39pm UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/7 "2025-01-22T12:39:37Z")
You did not understand the solution I proposed. The input `>>` is tokenized as `RRANGLE RANGLE`, while the input `> >` is tokenized as `RANGLE RANGLE`. Notice how the first token of both sequences is different.
---
### Author:  [@osa1](https://discuss.ocaml.org/u/osa1)
#### Post date: [January 22, 2025, 1:31pm UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/8 "2025-01-22T13:31:50Z")
Ah, that makes sense, thanks.
I’m curious if there are open source parsers (using Menhir or another L(AL)R) that use this approach that I can have a look?
---
### Author:  [@WardBrian](https://discuss.ocaml.org/u/WardBrian)
#### Post date: [January 22, 2025, 4:51pm UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/9 "2025-01-22T16:51:06Z")
> [@osa1](#):
>
> My question was whether Menhir allows checking whitespace between two tokens
You can compare the values of `$startpos(...).pos_cnum` between the two tokens, and if they differ by more than one then whitespace was present
---
### Author:  [@osa1](https://discuss.ocaml.org/u/osa1)
#### Post date: [January 23, 2025, 8:10am UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/10 "2025-01-23T08:10:01Z")
> [@WardBrian](#):
>
> You can compare the values of `$startpos(...).pos_cnum` between the two tokens, and if they differ by more than one then whitespace was present
Thanks. I think in this particular case I think this would work, but checking the whitespace in a semantic action means the parser already decided to reduce a production, so we have to raise a parse error if there’s space between the two tokens. We can’t continue parsing.
(Or maybe Menhir allows continuing parsing from a semantic action code, without reducing?)
Ideally the parser should check the whitespace _before_ deciding to reduce. I.e. if I have ` > >` and it shifted the first `>`, it should be in a state where it expects another `>` right next to the current one, or one of `expr` tokens (or others depending on the grammar). This state would not include `>` with whitespace on the left as a valid shift token.
As I said, in this particular problem handling this in a semantic action is fine as `> >` in expression context is always a parse error (probably).
---
### Author:  [@silene](https://discuss.ocaml.org/u/silene)
#### Post date: [January 23, 2025, 8:42am UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/11 "2025-01-23T08:42:34Z")
> [@osa1](#):
>
> I’m curious if there are open source parsers (using Menhir or another L(AL)R) that use this approach that I can have a look?
No idea. In Why3, we have something related, because we need `(*)` to be parsed as a sequence of three tokens, while `(*` would normally start a comment.
In your case, it is just a matter of adding the following line to your lexer (assuming it is an `ocamllex`-based lexer):
```auto
| ">>" { backjump lexbuf 1; RRANGLE }
```
where `backjump` is defined as follows:
```ocaml
let backjump lexbuf chars =
if chars < 0 || chars > lexbuf.lex_curr_pos - lexbuf.lex_start_pos then invalid_arg "backjump";
let pos = lexbuf.lex_curr_p in
lexbuf.lex_curr_pos <- lexbuf.lex_curr_pos - chars;
lexbuf.lex_curr_p <- { pos with pos_cnum = pos.pos_cnum - chars }
```
Then, as I wrote before, modify your parser by replacing `RANGLE` with `(RRANGLE | RANGLE)` wherever `>>` should be parsed as `> >`.
---
### Author:  [@keleshev](https://discuss.ocaml.org/u/keleshev)
#### Post date: [January 23, 2025, 9:39am UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/12 "2025-01-23T09:39:53Z")
Maybe something like the C “lexer hack” can work here?
[Parsing Ambiguity: Type Argument v. Less Than — Vladimir Keleshev](https://keleshev.com/parsing-ambiguity-type-argument-v-less-than)
One way to do it is to maintain a state within the lexer, something like `let is_type_context = ref false`, and let the lexer look up this context and issue two tokens when `>>` is matched.
---
### Author:  [@EmileTrotignon](https://discuss.ocaml.org/u/EmileTrotignon)
#### Post date: [January 23, 2025, 2:39pm UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/13 "2025-01-23T14:39:00Z")
Its probably possible to pass the context as an argument to the lexer rules.
---
### Author:  [@hhugo](https://discuss.ocaml.org/u/hhugo)
#### Post date: [January 24, 2025, 11:02am UTC](https://discuss.ocaml.org/t/menhirs-solution-for-handling-double-angle-brackets-differently-in-type-and-term-contexts/15998/14 "2025-01-24T11:02:49Z")
The incremental API of menhir allows to store the state of the parser and feed it tokens. With this, you can restart parsing from previous state with different tokens. Also, you can also ask whether a given state will accept a specific token.
You can checkout js\_of\_ocaml javascript parser for examples:
>