The Problem
I have a bunch of regular expressions that I need to use in some code, but I'm using a programming language that doesn't support regex! Luckily, I know that the test string will have a maximum length and will be composed of printable ASCII only.
The Challenge
You must input a regex and a number n
, and output every string composed of printable ASCII (ASCII codes 32 to 126 inclusive, to
~
, no tabs or newlines) of length less than or equal to n
that matches that regex. You may not use built-in regular expressions or regex matching functions in your code at all. Regular expressions will be limited to the following:
- Literal characters (and escapes, which force a character to be literal, so
\.
is a literal.
,\n
is a literaln
(equivalent to justn
), and\w
is equivalent tow
. You do not need to support escape sequences.) .
- wildcard (any character)- Character classes,
[abc]
means "a or b or c" and[d-f]
means anything from d to f (so, d or e or f). The only characters that have special meaning in a character class are[
and]
(which will always be escaped, so don't worry about those),\
(the escape character, of course),^
at the beginning of the character class (which is a negation), and-
(which is a range). |
- the OR operator, alternation.foo|bar
means eitherfoo
orbar
, and(ab|cd)e
matches eitherabe
orcde
.*
- match the previous token repeated zero or more times, greedy (it tries to repeat as many times as possible)+
- repeated one or more times, greedy?
- zero or one times- Grouping with parentheses, to group tokens for
|
,*
.+
, or?
The input regex will always be valid (i.e., you do not have to handle input like ?abc
or (foo
or any invalid input). You may output the strings in any order you would like, but each string must appear only once (don't output any duplicates).
The Test Cases
Input: .*
, 1
Output: (empty string), ,
!
, "
, ..., }
, ~
Input: w\w+
, 3
Output: ww
, www
Input: [abx-z][^ -}][\\]
, 3
Output: a~\
, b~\
, x~\
, y~\
, z~\
Input: ab*a|c[de]*
, 3
Output: c
, cd
, ce
, aa
, cde
, ced
, cdd
, cee
, aba
Input: (foo)+(bar)?!?
, 6
Output: foo
, foo!
, foofoo
, foobar
Input: (a+|b*c)d
, 4
Output: ad
, cd
, aad
, bcd
, aaad
, bbcd
Input: p+cg
, 4
Output: pcg
, ppcg
Input: a{3}
, 4
Output: a{3}
The Winner
This is code-golf, so the shortest code in bytes will win!
|
makes very little sense. It doesn't seem to handle nested groups ora|b|c
. What's wrong with using the standard explanations in terms of how strongly concatenation and alternation bind? (And you have no excuse for not using the sandbox) \$\endgroup\$