O Backus Naur Form estendido (EBNF) pode descrever um conjunto não ordenado de valores?

Question

Gostaria de definir um conjunto não ordenado de valores usando uma gramática livre de contexto Extended Backus-Naur Form (EBNF).É fácil definir uma lista não ordenada de valores em EBNF, por exemplo:

value = 'A' | 'B' | 'C';
list = value, {',', value};

No entanto, estou com dúvidas de que isso possa ser feito para um conjunto não ordenado.

Abaixo estão exemplos de conjuntos de valores não ordenados válidos:

A, B, C, D
A, B, D, C
A, D, C, B
...
D, C, B, A

Embora as listas inválidas sejam:

A, A, C, D
B, C, C, B
A, A, A, A
...

ou listas de comprimento arbitrário.

A, A, B, C, D, A
A, B, C, D, A, B, C, D
...

Answer 1

Você pode definir conjuntos não ordenados em EBNF, mas apenas listando todas as enumerações possíveis.Isso é impraticável para conjuntos maiores que dois elementos.

O padrão - na medida em que EBNF é uma notação padronizada - permite que você use o inglês (ou qualquer outro idioma com o qual se sinta confortável) para descrever uma sequência que de outra forma não seria descritível.Por exemplo, o EBNF para EBNF inclui esta produção:

syntactic exception
= ? a syntactic-factor that could be replaced 
    by a syntactic-factor containing no
    meta-identifiers
  ? ;

Da mesma forma, você poderia escrever algo como:

value = 'A' | 'B' | 'C';
list = value, {',', value};
set = ? a "list" where all "value"s are unique ? ;

ou talvez

set = ? a "list" with exactly three values
        where all "value"s are unique
      ? ;

Isso não é muito útil para construir um gerador de analisador, mas pode ser útil para um leitor humano que entende a mesma linguagem que você.

Para geradores de analisadores reais, uma estratégia comum é permitir qualquer lista, que pode incluir elementos repetidos, e então rejeitar listas inválidas durante a análise semântica.(Ou até antes.Não é uma análise difícil.)