White space handling with ambiguous terminals

[udif]

Here is a simplified version of a simple parser I wrote

start: q_or
?q_or : q_and ("or"  q_and)*
?q_and: q_val ("and" q_val)*
?q_val: escaped_string
        | string
        | "not"i q_not 
        | "(" q_or ")"
q_not: q_val
string : STRING
escaped_string : ESCAPED_STRING
STRING: /\w+/
%import common.ESCAPED_STRING
%import common.WS
%ignore WS

It parses simple expressions using and/or/not operators, optionally quoted arguments, and parentheses.

However, my naïve approach causes the expression a andb to be legally parsed as a and b instead of being flagged as illegal, because the and is eagerly matched as a single token instead of taking the longest match first.

In order to revent this, I coded the following alternative:

start: q_or
?q_or : q_and (ws "or"  ws q_and)*
?q_and: q_val (ws "and" ws q_val)*
?q_val: escaped_string
        | string
        | "not"i q_not 
        | "(" q_or ")"
q_not: q_val
string : STRING
escaped_string : ESCAPED_STRING
ws : WS
STRING: /\w+/
%import common.ESCAPED_STRING
%import common.WS
%ignore WS

This parser successfully errors on a andb as I expect.
(The first ws in the q_or and q_and rules might be redundant).
This workaround is not only ugly, it injects extra WS tokens into my Tree which I have to put extra effort to filter out.

How could I achieve this in a simpler, cleaner, way?

[erezsh]

Why not rename it to _ws? Or better, just _WS? Then it won't appear in the tree.

?q_or : q_and (_WS "or"  _WS q_and)*

[udif]

Why not rename it to _ws? Or better, just _WS? Then it won't appear in the tree.

Because I have missed that part in the documentation mentioning that underscores are filtered out of the tree 😄
So generally speaking, is this the best approach to solve this problem, or is there a way to prevent short token matching? This bring back ancient memories from C64 BASIC.
The documentation mentions priorities, but I couldn't get that to work.

[erezsh]

Yes, it seems like the right way to go.

short token matching

Not sure what you mean.

[udif]

Lets take this minimal example:

?start: q_and
?q_and: STRING ( _AND  STRING)*
_AND: "and"i
STRING: /\w+/
%import common.WS
%ignore WS

Matching it against a and b it is working as expected.

You have here 2 token types, one is "and", and the other is any alphanumeric string, with 1 or more characters.

The problem arises when you encounter a andb. How do you tokenize andb?

What ANTLR and flex do, they try to match the longest lexer token it can, so in this case it would have matched STRING, because the STRING can match a single token for 4 input characters, while _AND consumes only 3.

What lark does, it matches and as _AND and then proceeds to match the remaining b as STRING.

This is what I referred to as C64 BASIC behavior... In that ancient ancient BASIC implementations, a tokenizer would try matching any string and abort once it finds a matching token, so you could write IFA=0THENX=1 instead of IF A=0 THEN X=1 and it would still work.

https://stackoverflow.com/questions/6736610/order-of-precedence-for-token-matching-in-flex
https://stackoverflow.com/questions/45450156/how-does-antlr-decide-which-lexer-rule-to-apply-the-longest-matching-lexer-rule

[MegaIng]

That is a consequence of the default lexer='contextual'. At the place where the and matches, no other tokens can match, so the only possible one is tried. You can instead use lexer='standard' (or in >=1.0 'basic') to get the behavior you want.

[udif]

Thanks, this seems to be the issue!
I found the lexer documentation in the document, but I can't easily test it with the Lark IDE as it doesn't let me change the lexer type.
I've tried changing it in my code (lexer='standard'), and it seems to be working! Later I'll take a deeper look into the different lexer types.