Может расширить форму Naur Backus (EBNF) описывать неупорядоченный набор значений?

Question

Я хотел бы определить неупорядоченный набор значений с использованием расширенной формы Backus Naur (EBNF) контекста бесплатной грамматики.Легко определить неупорядоченный список значений в EBNF, например:

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

.

Однако у меня сомнения, это можно сделать для неупорядоченного набора.

Ниже приведены примеры действительных неупорядоченных наборов значений:

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

.

В то время как неверные списки будут:

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

.

или списки произвольной длины.

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

.

Answer 1

Вы CAN определите неупорядоченные наборы в EBNF, но только путем перечисления всех возможных перечислений. Это непрактично для множеств больше, чем около двух элементов.

Стандарт - в той степени, в которой EBNF Стандартизированная запись - позволяет использовать английский (или любой другой язык, с которым вы чувствуете себя комфортно), чтобы описать последовательность, которая не обращена иначе. Например, EBNF для EBNF включает в себя эту продукцию:

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

.

Точно так же вы можете написать что-то вроде:

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

.

или, возможно,

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

.

Это не так много использовать для создания генератора парсера, но это может быть полезно для человеческого читателя, который понимает тот же язык, что и вы.

для реальных генераторов парсеров, общая стратегия состоит в том, чтобы позволить любому списку, которая может включать повторные элементы, а затем отклонить неверные списки во время семантического анализа. (Или даже раньше. Это не сложный анализ.)