Ambiguity in mangling grammar around type qualifiers about cxx-abi HOT 8 OPEN

Hmm, yes, that is awkward to specify in standard CFG notation, because you really want to define <qualifiers> in a way that makes it not allowed to expand to the empty string: you want to say that every single thing in it is optional, but one of them has to be there.

If you defined <qualifiers> so that it had to be non-empty, you could do something like this:

<type> ::= <qualifiers> <subtype>
       ::= <unqualified-type>
<subtype> ::= <unqualified-type>
<unqualified-type> ::= [big list of more specific productions]

and then designate <type> and <subtype> as the nonterminals that are substitution candidates. That way there's always an SC for the overall type, and an extra one for the unqualified type only if at least one qualifier is present.

But in plain CFG notation it's pretty awkward to write <qualifiers> in a way that forces it to be non-empty. The only approach I can think of is to break it up into subcases based on the first non-empty part:

<qualifiers> ::= <extended-qualifier>+ [r] [V] [K]
             ::=                        r  [V] [K]
             ::=                            V  [K]
             ::=                                K

and, really, yuck!

from cxx-abi.

Both the fully-qualified and unqualified types need to introduce substitution candidates, but we shouldn't do it twice for unqualified types. I'm hesitant to do some major refactor of the tree, but if you can find a clean solution, I'm open to taking it.

from cxx-abi.

Yeah. Unfortunately, I think this is a situation where creating a formally correct and unambiguous grammar is actually in tension with clarity for human readers, which seems like the more important goal. I'm inclined to just close this, but I can leave it open if you'd like to continue thinking about it for a while.

from cxx-abi.

No argument there – of course I agree that clarity for humans is more important. But it would be nice if we could also have a reference parser that verifiably matches the spec.

Would you be open to a compromise in which the grammar is refactored as in the first snippet above, but with the RHS reference to <qualifiers> simply adding a note that it must be non-empty?

<type> ::= <qualifiers> <subtype> # but only if <qualifiers> is non-empty
       ::= <unqualified-type>
<subtype> ::= <unqualified-type>
<unqualified-type> ::= [big list of more specific productions]

That loses the really ugly part, which is the cumbersome redefinition of <qualifiers> via lots of horrible repetitive productions to force it to be non-empty.

I don't know that you could make an LR parser generator accept a grammar in this unusual representation (even if you wrote a custom one), but I do know that the simpler and more brute-force Earley algorithm would cope with it fine. Perhaps that would still be adequately clear to humans, while also permitting at least one parsing technology to handle the grammar?

from cxx-abi.

Yeah, I think a note saying that <qualifiers> must be non-empty (and maximal?) would be totally reasonable.

from cxx-abi.

I'd prefer just "non-empty", and to handle "maximal" by reorganising the grammar to ensure it can't generate two adjacent <qualifiers>. "Maximal" is a harder property to check for automatically!

from cxx-abi.

Do you have a suggestion of how to do that which doesn't look awful?

from cxx-abi.

I thought the suggestion in my last-but-one comment was reasonably minimal, just rearranging the top-level rule or two for <type>, and annotating the one use of <qualifiers> with a note saying this rule is only valid if it's non-empty. With that, <qualifiers> itself wouldn't have to be modified at all.

(It does mean there's no formal representation of that non-emptiness requirement. But I don't think there'd be any clean way to do that unless you introduced some kind of exciting new syntax for grammar rules, like "lhs ::= rhs1 AND NOT rhs2"!)

from cxx-abi.