Is it possible to create a regular expression that matches regular expressions in any given notation?
Or, in other words, does there exist a unambiguous and full notation for regular expressions that can be parsed with regular expressions?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityIs it possible to create a regular expression that matches regular expressions in any given notation?
Or, in other words, does there exist a unambiguous and full notation for regular expressions that can be parsed with regular expressions?
Even if we require that the expressions are "human-readable", and the conversion between the standard notation and the new notation is fairly easy to compute, the answer is "yes".
For example, we can modify the standard notation as follows to obtain "compressed" regular expressions:
That is, ((a|b)*c)de(f|g)
can be expressed in the "compressed" notation using, for example, any of the following forms: a|b)*c)de(f|g
or ((a|b)*c)de(f|g
or (a|b)*c)de(f|g)
.
The compressed notation is unambiguous in the sense that you can recover a semantically equivalent expression by simply adding a sufficient number of leading and trailing parentheses to make everything balanced. Of course, a|b)*c)de(f|g
might represent ((a|b)*c)de(f|g)
or (((a|b)*c)de(f|g))
, but adding extra parentheses does not change the language defined by the expression.
The "compressed" notation is a regular language.
And yes, this is cheating.
No, it is not possible. You can reduce the language of regular expressions to the language of matching brackets using a homomorphism; As matching brackets is not a regular language, you will neither be able to parse regular expressions with a regular expression.