Может расширить форму Naur Backus (EBNF) описывать неупорядоченный набор значений?
-
21-12-2019 - |
Вопрос
Я хотел бы определить неупорядоченный набор значений с использованием расширенной формы 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
...
. Решение
Вы 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
? ;
.
Это не так много использовать для создания генератора парсера, но это может быть полезно для человеческого читателя, который понимает тот же язык, что и вы.
для реальных генераторов парсеров, общая стратегия состоит в том, чтобы позволить любому списку, которая может включать повторные элементы, а затем отклонить неверные списки во время семантического анализа. (Или даже раньше. Это не сложный анализ.)