Ambiguity issues with 0.11.2 version of the vscode extension

[Hassanayo]

Ever since I updated the vscode extension of rascal to version 0.11.2, I have been getting ambiguity warnings and errors when I try to test my syntax. I downgraded back to 0.11.1 and it works as it used to. I even tried it with other previous versions of the extension and they work like they should. What could be the cause?

This is a link to a minimal example of what i'm trying to test https://github.com/Hassanayo/test-expr

There is a file I use to run tests at

src/lang/testlang/Test.rsc

[jurgenvinju]

Some analysis:

• Typically in modules where no layout is defined, the "default" layout nonterminal is used which only accepts the empty string.
• We changed the way "import" works for grammars, because it ignored modules that were extended by an imported module before. I know.. subtle.
• This bug fix can influence which layout definition is used on a rule, since those come with the extends and imports
• The use of a production reference has not been well-tested in combination with the above changes; so we should keep an eye on that too.

For possible workarounds I would suggest extending the Expression module with the Layout module. That way the same layout is applied twice and the source of ambiguity would disappear. That's an educated guess. Please confirm?

[Hassanayo]

This helped a lot. I was also able to apply this understanding to other parts of my code and it fixed the ambiguity issues I was having. Thank you

[rodinaarssen]

I've reduced the provided example even further. Some more analysis:

module A

syntax Expr
    = \one: "1"
    | left add: Expr lhs "+" Expr rhs
    ;

module B

extend A;

layout Layout = [\ ]*;

Note that module B has a layout definition, whereas module A does not. Now, B's Expr seems to have alternatives with A's default layout, and with B's custom layout. This leads to ambiguity in the case of empty layout (1+1) and ambiguity predictions during parser generation.

rascal>(Expr)`1+1`
warning, ambiguity predicted: left add: Expr lhs  "+"  Expr rhs  and left add: Expr lhs  "+"  Expr rhs  lack left or right associativity or priority (>)
warning, ambiguity predicted: left add: Expr lhs  "+"  Expr rhs  and left add: Expr lhs  "+"  Expr rhs  lack left or right associativity or priority (>)
|prompt:///|(0,11,<1,0>,<1,3>):ambiguity in concrete syntax
|prompt:///|(0,11,<1,0>,<1,3>):ambiguity in concrete syntax
|prompt:///|(0,11,<1,0>,<1,11>): Parse error in concrete syntax fragment
Advice: |https://www.rascal-mpl.org/docs/Rascal/Errors/CompileTimeErrors/SyntaxError|
ok
rascal>#Expr
type[Expr]: type(
  sort("Expr"),
  (
    layouts("$default$"):choice(
      layouts("$default$"),
      {prod(
          layouts("$default$"),
          [],
          {})}),
    empty():choice(
      empty(),
      {prod(
          empty(),
          [],
          {})}),
    sort("Expr"):choice(
      sort("Expr"),
      {
        prod(
          label(
            "one",
            sort("Expr")),
          [lit("1")],
          {}),
        associativity(
          sort("Expr"),
          left(),
          {prod(
              label(
                "add",
                sort("Expr")),
              [
                label(
                  "lhs",
                  sort("Expr")),
                layouts("$default$"),
                lit("+"),
                layouts("$default$"),
                label(
                  "rhs",
                  sort("Expr"))
              ],
              {assoc(left())})}),
        associativity(
          sort("Expr"),
          left(),
          {prod(
              label(
                "add",
                sort("Expr")),
              [
                label(
                  "lhs",
                  sort("Expr")),
                layouts("Layout"),
                lit("+"),
                layouts("Layout"),
                label(
                  "rhs",
                  sort("Expr"))
              ],
              {assoc(left())})})
      }),
    layouts("Layout"):choice(
      layouts("Layout"),
      {prod(
          layouts("Layout"),
          [\iter-star(\char-class([range(32,32)]))],
          {})})
  ))

[rodinaarssen]

I could imagine that priorities between nonterminals could have an additional interplay here:

module A

syntax Expr
    = \one: "1"
    | left mult: Expr lhs "*" Expr rhs
    > left add: Expr lhs "+" Expr rhs
    ;

module B

extend A;

layout Layout = [\ ]*;

This yields

