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?

Improve this question
$\endgroup$
2
  • $\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, 2012 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, 2012 at 11:00

2 Answers 2

Reset to default
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
Improve this answer
$\endgroup$
4
  • $\begingroup$ @GuyCoder I meant the number of characters in the regex. Mine has 17, yours has 20. $\endgroup$
    – sepp2k
    Apr 4, 2012 at 2:04
  • $\begingroup$ @sepp2k: Counting superfluous parentheses is not fair. $\endgroup$
    – Raphael ♦
    Apr 4, 2012 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, 2012 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, 2012 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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