Background

SDF allows for context-free grammar specifications. And provides all kinds of convenient disambiguation mechanisms. Because you’ll usually want a (mostly) unambiguous grammar.

But if you want ambiguity, you either need to leave that in your grammar or massage your grammar so you can use some handwritten AmbXyz constructor name.
The second choice you don’t want, that’s why you’re writing in SDF rather than a more traditional formalism like the one yacc or Antler uses.
But the first choice isn’t that great either: there are automatic warnings in the editor when something is ambiguous, and in Stratego you have to define amb : List(a) -> a before you can match on it.

It makes total sense that you get warnings and have to jump through hoops to match amb in Stratego, because most of the time an ambiguous parse means you forgot something in your syntax definition.
But there are examples where you really need ambiguous syntax and you want to use for example name analysis to disambiguate:

1. In Java this happens for references to a field vs. a local variable. But there you can just parse as a variable reference and let the name binding rules resolve that reference to a variable or if that isn’t present a field. That matches how you would read Java code, look for a variable and if it’s not present look for a field. This is the easy case, where both options are references.
2. The motivating example for me is in the programming language CamlLight. In this functional language there are Algebraic Data Types (in simplest form these equal enums) and you can do pattern matching. This combination is quite natural, but the complication comes from ambiguity between variable names and ADT constructor names. In a pattern a single lower-case letter (for example) can mean the introduction of a variable or matching against a previously defined constructor with that name. The difference with the Java example is that the ambiguity is now between a reference and a definition.
   There are different ways to solve these ambiguities at the name-binding phase, including analysis->disambiguation->reanalysis. But the nicest way seems to be to leave the syntax ambiguous, supply the normal name binding rules and disambiguate after name analysis (no reanalysis required).

Proposal

Define a new attribute in SDF ambiguous. Example use:

Pattern.PatternVar     = [[IDENT]] {ambiguous}
Pattern.Constructor    = [[ADTConstructor]]

When this attribute is used, any ambiguity originating from the rules that it marks is wrapped into the constructor Amb in stead of amb (perhaps use something like ExplicitAmb in stead?). When the constructor signatures of the language are collected (in include/<nameofthelanguage>.str), not only should the constructors for the List and Option be added, but also for this explicit ambiguity. And in an editor explicit ambiguity is not marked with a warning.

Summary

Ambiguity can easily be introduced when writing a grammar in SDF. Usually it’s an error by the person who wrote the grammar and should be fixed. Therefore the standard behaviour of a warning on ambiguities in the editor of the language makes sense, as does not being able to match on amb([ ... ]) in Stratego (at least out-of-the-box without defining amb as a constructor).
But there are situations where you want to have ambiguity in the grammar which you will resolve later with information from semantic analyses (e.g. name analysis). Therefore it would nice to be able to define ambiguity explicitly in SDF through an attribute on a rule that introduces such an ambiguity.

Submitted by Jeff Smits on 5 March 2014 at 11:10

Do you still get the warning, when you remove the amb term during analysis (either before or after name analysis)?

Yes, you still get the warning. I tried by adding a desugaring before the analysis that chooses the first term in the amb list.