rascal>(Expr)`1+1`
warning, ambiguity predicted: left add: Expr lhs  "+"  Expr rhs  and left add: Expr lhs  "+"  Expr rhs  lack left or right associativity or priority (>)
warning, ambiguity predicted: left add: Expr lhs  "+"  Expr rhs  and left mult: Expr lhs  "*"  Expr rhs  lack left or right associativity or priority (>)
warning, ambiguity predicted: left add: Expr lhs  "+"  Expr rhs  and left add: Expr lhs  "+"  Expr rhs  lack left or right associativity or priority (>)
warning, ambiguity predicted: left add: Expr lhs  "+"  Expr rhs  and left mult: Expr lhs  "*"  Expr rhs  lack left or right associativity or priority (>)
warning, ambiguity predicted: left mult: Expr lhs  "*"  Expr rhs  and left add: Expr lhs  "+"  Expr rhs  lack left or right associativity or priority (>)
warning, ambiguity predicted: left mult: Expr lhs  "*"  Expr rhs  and left mult: Expr lhs  "*"  Expr rhs  lack left or right associativity or priority (>)
warning, ambiguity predicted: left mult: Expr lhs  "*"  Expr rhs  and left add: Expr lhs  "+"  Expr rhs  lack left or right associativity or priority (>)
warning, ambiguity predicted: left mult: Expr lhs  "*"  Expr rhs  and left mult: Expr lhs  "*"  Expr rhs  lack left or right associativity or priority (>)
|prompt:///|(0,11,<1,0>,<1,3>):ambiguity in concrete syntax
|prompt:///|(0,11,<1,0>,<1,3>):ambiguity in concrete syntax
|prompt:///|(0,11,<1,0>,<1,11>): Parse error in concrete syntax fragment
Advice: |https://www.rascal-mpl.org/docs/Rascal/Errors/CompileTimeErrors/SyntaxError|
ok
rascal>#Expr
type[Expr]: type(
  sort("Expr"),
  (
    layouts("$default$"):choice(
      layouts("$default$"),
      {prod(
          layouts("$default$"),
          [],
          {})}),
    empty():choice(
      empty(),
      {prod(
          empty(),
          [],
          {})}),
    sort("Expr"):choice(
      sort("Expr"),
      {
        priority(
          sort("Expr"),
          [
            choice(
              sort("Expr"),
              {
                prod(
                  label(
                    "one",
                    sort("Expr")),
                  [lit("1")],
                  {}),
                associativity(
                  sort("Expr"),
                  left(),
                  {prod(
                      label(
                        "mult",
                        sort("Expr")),
                      [
                        label(
                          "lhs",
                          sort("Expr")),
                        layouts("Layout"),
                        lit("*"),
                        layouts("Layout"),
                        label(
                          "rhs",
                          sort("Expr"))
                      ],
                      {assoc(left())})})
              }),
            associativity(
              sort("Expr"),
              left(),
              {prod(
                  label(
                    "add",
                    sort("Expr")),
                  [
                    label(
                      "lhs",
                      sort("Expr")),
                    layouts("Layout"),
                    lit("+"),
                    layouts("Layout"),
                    label(
                      "rhs",
                      sort("Expr"))
                  ],
                  {assoc(left())})})
          ]),
        priority(
          sort("Expr"),
          [
            choice(
              sort("Expr"),
              {
                associativity(
                  sort("Expr"),
                  left(),
                  {prod(
                      label(
                        "mult",
                        sort("Expr")),
                      [
                        label(
                          "lhs",
                          sort("Expr")),
                        layouts("$default$"),
                        lit("*"),
                        layouts("$default$"),
                        label(
                          "rhs",
                          sort("Expr"))
                      ],
                      {assoc(left())})}),
                prod(
                  label(
                    "one",
                    sort("Expr")),
                  [lit("1")],
                  {})
              }),
            associativity(
              sort("Expr"),
              left(),
              {prod(
                  label(
                    "add",
                    sort("Expr")),
                  [
                    label(
                      "lhs",
                      sort("Expr")),
                    layouts("$default$"),
                    lit("+"),
                    layouts("$default$"),
                    label(
                      "rhs",
                      sort("Expr"))
                  ],
                  {assoc(left())})})
          ])
      }),
    layouts("Layout"):choice(
      layouts("Layout"),
      {prod(
          layouts("Layout"),
          [\iter-star(\char-class([range(32,32)]))],
          {})})
  ))

[jurgenvinju]

That's a great reduction to the essence @rodinaarssen

Conclusion: the interplay between extend and layout is working as planned but it's neither intuitive nor handy. It's a complex interplay that produces alternatives of the same rule with different layout nonterminals interlaced.

• We could experiment with a different algorithm where layout is only added after extend has done its work.
• And/Or an algorithm that detects and removes duplicates caused by the default layout explicitly. Since nobody typed in the default.
• Or: remove the notion of default layout entirely.
• And the checker can also detect such duplicates and force a layout definition in the extending or importing module to shadow ambiguous definitions.

All of the above suggestions break existing grammars.

[jurgenvinju]

If we remove default layout from the game the parser generator could warn about missing layout definitions where the grammar is used for parsing and concrete syntax.

[jurgenvinju]

Personally i like the default layout because it helps people get started and make results before having crossed all their t's and dotted their i's. Like syntax E = "a" "b" simply works out of the box.

So: I think it makes sense to not add default layout to rules yet if they are still to be extended, and probably merged with a layout declaration. So let's try that?

Knowing that such a change can also remove ambiguity and even introduce new parse errors in existing grammars. Especially owners of highly modular grammars could be in for small surprises. However, in my mind this would be only for grammars that depend on the default implicit layout to go before extend. If people need the old behavior, they can drop this into their bottom modules: layout Empty = ;

What are you thoughts on this @DavyLandman @rodinaarssen @Hassanayo ?

[DavyLandman]

Yes, I agree, only add default layout in the end, if non of the modules ended up contributing layout. That way you get less surprises, but still enable the case where people didn't specify their layout.