SDF features separators for * and + such as:

[{Member "\n"}*]

I propose to add pre and post strings as well, for both * and + as well as ?.

This will enable patterns such as

class [ID] [{" extends " ID}?] {
  ...
}

That now have to be encoded as:

Class.Class = [class [ID][Extends?] {
  ...
}]
Extends = [ extends [ID]]

Possible syntax:

{[String?] [ID] [String?] [String?]}*
{[String?] [ID] [String?] [String?]}+
{[String?] [ID] [String?]}?

But this makes {Foo "foo"}* ambiguous, as it is not clear whether "foo" is the separator or the postfix string.

Any suggestions?

Submitted by Daco Harkes on 20 September 2016 at 13:06

this would be nice, to disambiguate maybe explicit syntax needs to be added for the postfix operator? Would be nicer on the separator but that would break backwards compatibility

I can see that this makes sense for optional phrases. I see a general use case for this case. For repetition operators, this appears to be an adhoc abstraction coming from a very particular need. The pre- and post- phrase can go into the sort that is repeated, since these phrases will be repeated as well. To me, the proposed 4-element syntax is also unintuitive. Let’s say you teach compiler construction. How would you explain and justify such a construct?

Our current syntax for separators {ID ", "}* is also not entirely intuitive, as it implies that every element must be followed by the separator.

For comparison, here’s how this would work in XText:

Class:
	'class' name=ID ('extends' interfaces+=ID (',' interfaces+=ID)*)?
);

If sub-patterns were be supported in SDF, we could write (for a prefix):

Class.Class = "class" ID ("extends" {ID ", "}+)?

And the corresponding template syntax:

Class.Class = <class <ID> <(<extends> {ID ", "}+)?>>

SDF2 supported arbitrary composition of symbols; see section 3.2 of A Family of Syntax Definition Formalisms. This included sequential composition, which allow things such as

“begin” (Decl “;”)? {Stat “;”}+ “end” -> Stat

to have an optional declaration followed by semicolon followed by a list of statements separated by semicolons.

I decided not to have such arbitrary regular expressions in SDF3, since their use in SDF2 turned out cumbersome. That is, the mapping to abstract syntax tree and more importantly pretty-print rules (in GPP) did not support the arbitrary regular expressions. The current SDF3 style forces the introduction of constructors for every sub-expression with literals.

Supporting regular expressions again is not an issue for parsing; embedded regular expressions are just lifted out into auxiliary productions by normalization. The question that such proposals should address is how these constructs are treated in the rest of the pipeline. In addition, the cognitive aspect should be considered, of course.