Ambiguities and how to handle them

[rbartlensky]

Hey!

While porting an early YACC grammar of Rust, I noticed an interesting edge case that I'm not entirely sure how to handle.

When parsing nested generic parameters, the "original" YACC grammar has a rule to parse a >> token, and emits code that puts back a > token into the lexer. It seems that this is how it works around ambiguities between >> as an operator and >> as generic parameter delimiters.

How should I approach such cases in grmtools? I am aware you can call lexer methods in action blocks, but currently the lexer trait has a limited API.

[ratmice]

I've never tried this myself before, looking at the generated code, it does seem as you say this is in the parser's lexer parameter of the action blocks being an &dyn NonStreamingLexer<...>, and as such I'm assuming that this is also the case even when using a hand written lexer like the calc_manual_lex example.

The only workaround I can think of then might be using something like the %parse_param option in lrpar, and using that to pass in a communications channel to the parser, that a manual lexer can read back? (either through atomics, or an actual channel type like crossbeam or any other mpsc channel).

That is the only thing I could think of, but perhaps I'm missing some other way.

Edit: I think but I'm not completely certain using %parse_param would help, without a way to add extra bounds to the param, in that I think it is only a generic T: Clone in the library portions of lrpar, but your action should see the actual type?

Edit: Just some notes on why mpsc channel specifically, because of the Clone that will happen for each action, each action will look like a different producer, with the lexer itself as a single consumer.

[ltratt]

Amongst the horrors that Yacc allows is this sort of interaction between the lexer and parser, which is a form of context sensitivity. It's never been entirely clear to me how dependent this is on the particular LR parsing approach (does e.g. state table compression affect it? I have never investigated), so I punted on it.

There are some workarounds, none of them ideal.

The most obvious -- and how I've generally done this -- is to only have > as a token and then >> is modelled as two consecutive > tokens. The obvious nastiness is that >> can now be written as > > (i.e. with lots of spaces) and it will be treated the same as >>. Now, in grmtools, one can do cunning things like add a check in the parser's action code saying "if the start span of the second > is not the same as the end span of > then throw a parsing error". This leads to an equivalent user experience to the intermixed lexer-and-parser combo. This has two limitations. First, if < and << are involved in a genuine parser-level ambiguity, this won't work (it's not equivalent in expressive power to the lex/yacc interaction, so it can't express everything, though I think it will work for the example you care about). Second, if you're not adding action code, you can't add the cunning check I suggested. Still, this is almost certainly the approach I would try first.

Another might be lexing states (https://softdevteam.github.io/grmtools/master/book/start_states.html). Honestly, I haven't used these, or put enough time into working out if/how they might be the right thing. I think they suffer from the same problem in this case as the next solution which is...

...to hand-write a lexer that can "magically" distinguish when it's in a typing or binary operation context. At the limit, of course, this would have to encode a large chunk of the parser in the lexer!

[ratmice]

One of the reasons I liked the custom lexer owning the consumer end of a channel, and pass the mpsc producer end of a channel to the parser via %parse_param is that it appears to be able to mirror the push_back interaction that rust parser/lexer is using pretty exactly. (Instead of using the lexer as a single bidirectional channel, you have the lexer as a unidirectional channel, and another back channel to go from parser -> lexer).

I know I'd find it difficult to understand whether two different types of hacks behave the same in all cases,
there is definitely a question of how well it will perform though with cloning a channel end with each action.

Edit: Let me know if you want me to sketch out an example in this style, as I've never seen it done in grmtools

[ltratt]

I must admit that I'm not sure I understand the channel idea at a detailed level (though I get the high level idea).

[ratmice]

Likewise in all honestly, In that I'm not familiar with that rust parser ambiguity, or it's particular workaround. Just some confidence that the lifetimes of the high level idea work out.

[rbartlensky]

Thanks for all the quick responses. I have some thoughts on all solutions below:

• The channel solution: I get the idea, but I don't think it will work in practice. I noticed in lrpar that lexemes are read and cached before parsing starts (I hope I didn't misread this, I only skimmed over the implementation). So even if an action could change the lexer state, it won't be able to change the state of "what is the next lexeme" because the parser doesn't check the lexer anymore for lexemes.
• The splitting >> into > > solution: This might work, and I find it a bit less hacky overall (because we don't need to mutate anything while parsing).
• Lexer with context solution: I think this might be the solution I would have to reach for if I can't apply solution no.2 to all the weird ambiguities I find.

[ratmice]

Ahh, I hadn't thought of that and it seems you are right. This seems to be described in the comment here. I was assuming we could just produce them incrementally via the trait.

grmtools/lrpar/src/lib/parser.rs

Lines 118 to 120 in aac2f25

	// In the long term, we should remove the `lexemes` field entirely, as the `NonStreamingLexer` API is
	// powerful enough to allow us to incrementally obtain lexemes and buffer them when necessary.
	pub(super) lexemes: Vec<LexerTypesT::LexemeT>,