Can Lark be restricted to act as an SLR(1) or LR(1) parser?

[jpivarski]

I'm considering a project that would require DSL parsing on very low-end processors (like Z80s), in which the syntax of the language can be designed to fit the hardware limitations. However, I'm familiar with Lark and Python, and would much rather do prototyping (designing the syntax of the mini-language) in Lark, to get a sense of what kinds of languages would be possible before learning all about emulators and probably writing shift-reduce in assembly.

I've heard that SLR(1) and LR(1) use smaller parse tables and would be more low-end hardware-friendly. Lark has an LALR(1) option, so these parsing algorithms are subsets of what Lark provides in LALR(1) mode.

I'm reading lessons like this one about what exactly these rules are, but I'll need some automated check to tell me I'm overstepping the SLR(1) or LR(1) bounds while developing the DSL grammar (writing the .g file and testing it with Lark). Is there a Lark option or some simple function I could apply to a lark.Lark object to know if it fits these two constraints? Or could I even get the exact size of the parsing table for a given grammar, so that I can estimate what its memory footprint would be on the low-end device?

[MegaIng]

The answer is currently not, but that should not be impossible to add. It might even be reasonably possible to replace the LALR state table generation with a LR(1) or SLR(1) parse table generation, since AFAIK, the actual parsing loop is the same. However, I am not the expert on the parsing implementations.

[erezsh]

SLR(1) and LALR(1) are very very similar. So if a grammar is LALR(1) compatible, it is very likely it will also be SLR(1) compatible. If you really want to make sure it's SLR(1), you can go back to earlier versions of Lark which implemented SLR instead of LALR. (I'll try to find the exact version if you're interested). It will have fewer features than the latest version, of course, but it should be good enough for most purposes.

As for size of table, you can do something like this:

>>> calc_parser = lark.Lark(...)
>>> len( calc_parser.parser.parser.parser.parse_table.states )
23
>>>> sum({1+len(v) for k, v in calc_parser.parser.parser.parser.parse_table.states.items()})
35

It's not "official API", as you might imagine, but it's close enough.

[jpivarski]

If you really want to make sure it's SLR(1), you can go back to earlier versions of Lark which implemented SLR instead of LALR. (I'll try to find the exact version if you're interested).

Is it before issue #478/PR #418 was merged and released? I can search the tags to find that version number if using this version in "LALR(1) mode" is known to give SLR(1) behavior. Since I'm using this for prototyping a language, not the eventual implementation, that would be sufficient. (Lark was mature in November 2019.)

Thanks for the pointer to the parse table size! I understand that it can't be relied upon as a fixed, public API, but it's perfect for this project.