Lark: Parse-time specification of start non-terminal

[petee-d]

I'm working on a grammar for a query language that has several entities that can recursively use each other. As an example, imagine SQL and entities like an entire subquery, a projection item, a constraint in the WHERE clause - any of those entities can contain the other entities inside. The parser needs to be able to parse a string given what kind of entity it is, i.e. I ultimately need a method that parses any valid select query, another method that parses any valid projection item, another one that parses a constraint and so on - I think I'll need at least 7 such entities.

I currently see two options on how to do that.

• Create mutliple parsers, each time specifying the same grammar but different start non-terminal. This has the disadvantage of compiling the grammar and creating the parser each time, which is a problem considering just one parser takes quarter of a second to build and with 7 the startup time increases too much.
• Create a grammar with a special starting non-terminal that determines the type of entity that the parsed string should represent based on some short prefix, like here (just an illustration, I didn't even check this is a valid grammar):

start: "!select" select
     | "!projection" projection
     | "!where" where
// bellow is what the actual grammar might look like
select: "select" projection+ "where" where
projection: "column" | select
where: "constraint" | "exists(" select ")" 

The above is most likely what I'll end up doing, but it's ugly and I will have to account for this artificially added prefix in determining the position of parse errors in user supplied inputs.

A better solution I could imagine is the ability to supply the start non-terminal when calling the parse method. I don't know much of the theory behind the other parser frontends, but for LALR this should be possible just by initializing the parser state stack with a state determined by mapping the name of the start non-terminal supplied by the caller.

This is probably too big of a change for me to attempt to do myself any time soon. Is this something that you would like lark to have one day? Do you see any better workaround, or is the input prefix hack the best one can do?

[erezsh]

Upon some reflection, I think what you're asking is possible, and shouldn't be too difficult to implement (if and when I find the time to do it). However I'm not 100% certain that's the case, as I might be forgetting some hidden obstacle.

The API I envision for such a feature, is to specify ahead-of-time a list of possible start symbols, and later on to be able to choose between them. So:

parser = Lark(..., start=['rule1', 'rule2', 'rule3')
parser.parse('text', start='rule1')
parser.parse('text', start='rule2')

Just to make sure, will that work for your purposes?

Also, did you consider using Earley? While slower for big chunks of texts, it is much faster to initialize, and you could easily implement multiple start symbols there yourself.

[petee-d]

That API seems great, I didn't think it would be necessary to initialize the parser with a set of possible start symbols, but it's certainly not a problem for my usage.

As for Earley, while long startup time is somewhat of an issue, parsing time is still orders of magnitudes more important.

Thank you for your response, I'm glad such a feature sounds reasonable for you. I'll see which one of the two workarounds I will use in the meantime.

[bilderbuchi]

This feature sounds useful also for, e.g., testing the correct operation of atransformer for certain sub-parts of the grammar. Currently, I create a separate Lark instance for each test which, although relatively easy to implement with pytest fixtures, is quite wasteful/slow.

Maybe a better API would be

parser = Lark(..., start='rule2', start_choices=['rule1', 'rule2', 'rule3'])
parser.parse('text')  # will use rule2
parser.parse('text', start='rule1')  # will dynamically switch to start with rule1

to ensure this feature remains optional and to not complicate parse calls for the "default" usage?

[erezsh]

@petee-d

I pushed a working solution to a new branch called lalr_refactor

Can you check if it's working for you?

Example usage:

        def test_multi_start(self):
            parser = _Lark('''
                a: "x" "a"?
                b: "x" "b"?
            ''', start=['a', 'b'])

            self.assertEqual(parser.parse('xa', 'a'), Tree('a', []))
            self.assertEqual(parser.parse('xb', 'b'), Tree('b', []))

[petee-d]

@erezsh, you are the most amazing open source software author I've ever had the please to encounter. :) Every time I reported a problem with lark (of which there really aren't many), you reacted incredibly fast either with a fix or a code review, but I really didn't expect this barely important feature request to be satisfied this fast... Lark is now officially my favorite Python library, I already wanted to dedicate my next PyCon SK talk to it, I'll definitely do it now.

I tested your solution on my 10kB grammar and it works great!

[erezsh]

Thanks, @petee-d, I'm happy you had such a good experience with Lark! And I'm flattered to receive such compliments. This feature request just had the right balance of being small and simple enough, but also a little tricky, which is my favorite combination. Also, I think it's an improvement on Lark's API.

If you do end up talking about Lark, let me know if you have any questions for me. And if possible, please send me the link afterwards, so I can brag about it :)

[petee-d]

Just to tame the expectations, the conference is like 9 months away. :)

I certainly don't want to rush you or anything, but do you have plans to get the multiple start token changes to pip any time soon? If not, I might end up using it in production by commit ID, but that's not ideal. :smile:

[erezsh]

Heh, no problem. Well, now that it's tested and seems to be working, I can merge it into master. But then I usually wait a couple of weeks at least, to see if it breaks anything before pushing a new version to pip.

[petee-d]

That's awesome, it might take a couple of weeks to get my thing to production anyway and I can do with a commit reference until then.

[erezsh]

(pushed to master)