3
$\begingroup$

I am trying to figure out the simplest way to do this using a regular expression.

  • Three symbols a, b, c.
  • The sequence length is unlimited, i.e. *.
  • The symbol a must be somewhere in the sequence at least once, but can appear more than once.
  • The sequence may have only a.

More formally, $\{ w \in \{a,b,c\}^* ~|~ \#_a(w)\ge 1 \}$, where $\#_a(w)$ is the number of $a$s in $w$.

The best I get is

$( ( b \mid c )^*\, a\, ( b \mid c )^* )^+$

Is that the simplest way?

$\endgroup$
  • $\begingroup$ You ask for EBNF, but you give a regular expression. What is it you want? Also, what does "The sequence can have only a" mean; one one of something (what?) or only symbols $a$? $\endgroup$ – Raphael Apr 4 '12 at 5:54
  • $\begingroup$ It is actualy part of a grammar, thus the EBNF. sepp2k hit the nail on the head with his answer. $\endgroup$ – Guy Coder Apr 4 '12 at 11:00
7
$\begingroup$

The simplest regular expression I can think of for this is $\left(a \mid b \mid c\right)^* a \left(a \mid b \mid c\right)^*$. This is simpler than yours by the following measures of complexity:

  • It contains less nesting (and fewer parentheses in general)
  • It contains fewer quantifiers
$\endgroup$
  • $\begingroup$ @GuyCoder I meant the number of characters in the regex. Mine has 17, yours has 20. $\endgroup$ – sepp2k Apr 4 '12 at 2:04
  • $\begingroup$ @sepp2k: Counting superfluous parentheses is not fair. $\endgroup$ – Raphael Apr 4 '12 at 10:20
  • $\begingroup$ This is simpler because it is nested only to depth one, which makes reasoning about it much easier than if the depth were two or more. In fact, I vote this the simplest and clearest possible. $\endgroup$ – David Lewis Apr 4 '12 at 10:53
  • $\begingroup$ @Raphael I don't need to count superfluous parentheses to have fewer of them. His expression has 3 pairs of non-superfluous parentheses with a nesting-depth of 2. Mine has 2 pairs and a nesting depth of 1. $\endgroup$ – sepp2k Apr 4 '12 at 12:58
5
$\begingroup$

As the expression is to be part of a parser (i.e. should be efficiently checkable), it might be a good idea to make the regular expression unambiguous:

$\qquad \displaystyle (b \mid c)^*\, a\, (a \mid b \mid c)^*$

describes the same language but avoids ambiguity by distinguishing the first $a$ in a matching word. Wether this has an impact depends on the way your parser generator works.

This is the same written as diagram, with the token names the OP uses: enter image description here
Image by Guy Coder.

$\endgroup$
  • $\begingroup$ Also, it is just that tiny bit shorter than Sepp's. :] $\endgroup$ – Raphael Apr 4 '12 at 16:32
  • $\begingroup$ @GuyCoder: This one is unambiguous. I guess your problem lies elsewhere? $\endgroup$ – Raphael Apr 4 '12 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.