Why does regex affect outer rules?

[mannim72]

Hi,

I just got my hands on Lark and am sorry, if this should be a banal question.

Minimal example

from lark import Lark

parser = Lark(
    r"""
    start: "[" FOO "]"
    FOO: /.+/

    %import common.WS
    %ignore WS
    """,
    start="start",
)

print(parser.parse("[FOobarbaz]"))

Expected

Parsing algorithm evaluates start and filters out [,] tokens from the input, as they belong to outer rule.
It then continues evaluation of the inner terminal FOO with input excluding brackets.

Actual

Regex in FOO affects start, eating up the trailing ] token from the outer rule - at least from interpreting the error message:

raise UnexpectedEOF(expected_terminals, state=frozenset(i.s for i in to_scan))
lark.exceptions.UnexpectedEOF: Unexpected end-of-input. Expected one of:
* RSQB

Requirements

• FOO should at least not be empty, but otherwise has no restrictions
• .+ reflects my current knowledge about underlying grammar - I wanted to use this in a first step and fine-tune gradually.
• FOO: /\w+/, ESCAPED_STRING and SIGNED_NUMBER are not sufficient, e.g. I also need to account for :ns/foo.
• Whitespace doesn't matter. e.g. valid input: [FOobarbaz] or [ FOobarbaz ]
  • (Btw: am I right, that in case of %ignore WS, \s,\S would still be evaluated first? Does it make sense at all to use both together?)

Workaround

FOO: /[^\[\]]+/
FOO: /.+\b/

First has the disadvantage to depend on the tokens of the upper start rule, assuming there are wrapping [ and ].
Second at least looses this restriction up a bit, but is not optimal.

Related

(still errors with these)

• How to match anything without error? #1163
  • tried to convert terminal to rule foo: /.+/, as terminal seem to be more greedy
• How do I match any token in the grammar? #1048
  • tried to use lower precedence FOO.-1000: /.+/

Question

Is this a limitation of the underlying Earley parsing algorithm with regexes or did I miss something?
Would the only real solution to narrow valid input patterns further and not use generic .*, despite I am still in the process of exploring valid patterns?

Thanks!

[MegaIng]

You can make this work by using lexer="dynamic_complete". This is very, very slow. For large inputs.

Lark uses regex engines (either the stdlib re or the third party regex). Those will consume as much as they can, independent of the surrounding grammar. So the terminals lark sees are "[", "FOobarbaz]" and then $EOF. This is not fixable from the park side without massive performance hits.

You can use foo: /./+, but like the dynamic complete option, this will be very slow, and in addition the Tree will be annoying to use.

[mannim72]

Thank you so much for this quick explanation and answer on a Sunday, greatly appreciated!

I just tried the dynamic_complete lexer and it indeed works! Guess I'll use that until I know, what an appropriate grammar for my case exactly looks like and then switch back to the default dynamic.

[mannim72]

Ah, forgot one thing: Mind explaining what foo: /./+ is (+ looks like a regex modifier here) and why it works ?