L'esteso Backus Naur Form (EBNF) descrive un insieme di valori non ordinato?

Question

Mi piacerebbe definire un insieme di valori non ordinato utilizzando una grammatica gratuita di un contesto Extended Backus-Naur (EBNF).È facile definire un elenco non ordinato di valori in EBNF, ad esempio:

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

.

Tuttavia, sto avendo dubbi può essere fatto per un set non ordinato.

Di seguito sono riportati esempi di set di valori non ordinati validi:

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

.

Mentre elenchi non validi sarebbe:

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

.

o elenchi di lunghezza arbitraria.

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

.

Answer 1

You può definire i set non ordinati in EBNF, ma solo elencando tutte le possibili enumerazioni. Questo non è pratico per i set più grandi di due elementi.

Lo standard - nella misura in cui EBNF è Una notazione standardizzata: consente di utilizzare l'inglese (o qualsiasi altra lingua con cui ti senti a tuo agio) per descrivere una sequenza che non è altrimenti descrittabile. Ad esempio, l'EBNF per EBNF include questa produzione:

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

.

Allo stesso modo, potresti scrivere qualcosa del genere:

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

.

o forse

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

.

Questo non è molto utile per costruire un generatore di parser, ma potrebbe essere utile per un lettore umano che capisce la stessa lingua come te.

Per i generatori di parser reali, una strategia comune è consentire qualsiasi elenco, che potrebbe includere elementi ripetuti, quindi rifiutare gli elenchi non validi durante l'analisi semantica. (O anche prima. Non è un'analisi difficile.)