I have been having issues where I get an ambiguity reported where the branches of the ambiguity appear to be identical.

I recently have run into this problem a couple times after updating to the nightly, I suspect there may be a new bug since then. However, I haven’t tested this on the old grammar yet - I thought I should check whether it would actually be a bug or “by design”.

The full grammar is available in a gist

Here’s a relevant excerpt:

Def+ Expr -> Expr{"Let",left}

":" Expr -> OptContract{"SomeContract"}
":" "*"  -> OptContract{"AsIs"}
""       -> OptContract{"DefaultContract"}

ID "(" {Param ","}* ")" OptContract "=" Expr -> Def{"Fun"}
ID OptContract "=" Expr                      -> Def{"Var"}

This parses a string

seven = 7 seven

like this:

Let(
  [ amb(
      [ Var("seven", DefaultContract(), Int("7"))
      , Var("seven", DefaultContract(), Int("7"))
      ]
    )
  ]
, Id("seven")
)

The ambiguity here is puzzling for me. I had previously run into this when using the ‘*’ or ‘?’ quantifiers to allow some term to be optional.

Is this new and unexpected, or is there something I’m just not getting about how to make something optional?

Submitted by Dobes Vandermeer on 16 December 2012 at 05:49

Such ambiguities are typically caused by layout. In your case, the "" -> OptContract rule is the first candidate. You can simply use a rule with a real empty left-hand side instead: -> OptContact.

Since you know the mailing list: Can you please continue to post such questions there?

I keep this issue open for now, but I doubt it is really a bug.

I had originally not had the "" in OptContact but tried it in the off chance it would help. I just tried removing it as you suggested but it didn’t fix it, unfortunately. :-(

The only thing that seems to fix the issue is to eliminate the OptContract rule by splitting the rules that use it into three versions and inline the OptContract rule.

What is the amb you get when changing the Def{“var”} rule into one with the ‘?’ quantifier and by removing "" -> OptContract{"DefaultContract"}?

Like this:

ID "(" {Param ","}* ")" OptContract? "=" Expr -> Def{"Fun"}

If I use ? like this:

ID (":" Expr)? "=" Expr                      -> Def{cons("Var")}

Or like this:

  ":" Expr -> Contract{cons("Contract")}
  ID Contract? "=" Expr                      -> Def{cons("Var")}

For this input:

seven = 7 seven

I get this:

Let(
[ amb(
[ Var(“seven”, None(), Int(“7”))
, Var(“seven”, None(), Int(“7”))
]
)
]
, Id(“seven”)
)

But splitting the rule into two like this:

  ID ":" Expr "=" Expr                      -> Def{cons("Var")}
  ID          "=" Expr                      -> Def{cons("NormalVar")}

I don’t get any ambiguity:

Let([NormalVar("seven", Int("7"))], Id("seven"))

But I have less re-use of existing rules (both in the grammar and in desugaring).

I ran into this issue twice in the same week so it seemed like it might trip other people up and it really LOOKS like a bug since the branches of the ambiguity are (apparently) identical.

I have also reverted back to the stable version Spoofax/IMP 1.0.2.0-r24315 but the problem persists.

Ah, I think I’m onto something - everytime I insert a space I get another level of ambiguity, so:

seven    = 7 seven

becomes

		Let(
		  [ amb(
		      [ amb(
		          [ amb(
		              [ amb(
		                  [ Var("seven", None(), Int("7"))
		                  , Var("seven", None(), Int("7"))
		                  ]
		                )
		              , Var("seven", None(), Int("7"))
		              ]
		            )
		          , Var("seven", None(), Int("7"))
		          ]
		        )
		      , Var("seven", None(), Int("7"))
		      ]
		    )
		  ]
		, Id("seven")
		)

After some investigation, the problem appears to be that I had mistakenly grouped the “greedy matching rules” for comments into lexical restrictions instead of context-free restrictions. Putting the rules into context-free restrictions seems to resolve the issue. Like this:

  %% Ensure greedy matching for comments
	context-free restrictions
		LAYOUT? -/- [\ \t\n\r]
		LAYOUT? -/- [\/].[\/]
		LAYOUT? -/- [\/].[\*]

Apparently there are two types of lexical restrictions at play here, but I didn’t notice that I had conflated them (until now, that is).

Is there a document describing the distinction between the two types of restrictions? This seems somehow useful for something I was trying to achieve recently … I may have failed because I was using the wrong kind of restriction there as well.

As I mentioned in an earlier comment, ambiguities with the same AST do not indicate a bug, but an ambiguity caused by layout. Please discuss such issues on the mailing list. Case closed for now.

OK got it, sorry about that.