Proposal: Order independent parsing

[martin31821]

I stumbled across a minor issue which is might worth further discussion.

I think it would be good to have a possibility to declare substructs as order independent.

Use Case

I have a language which is influenced by hcl, but has support for nested blocks with special names, the idea is to support an arbitrary order for those sub-blocks, but have the blocks only being generated either zero or one time.

Solution proposal

Introducing a new parser primitive like { } for repetition (e.g. using <>) which defines a Set of arguments, which can be parsed order independent.

[alecthomas]

Can you provide an example of what you're suggesting? Both a proposed grammar and some sample input, perhaps.

EBNF is very well established, so it would be surprising to me if you've encountered something that can't be expressed in it.

[martin31821]

The closest I can think of is something like this:

x = (a b c) | (a c b) | (b a c) | (b c a) | (c a b) | (c b a);
a = "foo" "{" { k "=" v "," } "}";
b = "bar" "{" { k "=" v "," } "}";
c = "baz" "{" { k "=" v "," } "}";
k = IDENTIFIER;
v = STRING;

basically the idea is to have multiple rules which can occur in any order but each rule may only occur once, so the following is valid:

foo {
a="b",
c="d",
}
bar {
a="b",
c="d",
}

but this is not:

foo {
a="b",
c="d",
}
foo {
e="f",
}

I'd like to specify something like this as semantically equivalent of the above:

x = <a b c>;
a = "foo" "{" { k "=" v "," } "}";
b = "bar" "{" { k "=" v "," } "}";
c = "baz" "{" { k "=" v "," } "}";
k = IDENTIFIER;
v = STRING;

[alecthomas]

Ah, ok, interesting idea. I think that in the interest of keeping the grammar syntax simple (and sticking largely with EBNF), that it's fine to enforce this in semantic analysis, after parsing.