Generating autocomplete "kernels" from Ohm grammars

[westoncb]

I have been thinking about making something like a "generator generator" based on Ohm grammars: it would take in a grammar and spit out 1) a graph representation of the grammar 2) something that can walk the graph according to repetition operators associated to nodes/rules, generating characters when terminals are reached.

The idea is that the generated "generator" would form the kernel of an autocomplete system (but could also be used to procedurally generate grammatical sentences).

If I were to build it I'd open source it. My approach is to use Ohm to generate a parser for Ohm grammars; then when given a grammar, parse it, use the AST to construct a graph based on how Rules reference each other (Edit: just realizing Ohm already provides a tree representation of grammars when doing ohm.grammar(grammarString), so can probably construct graph from this...).

The reason for the graph representation is just that it's a convenient structure for the "walker" to navigate: whenever it is at a node (representing some Rule), the repetition operators at that node dictate constraints on its behavior: it can be forced down a particular edge, certain loops can be followed multiple times, etc.

The autocomplete system would function by allowing users to make choices whenever multiple options are available at a given node.

my question:

Can anyone advise me as to whether this seems like a good general direction? Are there standard approaches to building autocomplete systems from formal grammars that might be superior? If you were to build some kind of general basis for generating autocomplete systems from Ohm grammars, what is the approach you would take?

[MuhammedZakir]

I have also thought about this. It would be pretty cool if we could get a generator and a parser from a single grammar. It's in my to-do list atm as I don't have enough knowledge and time for this.

I think left-corner parser [1] may be a better fit for this purpose.

[1] https://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node53.html

[westoncb]

That looks pretty interesting, though I am specifically interested in doing this with Ohm grammars. I think I'll just give it a shot at some point this week, since a basic version doesn't seem like too much work... (My guess is that if it needed to support every feature of Ohm's grammars it would be quite difficult, and theoretical considerations would be much more important—but, there may be a subset that could be worked with for more basic cases, and more complete support could be added over time.)