4

I'm using lark, an excellent python parsing library.

It provides an Earley and LALR(1) parser and is defined through a custom EBNF format. (EBNF stands for Extended Backus–Naur form).

Lowercase definitions are rules, uppercase definitions are terminals. Lark also provides a weight for uppercase definitions to prioritize the matching.

I'm trying to define a grammar but I'm stuck with a behavior I can't seem to balance.

I have some rules with unnamed literals (the strings or characters between double-quotes):

directives: directive+
directive: "@" NAME arguments ?
directive_definition: description? "directive" "@" NAME arguments? "on" directive_locations
directive_locations: "SCALAR" | "OBJECT" | "ENUM"

arguments: "(" argument+ ")"
argument: NAME ":" value

union_type_definition: description? "union" NAME directives? union_member_types?

union_member_types: "=" NAME ("|" NAME)*

description: STRING | LONG_STRING    

STRING: /("(?!"").*?(?<!\\)(\\\\)*?"|'(?!'').*?(?<!\\)(\\\\)*?')/i
LONG_STRING: /(""".*?(?<!\\)(\\\\)*?"""|'''.*?(?<!\\)(\\\\)*?''')/is
NAME.2: /[_A-Za-z][_0-9A-Za-z]*/

It works well for 99% of use case. But if, in my parsed language, I use a directive which is called directive, everything breaks:

union Foo @something(test: 42) = Bar | Baz   # This works
union Foo @directive(test: 42) = Bar | Baz   # This fails

Here, the directive string is matched on the unnamed literal in the directive_definition rule when it should match the NAME.2 terminal.

How can I balance / adjust this so there is no ambiguity possible for the LALR(1) parser ?

achedeuzot
  • 4,164
  • 4
  • 41
  • 56

1 Answers1

9

Author of Lark here.

This misinterpretation happens because "directive" can be two different tokens: The "directive" string, or NAME. By default, Lark's LALR lexer always chooses the more specific one, namely the string.

So how can we let the lexer know that @directive is a name, and not just two constant strings?

Solution 1 - Use the Contextual Lexer

What would probably help in this situation (it's hard to be sure without the full grammar), is to use the contextual lexer, instead of the standard LALR(1) lexer.

The contextual lexer can communicate to some degree with the parser, to figure out which terminal makes more sense at each point. This is an algorithm that is unique to Lark, and you can use it like this:

parser = Lark(grammar, parser="lalr", lexer="contextual")

(This lexer can do anything the standard lexer can do and more, so in future versions it might become the default lexer.)

Solution 2 - Prefix the terminal

If the contextual lexer doesn't solve your collision, a more "classic" solution to this situation would be to define a directive token, something like:

DIRECTIVE: "@" NAME

Unlike your directive rule, this leaves no ambiguity to the lexer. There is a clear distinction between a directive, and the "directive" string (or NAME terminal).

And if all else fails, you can always use the Earley parser, which at the price of performance, will work with any grammar you give it, regardless of how many collisions there might be.

Hope this helps!

Edit: I'd just like to point out the the contextual lexer is the default for LALR now, so it's enough to call:

parser = Lark(grammar, parser="lalr")
Erez
  • 1,287
  • 12
  • 18
  • 1
    I ended up using the contextual lexer. It helped massively ! Thanks :D – achedeuzot Jul 06 '18 at 15:58
  • @Erez: How can I match my grammar pattern in the long string? For ex. If I have "I have claimed 2 under rule 5 of GRAMMER PATTERN HERE again there are some strings", then have grammar for "GRAMMER PATTERN HERE", so how can I tell my grammer there are some literals/special chars/strings before and after my grammer match string? – Mohanraj Sep 18 '18 at 12:17
  • I think your best bet is to parse the GRAMMAR PATTERN in the strings after the first parse is done. So to have 2 passes in total. – Erez Sep 19 '18 at 20:41