Need help parsing "nested" strings

[Techcable]

Hi! I'm trying to parse nested quoted strings (like the shell does). I have a working recursive decent parser that I'm trying to port to lark.

In zsh, the following double-quoted strings all parse as a single item:

echo "foo"
echo "foo "bar" baz"
echo "foo "bar\"k" baz"
echo "foo \" baz"

Here is my grammar so far

REGULAR_DQUOTED_CHARS: /([^"\\]|\\[^"\\]|\\[\\"])+/
double_quoted_string: "\"" (REGULAR_DQUOTED_CHARS | double_quoted_string)* "\""

It parses basic strings correctly (without nesting), but it cannot handle "foo "bar" baz". The problem seems to be that there's ambiguity when it encounters the closing quote. It thinks it should start a new double_quoted_string instead of closing the existing one. 😦

I'm no really sure how to proceed because I've never used LALR parsers before 😦

I am also willing to write some sort of plugin to handle this, but I'm not sure how to do that (could you point me to the appropriate documentation or examples?)

I would prefer not to use insane regex features like lookahead/lookbehind (I don't really understand those 😉)

EDIT: Similarly, how would I parse balanced parentheses like "(foo (bar) baz)" without caring what is inside?

[MegaIng]

What is the pattern that says "foo "bar" baz" should be a single terminal? You need to encode that pattern in some way (probably a look ahead regex).

[Techcable]

Instead of using regexes I'm trying to use nested rules with double_quoted_string.

double_quoted_string: "\"" (REGULAR_DQUOTED_CHARS | double_quoted_string)* "\""

So REGULAR_DQUOTED_CHARS should match everything except an unquoted " (it does that correctly)

So what I want for "foo "bar" baz" is the parse tree

(double_quoted_string
    (regular "foo ")
    (double_quoted_string (regular "bar"))
    (regular " baz")
)

However the problem is the parser is too eager with the closing quote, so at the end of "bar" it should close the second level of nesting, but instead it starts a new double_quoted_string (adding a third level of nesting).

I don't really know how to fix this :(

I don't really understand lookahead/lookbehind regexes 😦 If you could link me to a good tutorial that explains this use case I would be happy to look into that instead.

[MegaIng]

Once again, what are the rules? Clearly in one sentence say when an encountered " starts a new nested string and when it ends the current one. If the answer is "Well, we otherwise don't have enough closing quotes", then this is straight up context sensitive and can't really be done in a nice way.

[Techcable]

Yes. I've looked into it some more and it seems parsing the shell is highly context sensitive 😦

This isn't the only problem, there are actually a ton of them.

I will most likely have to write a custom lever from scratch....

[erezsh]

It seems that the pattern is that after a string quote you can't have a letter (or digit too?) . I'm guessing it because in this example echo "foo \" baz" it's escaped, probably because a whitespace follows. If that's the case, then forward-lookahead should do the trick easily.

As for plugins, we have a slightly smarter mechanism. Instead of inserting yourself in the middle of the parse, you can instead instrument it using this feature: https://lark-parser.readthedocs.io/en/latest/classes.html#lark.Lark.parse_interactive

Which uses this class: https://lark-parser.readthedocs.io/en/latest/classes.html#interactiveparser

The API for it is still a little rough around the edges, but it works. And I don't mind doing a bit of polishing if you decide to use it.