Parglare cannot deal with a LL(1) grammar: S/R conflict

[KOLANICH]

• parglare version: latest from git
• Python version: 3.9
• Operating System: Uhuntu 20.20

Description

https://gist.github.com/KOLANICH/13b0af89f421b172a62c0d81ce7405ed

`parglareBugReport.pglr`

``` addr: addrPart+ {shift}; addrPart: part | optAddrPart {shift}; optAddrPart: OptionalStart addr OptionalEnd {shift}; part: Prefix Ident optArg? {shift}; optArg: OptionalStart ArgumentStart Ident ArgumentEnd OptionalEnd {shift}; LAYOUT: EMPTY; terminals WS: /[\ \t\n\r\x0b\x0c]+/; Ident: /[A-Z_a-z]+/; OptionalStart: '['; OptionalEnd: ']'; ArgumentStart: '<'; ArgumentEnd: '>'; Prefix: ':'; ```

[igordejanovic]

Thanks for the report. Could you please paste here just the minimal parglare grammar you have there on the linked gist?

[KOLANICH]

Done.

[igordejanovic]

This grammar seems not to be LR(1). Compiling by pglr produces:

State 10:Ident
    5: part = Prefix Ident . optArg_opt   {Prefix, OptionalEnd, OptionalStart, STOP}
    10: optArg_opt = . optArg   {Prefix, OptionalEnd, OptionalStart, STOP}
    11: optArg_opt = .   {Prefix, OptionalEnd, OptionalStart, STOP}
    6: optArg = . OptionalStart ArgumentStart Ident ArgumentEnd OptionalEnd   {Prefix, OptionalEnd, OptionalStart, STOP}

In state 10:Ident and input symbol 'OptionalStart' can't decide whether to shift or reduce by production(s) '11: optArg_opt = '.
There is 1 Shift/Reduce conflict.
Either use 'prefer_shifts' parser mode, try to resolve manually, or use GLR parsing.

Which states that when parser sees Ident as a part of part rule and there is OptionalStart ahead it can't decide whether to shift in anticipation to recognize non-empty optArg or reduce optArg as empty and finish part and then use OptionalStart ahead as the optAddrPart which can follow.

I suppose that your idea was that the conflict should be resolved by shift in rule:

part: Prefix Ident optArg? {shift};

But optArg? is desuggared to productions optArg_opt: optArg | EMPTY; and shift is not propagated thus both empty reduction and shift are valid.

We could consider to propagate disambiguation to desuggared productions but will need some time to think of the consequences.

There are two way to resolve. Either spell out the optional optArg and disambiguate on empty reduction:

optArg_opt: optArg | EMPTY {shift};

or just use prefer_shifts_over_empty strategy.

This is loosely related to #37 and #48

[KOLANICH]

Either spell out the optional optArg and disambiguate on empty reduction

Thanks, I'll try this.

[KOLANICH]

Thanks, that has worked to solve the compilation issues.