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-flavored)，但是有什么方法可以简化它吗？我想让它更具可读性/更少重复。

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

这个表达式可能会帮助您设计更好的表达式。您可以仅使用捕获组并从左向右滑动并传递您可能的输入来执行此操作，可能与此类似：

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

我只是猜测您希望捕获中间的逗号：

这可能不是您想要的确切表达方式。但是，它可能会向您展示如何以简单的方式完成此操作：

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

您可以在表达式的左右添加更多边界，可能类似于 this expression：

此图显示了第二个表达式的工作原理：

性能

此 JavaScript 片段显示了第二个表达式使用简单的 100 万次 for 循环的性能，以及它如何使用 first 和 second 捕获 </code> 和 <code>.

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, " and ");
}

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

Answer 2

我不熟悉 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 3

我找到了一种简化它的方法，但不是很多：

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

对于 three-term 解决方案，采用 two-term 解决方案并添加第一项：

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

对于任何 (n+1) 项解，采用 n-term 解并添加第一项。这个复杂度是O(n)，明显优于O(2ⁿ).

EBNF 用于捕获两个可选值之间的逗号

EBNF for capturing a comma between two optional values

regex

big-o

ebnf

性能