Console TAB-Autocomplete Support? (get list of legal tokens following a partial input string)

[davidmcnabnz]

Hi all,

Has anyone implemented TAB-completion in Lark-based REPLs?

I'm building a Lark-based program with a REPL console interface. With this, I'm really appreciating Lark's very straightforward usage pattern and flexibility.

In the program usage:

1. The user enters one full-line command, then hits ENTER
2. The command is sent to the parser
3. The transformer converts the tree to a 'command spec'
4. The program dispatches the command spec to the proper execution method, and gets a response object
5. The response object is formatted for display to the user
6. The user is prompted for the next command (or "quit" or Ctrl-D), and goes back to step 1

My front end supports command history, but I'd really like to be able to support tab-autocomplete as well.

What this would mean is a user being able to enter part of a command, then hit TAB, then see a list of possible tokens which would be legal from that point.

For instance, if one of the CLI's commands was show, with subcommands users, alarms, connections, then a user would be able to type 'show', then a space, then hit TAB, and see the lines:

users
alarms
connections

To accomplish that with a Lark-based parser, is there any way of feeding in a partial string of text, and getting a list of tokens which would be legal from that point?

Cheers
David

[erezsh]

Hi @davidmcnabnz ,

The way I would implement this is by trying to parse the incomplete string, as usual. It will of course throw an exception, for example UnexpectedToken, which you can then catch, and then access its expected attribute, which returns the set of legal tokens at that point.

Documentation for parsing exceptions: https://lark-parser.readthedocs.io/en/latest/classes.html#unexpectedinput

P.S. You could also use UnexpectedInput's interactive_parser attribute to get even more information about the state.

[davidmcnabnz]

Hi Erez,

Thanks for your recommendation.

In cases where the line entered by the user is not yet syntactically valid, I am able to catch an UnexpectedToken exception and translate the expected entries into user-facing help output. This so far is really good! :)

But my syntax has commands with optional add-ons, so when attempting a parse on a command that's already ok, but allows add-ons, I'll just get the transformer output, and no exception.

For an oversimplified example, the grammar:

start: cmd
cmd: FOO BAR foobar_arg?
foobar_arg: BAZ
  | BAM

FOO: "foo"
BAR: "bar"
BAZ: "baz"
BAM: "bam"

In this case, if a user hits TAB after they've entered foo bar, the line they've entered will be a syntactically valid match for cmd, and will satisfy start without any errors. But the user hits TAB wanting to know if anything else is permitted.

After a user has already entered foo bar, it should ideally be possible to determine what, if any, tokens can validly follow what they've entered. For a user, this would mean informing them that they can validly complete the command in any of 3 ways:

1. Just hit ENTER, because foo bar is sufficient
2. Enter baz, then hit ENTER
3. Enter bam, then hit ENTER

Are there any straightforward techniques you can recommend for interrogating the parser and seeing if there are any valid 'add-on' tokens?

Cheers
David

[MegaIng]

I created a small example: https://github.com/MegaIng/lark-autocomplete . This works for your example grammar and the python grammar that lark comes with, so it should be quite powerful. I want to extend that to an at least somewhat complete library.

[erezsh]

That's cool. What would you consider a complete library?

As it is now, I wouldn't mind adding it as another module in Lark, and maybe adding a few more usability features.

[MegaIng]

• support for step-by-step input using copies of the parser state to reduce computations time in an interactive environment.
• string suggestions instead of Token types where possible (potentially using interegular)
• ability to provide a list of defined names for specific tokens
• (optionally, potentially hard or impossible) ability to get a rule context in which a token is required to provide better suggestions, i.e. attribute names.

[erezsh]

Makes sense. Step-by-step should be easy if it's only for adding input.

Yeah, for the last point you would need the user to be a lot more involved, but I think it might be possible. There's a way to produce a partial tree automatically on error. If you run a simplistic interpreter on it, then the user only needs to implement the name-setting methods, like assign or for_as, etc., and return the new names they might have created.

It's not perfect, and of course isn't full-fledged auto-complete, although for motivated users it might be possible to implement the rest using the partial tree.

[erezsh]

P.S. regarding performance, good to keep this in mind - #1142

It's been a while, but iirc it could make accepts() much faster, especially for long inputs.

[davidmcnabnz]

@MegaIng huge appreciation for your demo. It totally satisfies the need, to the extent I've dropped you a PR with an interactive demo script.

Compliments too on your design of both the LarkCompleter class, and the CompleteResult objects it spits out. The result object gives the ideal "just barely enough" detail - especially with the .pos attribute allowing caller to determine where 'legal input' has ended, and the .prefix attribute to support filtering on the .token_options members.

Together with interrogating the .terminals list in the parser object, this allows an autocompleter to display options (if more than 1) or auto-append the line buffer (if just 1) or beep and swear (if none).

Thanks again
David