Soft Keywords and How to Implement Them

[isidentical]

I've been thinking for a day about how we can possibly implement PEP 622 in case of acceptance. While I was thinking, I drafted a piece of code, which might seem totally unreasonable (since it changes the parser to semi-LL(1) from LL(1)) but wanted to share it as a maybe last resort? I tried to document the strategy as inline comments, so feel free to read and comment about it:

https://github.com/davidhalter/parso/compare/master...isidentical:soft-keywords-very-very-bad-demo?expand=1

[isidentical]

CC: @davidhalter @bgw

[davidhalter]

@isidentical Interesting work. I'm not sure we should go this route. An alternative way to deal with "soft keywords" is using something like name: NAME | 'match'. That would of course need a step where match is converted back to a name if it's not a keyword (i.e. if the parent is not a match_stmt). What do you think about that idea?

However I would probably prefer a PEG parser at that point. But at the same time I haven't really thought about that either.

PS: I hope that the PEP gets rejected. IMO this is just additional syntax without major benefits. If pattern matching was at least an expression, then I would maybe see it, but this way it's just useless (you can do most thing with if).

[isidentical]

What do you think about that idea?

Will look into that (and possibly draft a PoC), but at least for now, I don't think it would be the right fit.

However I would probably prefer a PEG parser at that point. But at the same time I haven't really thought about that either.

Yes, me too (if we can). As I said, this is just a workaround for that problem. I, unfortunately, can't start such an action but can participate whenever I'm free. (If anyone interested with the idea, and maybe some rust/c backend).

PS: I hope that the PEP gets rejected. IMO this is just additional syntax without major benefits. If pattern matching was at least an expression, then I would maybe see it, but this way it's just useless (you can do most thing with if).

I ~partially agree. I don't really mind if it gets accepted, but not as is. IMHO It needs major changes including very big simplifications. It took like hours and hours to finally comprehend the whole document, which I believe shows it is a very complex and dense piece of language addition at least in a single transaction. It might be considered to divide the PEP into parts and gradually include/exclude some parts of it. Let's wait and see it, no need to rush :P

[davidhalter]

Yes, me too (if we can). As I said, this is just a workaround for that problem. I, unfortunately, can't start such an action but can participate whenever I'm free. (If anyone interested with the idea, and maybe some rust/c backend).

Why can't you start? Because it would be written in a lower level language?

It took like hours and hours to finally comprehend the whole document, which I believe shows it is a very complex and dense piece of language addition at least in a single transaction

Yeah, I also didn't read the whole thing, it's simply too long and complicated. But that might just be this iteration of the draft.

[isidentical]

Why can't you start? Because it would be written in a lower level language?

No, I'm currently in the process of getting a job for this summer. And not sure if I can dedicate some time to it, at least solely. If you / or anybody else tries to attempt it, I can help in my free times.

[isidentical]

@davidhalter would you check out (and comment if you have anything to say) this? https://bugs.python.org/issue40360

[davidhalter]

I have thought quite a bit about this. It's similar to your plan, but not exactly the same.

We can probably use our existing LL parser and make it PEG compatible with a small trick:
Backtracking in case of ambiguities (otherwise use normal LL). At the backtracking point just use the LL algorithm again for the plan.

This is very similar to PEG and would need some work, but it's probably not even that hard to do. The biggest challenge will probably be keywords/soft keywords and backtracking.

It seems like your solution is quite similar to this, but you seem to transition ahead to make it clear which plan to take. This works of course as well.

[isidentical]

Interesting, do you have time to come up with a draft that supports both soft keywords and the multiline context managers. Obivously, we don't need to have an ideal, an epitome strategy to parse, so we could just embed the backtracking into the LL parser. For the reference, I've written about it: https://tree.science/what-the-backtracking.html

[davidhalter]

At the moment I have other priorities, but I will definitely come up with something before 3.10 releases if you don't do the work :)

My goal for parso is just to get it running so people can use it. My priorities lie with creating a parser that is both faster and better than parso (and is probably a different project).

[isidentical]

if you don't do the work :)

:-) [inserts a november song]

My goal for parso is just to get it running so people can use it. My priorities lie with creating a parser that is both faster and better than parso (and is probably a different project).

I like hacky ways 😎

[davidhalter]

I think your general approach is pretty good, I would probably just use a slightly different approach in the generator (if possible): I would move some of the logic there to calculate the plans beforehand. But I haven't really thought about everything and your solution might be what we need.

[isidentical]

I started some stuff, but calculating the rules beforehand is a bit tricky. The thing that makes backtracking harder for us is error-recovery. If we'd assume all input is valid, we iterate all possible plans (for e.g optional parens for with-stmt) and try to perform a dry-run and see which one of the alternatives completed. And as soon as one completes, we could return it. But since we also do error recovery, we need to take on token at the time, feed all the plans, get the next possible plans, and complete those and repeat this until we find a plan that either takes more input than others.

The proposed patch does this on a very small scale, but for ambigous rules, I might have an alternate patch (still working on, but no luck so far). Basically what it does is, instead of keeping transitions as a 1-to-1 mapping between token_type -> DFA, it keeps them as 1-to-many mapping between token_type -> [DFA1, DFA2, ...]. And when we proceed to parser, we check how many dfas we have, if it is 1, then just return that, if it is more than 1, than try to repeat this process I just mentioned above.

[davidhalter]

I will answer later, but maybe you can answer something about CPython's PEG grammar. I don't really understand why the tilde in the following code is necessary. I have read the PEP about it and understand that it's usually used to avoid considering alternatives. But in this case there are no alternatives, so why is it there?

listcomp:
    | '[' named_expression ~ for_if_clauses ']'

[isidentical]

I presume you found it on the docs.python.org, which is the stripped version of the official grammar. That rule actually has 2 alternatives (one is only used for error reporting in cases like [a for a in *b], but since it is an error-only alternative it got stripped away. See the original rule. The reason that tilde is required there is, if we already parsed named_expression than that invalid_ alternative is no longer will needed since the only purpose of that alternative was checking whether the iterable is a starred item or not. So if the parser is able to recognize named_expression than it can continue forward without even considering alternatives and if it fails, it will raise a normal syntax error.