EBNF для ввода запятой между двумя необязательными значениями

Question

У меня есть два необязательных значения, и когда оба присутствуют, между ними должна быть запятая. Если присутствует одно или оба значения, может быть запятой, но если значения отсутствуют, запятая не допускается.

Допустимые примеры:

(first,second,)
(first,second)
(first,)
(first)
(second,)
(second)
()

Неверно примеров:

(first,first,)
(first,first)
(second,second,)
(second,second)
(second,first,)
(second,first)
(,first,second,)
(,first,second)
(,first,)
(,first)
(,second,)
(,second)
(,)
(,first,first,)
(,first,first)
(,second,second,)
(,second,second)
(,second,first,)
(,second,first)

У меня есть код EBNF ( XML-приправленный ), которого достаточно, но есть ли способ, которым я могу упростить его? Я хотел бы сделать его более читабельным / менее повторяющимся.

tuple ::= "(" ( ( "first" | "second" | "first" "," "second" ) ","? )? ")"

Если это легче понять в регулярных выражениях, вот эквивалентный код, но мне нужно решение в EBNF.

/\(((first|second|first\,second)\,?)?\)/

А вот полезная железнодорожная схема:

Этот вопрос становится еще более сложным, когда мы абстрагируем его от трех терминов : "first", "second" и "third" не являются обязательными, но они должны появляться в том порядке, разделенном запятыми , с дополнительной запятой. Лучшее, что я могу придумать, - это метод грубой силы:

"(" (("first" | "second" | "third" | "first" "," "second" | "first" "," "third" | "second" "," "third" | "first" "," "second" "," "third") ","?)? ")"

Очевидно, что решение, включающее O (2 ⁿ ) сложность, не очень желательно.

Answer 1

Я не знаком с EBNF, но я знаком с грамматиками BNF и синтаксического анализатора.Следующее - просто вариант того, что вы основали на моем собственном регулярном выражении.Я предполагаю, что пароли без кавычек не считаются токенами и используются для группировки связанных элементов.

  tuple ::= ( "(" ( "first,second" | "first" | "second" ) ","? ")" ) | "()"

• Соответствует либо (first,second, либо (first, либо (second
• , за которым следует закрывающая скобка.)
• или группировка пустых паренов.()

Но я сомневаюсь, что это улучшение.

Вот мой тестовый код Java.Первые две строки строк в тестовых данных совпадают.Другие нет.

      String[] testdata = {
            "(first,second,)", "(first,second)", "(first,)", "(first)",
            "(second,)", "(second)", "()",

            "(first,first,)", "(first,first)", "(second,second,)",
            "(second,second)", "(second,first,)", "(second,first)",
            "(,first,second,)", "(,first,second)", "(,first,)", "(,first)",
            "(,second,)", "(,second)", "(,)", "(,first,first,)",
            "(,first,first)", "(,second,second,)", "(,second,second)",
            "(,second,first,)", "(,second,first)"
      };

      String reg = "\\(((first,second)|first|second),?\\)|\\(\\)";
      Pattern p = Pattern.compile(reg);

      for (String t : testdata) {
         Matcher m = p.matcher(t);
         if (m.matches()) {
            System.out.println(t);
         }
      }

Answer 2

Я нашел способ упростить его, но ненамного:

"(" ( ("first" ("," "second")? | "second") ","? )? ")"

Для трехчленного решения , выберите двухчленное решение и добавьте первый член:

"(" (("first" ("," ("second" ("," "third")? | "third"))? | "second" ("," "third")? | "third") ","?)? ")"

Для любого (n + 1) срочного решения возьмите n-членное решение и добавьте первый член. Эта сложность составляет O (n) , что значительно лучше, чем O (2 ⁿ ) .

Answer 3

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

\((first|second|)(,|)(second|)([\)|,]+)

Я просто предполагаю, что вы хотите захватить среднюю запятую:

Возможно, это не точное выражение, которое вы хотите.Однако, это может показать вам, как это можно сделать простым способом:

^(?!\(,)\((first|)(,|)(second|)([\)|,]+)$

Вы можете добавить больше границ слева и справавашего выражения, может быть похоже на это выражение :

Этот график показывает, как будет работать второе выражение:

Производительность

Этот фрагмент JavaScript показывает производительность второго выражения с использованием простого цикла for, равного миллиону раз, и егозахватывает first и second с использованием $1 и $3.

repeat = 1000000;
start = Date.now();

for (var i = repeat; i >= 0; i--) {
	var string = "(first,second,)";
	var regex = /^(?!\(,)\((first|second|)(,|)(second|)([\)|,]+)$/gms;
	var match = string.replace(regex, "$1 and $3");
}

end = Date.now() - start;
console.log("YAAAY! \"" + match + "\" is a match ??? ");
console.log(end / 1000 + " is the runtime of " + repeat + " times benchmark test. ? ");