title: EBNF for capturing a comma between two optional values
body: <p>I have two optional values, and when both are present, a comma needs to be in between them. If one or both values are present, there <em>may</em> be a trailing comma, but if no values are present, no comma is allowed.</p>
  
  <p>Valid examples:</p>
  
  <pre><code>(first,second,)
  (first,second)
  (first,)
  (first)
  (second,)
  (second)
  ()
  </code></pre>
  
  <p><em>Invalid</em> examples:</p>
  
  <pre><code>(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)
  </code></pre>
  
  <p>I have EBNF code (<a href="https://www.w3.org/TR/xml/#sec-notation" rel="nofollow noreferrer">XML-flavored</a>) that suffices, but is there a way I can simplify it? I would like to make it more readable / less repetitive.</p>
  
  <pre><code>tuple ::= "(" ( ( "first" | "second" | "first" "," "second" ) ","? )? ")"
  </code></pre>
  
  <p>If it’s easier to understand in regex, here’s the equivalent code, but I need a solution in EBNF.</p>
  
  <pre class="lang-regex prettyprint-override"><code>/\(((first|second|first\,second)\,?)?\)/
  </code></pre>
  
  <p>And here’s a helpful railroad diagram:
  <a href="https://i.stack.imgur.com/yAtSC.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/yAtSC.png" alt="&quot;(&quot; ( ( &quot;first&quot; | &quot;second&quot; | &quot;first&quot; &quot;,&quot; &quot;second&quot; ) &quot;,&quot;? )? &quot;)&quot;"></a></p>
  
  <p>This question becomes even more complex when we <strong>abstract it to three terms</strong>: <code>"first"</code>, <code>"second"</code>, and <code>"third"</code> are all optional, but they must appear in that order, separated by commas, with an optional trailing comma. The best I can come up with is a brute-force method:</p>
  
  <pre><code>"(" (("first" | "second" | "third" | "first" "," "second" | "first" "," "third" | "second" "," "third" | "first" "," "second" "," "third") ","?)? ")"
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/neij8.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/neij8.png" alt="&quot;(&quot; ((&quot;first&quot; | &quot;second&quot; | &quot;third&quot; | &quot;first&quot; &quot;,&quot; &quot;second&quot; | &quot;first&quot; &quot;,&quot; &quot;third&quot; | &quot;second&quot; &quot;,&quot; &quot;third&quot; | &quot;first&quot; &quot;,&quot; &quot;second&quot; &quot;,&quot; &quot;third&quot;) &quot;,&quot;?)? &quot;)&quot;"></a>
  Clearly, a solution involving <em>O(2<sup>n</sup>)</em> complexity is not very desirable.</p>