Regexp with repeating patterns

A pattern can be matched a minimum+maximum number of times, where maximum can be infinite, for instance: The STAR operator goes from zero to infinite.

A Short Repeating Pattern

The /ab*ba/ is an interesting pattern which is very inefficient, but demonstrates perfectly the problems of finding longest match. It could be optimized to /abb*a/ and would then be much more efficient.

/ab*ba/.match("aa")

R0	R1	R2	R3	R4	R5
'a'	REP	'b'	/REP	'b'	'a'

I0	I1
a	a

input=I0 regex=R0 stack=[]

i.data == r.data == "a" → i+=1; r+=1

input=I1 regex=R1 stack=[]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I1 regex=R4 stack=[[I0 <I1_R2_N0_C0>]]

i.data ("a") != r.data ("b") → restart at the repeat point; repeat-count+=1

input=I1 regex=R2 stack=[[I0 <I1_R2_N1_C0>]]

i.data ("a") != r.data ("b") → stop (no more repeat is possible)

/ab*ba/.match("aba")

R0	R1	R2	R3	R4	R5
'a'	REP	'b'	/REP	'b'	'a'

I0	I1	I2
a	b	a

input=I0 regex=R0 stack=[]

i.data == r.data == "a" → i+=1; r+=1

input=I1 regex=R1 stack=[]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I1 regex=R4 stack=[[I0 <I1_R2_N0_C0>]]

i.data == r.data == "b" → i+=1; r+=1

input=I2 regex=R5 stack=[[I0 <I1_R2_N0_C0>]]

i.data == r.data == "a" → i+=1; r+=1

input=I3 regex=R6 stack=[[I0 <I1_R2_N0_C0>]]

the end → restart at the repeat point; repeat-count+=1

input=I1 regex=R2 stack=[[I0 <I1_R2_N1_C0>]]

i.data == r.data == "b" → i+=1; r+=1

input=I2 regex=R3 stack=[[I0 <I1_R2_N1_C1>]]

ignore repeat-close → r+=1

input=I2 regex=R4 stack=[[I0 <I1_R2_N1_C1>]]

i.data ("a") != r.data ("b") → restart at the repeat point; repeat-count+=1

input=I2 regex=R2 stack=[[I0 <I1_R2_N2_C0>]]

i.data ("a") != r.data ("b") → stop (no more repeat is possible)

/ab*ba/.match("abba")

R0	R1	R2	R3	R4	R5
'a'	REP	'b'	/REP	'b'	'a'

I0	I1	I2	I3
a	b	b	a

input=I0 regex=R0 stack=[]

i.data == r.data == "a" → i+=1; r+=1

input=I1 regex=R1 stack=[]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I1 regex=R4 stack=[[I0 <I1_R2_N0_C0>]]

i.data == r.data == "b" → i+=1; r+=1

input=I2 regex=R5 stack=[[I0 <I1_R2_N0_C0>]]

i.data ("a") != r.data ("b") → restart at the repeat point; repeat-count+=1

input=I1 regex=R2 stack=[[I0 <I1_R2_N1_C0>]]

i.data == r.data == "b" → i+=1; r+=1

input=I2 regex=R3 stack=[[I0 <I1_R2_N1_C1>]]

ignore repeat-close → r+=1

input=I2 regex=R4 stack=[[I0 <I1_R2_N1_C1>]]

i.data == r.data == "b" → i+=1; r+=1

input=I3 regex=R5 stack=[[I0 <I1_R2_N1_C1>]]

i.data == r.data == "a" → i+=1; r+=1

input=I4 regex=R6 stack=[[I0 <I1_R2_N1_C1>]]

the end → restart at the repeat point; repeat-count+=1

input=I1 regex=R2 stack=[[I0 <I1_R2_N2_C0>]]

i.data == r.data == "b" → i+=1; r=execute repeat pattern again

input=I2 regex=R2 stack=[[I0 <I1_R2_N2_C1>]]

i.data == r.data == "b" → i+=1; r+=1 (done with repeating)

input=I3 regex=R3 stack=[[I0 <I1_R2_N2_C2>]]

ignore repeat-close → r+=1

input=I3 regex=R4 stack=[[I0 <I1_R2_N2_C2>]]

i.data ("a") != r.data ("b") → stop (no more repeat is possible)

A Longer Repeating Pattern

/(ab)*a/.match("aba")

R0	R1	R2	R3	R4
REP	'a'	'b'	/REP	'a'

I0	I1	I2
a	b	a

input=I0 regex=R0 stack=[]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I0 regex=R4 stack=[[I0 <I0_R1_N0_C0>]]

i.data == r.data == "a" → i+=1; r+=1

input=I1 regex=R5 stack=[[I0 <I0_R1_N0_C0>]]

the end → restart at the repeat point; repeat-count+=1

input=I0 regex=R1 stack=[[I0 <I0_R1_N1_C0>]]

i.data == r.data == "a" → i+=1; r+=1

input=I1 regex=R2 stack=[[I0 <I0_R1_N1_C0>]]

i.data == r.data == "b" → i+=1; r+=1

input=I2 regex=R3 stack=[[I0 <I0_R1_N1_C0>]]

ignore repeat-close → r+=1

input=I2 regex=R4 stack=[[I0 <I0_R1_N1_C1>]]

i.data == r.data == "a" → i+=1; r+=1

input=I3 regex=R5 stack=[[I0 <I0_R1_N1_C1>]]

the end → restart at the repeat point; repeat-count+=1

input=I0 regex=R1 stack=[[I0 <I0_R1_N2_C0>]]

i.data == r.data == "a" → i+=1; r+=1

input=I1 regex=R2 stack=[[I0 <I0_R1_N2_C0>]]

i.data == r.data == "b" → i+=1; r+=1

input=I2 regex=R3 stack=[[I0 <I0_R1_N2_C0>]]

r == RepeatClose → restart at repeat pattern

input=I2 regex=R1 stack=[[I0 <I0_R1_N2_C1>]]

i.data == r.data == "a" → i+=1; r+=1

input=I3 regex=R2 stack=[[I0 <I0_R1_N2_C1>]]

the end → stop (no more repeat is possible)

Two repeating patterns with wildcards!

/.a.b/.match("abab")

R0	R1	R2	R3	R4	R5	R6	R7
REP	Any	/REP	'a'	REP	Any	/REP	'b'

I0	I1	I2	I3
a	b	a	b

input=I0 regex=R0 stack=[]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I0 regex=R3 stack=[[I0 <I0_R1_N0_C0>]]

i.data == r.data == "a" → i+=1; r+=1

input=I1 regex=R4 stack=[[I0 <I0_R1_N0_C0>]]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I1 regex=R7 stack=[[I0 <I0_R1_N0_C0,I1_R5_N0_C0>]]

i.data == r.data == "b" → i+=1; r+=1

input=I2 regex=R8 stack=[[I0 <I0_R1_N0_C0,I1_R5_N0_C0>]]

the end → restart at the repeat point; repeat-count+=1

input=I1 regex=R5 stack=[[I0 <I0_R1_N0_C0,I1_R5_N1_C0>]]

i.data == r.data == "." → i+=1; r+=1

input=I2 regex=R6 stack=[[I0 <I0_R1_N0_C0,I1_R5_N1_C0>]]

ignore repeat-close → r+=1

input=I2 regex=R7 stack=[[I0 <I0_R1_N0_C0,I1_R5_N1_C1>]]

i.data ("a") != r.data ("b") → restart at the repeat point; repeat-count+=1

input=I1 regex=R5 stack=[[I0 <I0_R1_N0_C0,I1_R5_N2_C0>]]

i.data == r.data == "." → i+=1; r=repeat-point

input=I2 regex=R5 stack=[[I0 <I0_R1_N0_C0,I1_R5_N2_C1>]]

i.data == r.data == "." → i+=1; done repeating, r+=1

input=I3 regex=R6 stack=[[I0 <I0_R1_N0_C0,I1_R5_N2_C2>]]

ignore repeat-close → r+=1

input=I3 regex=R7 stack=[[I0 <I0_R1_N0_C0,I1_R5_N2_C2>]]

i.data == r.data == "b" → i+=1; r+=1

input=I4 regex=R8 stack=[[I0 <I0_R1_N0_C0,I1_R5_N2_C2>]]

the end → not possible to match more with this repeat, thus pop repeat element and restart; repeat-count+=1

input=I0 regex=R1 stack=[[I0 <I0_R1_N1_C0>]]

i.data == r.data == "." → i+=1; done repeating, r+=1

input=I1 regex=R2 stack=[[I0 <I0_R1_N1_C0>]]

ignore repeat-close → r+=1

input=I1 regex=R3 stack=[[I0 <I0_R1_N1_C1>]]

i.data ("b") != r.data ("a") → restart at the repeat point; repeat-count+=1

input=I0 regex=R1 stack=[[I0 <I0_R1_N2_C0>]]

i.data == r.data == "." → i+=1; keep repeating

input=I1 regex=R1 stack=[[I0 <I0_R1_N2_C1>]]

i.data == r.data == "." → i+=1; done repeating, r+=1

input=I2 regex=R2 stack=[[I0 <I0_R1_N2_C2>]]

ignore repeat-close → r+=1

input=I2 regex=R3 stack=[[I0 <I0_R1_N2_C2>]]

i.data == r.data == "a" → i+=1; r+=1

input=I3 regex=R4 stack=[[I0 <I0_R1_N2_C2>]]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I3 regex=R7 stack=[[I0 <I0_R1_N2_C0,I3_R5_N0_C0>]]

i.data == r.data == "b" → i+=1; r+=1

input=I4 regex=R8 stack=[[I0 <I0_R1_N2_C0,I3_R5_N0_C0>]]

the end → restart at the repeat point; repeat-count+=1

input=I3 regex=R5 stack=[[I0 <I0_R1_N2_C0,I3_R5_N1_C0>]]

i.data == r.data == "." → i+=1; r+=1

input=I4 regex=R6 stack=[[I0 <I0_R1_N2_C0,I3_R5_N1_C1>]]

the end → pop repeat element; repeat-count+=1

input=I0 regex=R1 stack=[[I0 <I0_R1_N3_C0>]]

i.data == r.data == "." → i+=1; keep repeating

input=I1 regex=R1 stack=[[I0 <I0_R1_N3_C1>]]

i.data == r.data == "." → i+=1; keep repeating

input=I2 regex=R1 stack=[[I0 <I0_R1_N3_C2>]]

i.data == r.data == "." → i+=1; done repeating, r+=1

input=I3 regex=R2 stack=[[I0 <I0_R1_N3_C3>]]

ignore repeat-close → r+=1

input=I3 regex=R3 stack=[[I0 <I0_R1_N3_C3>]]

i.data ("b") != r.data ("a") → stop (no more repeat is possible)

/x((.))x/.match("0x1x2x3")

R0	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10
'x'	REP	GRP	REP	GRP	Any	/GRP	/REP	/GRP	/REP	'x'

I0	I1	I2	I3	I4	I5	I6
0	x	1	x	2	x	3

input=I0 regex=R0 stack=[]

i.data ("0") != r.data ("x") → try match i+=1

input=I1 regex=R0 stack=[]

i.data == r.data == "x" → i+=1; r+=1

input=I2 regex=R1 stack=[]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I2 regex=R10 stack=[[I0 <I2_R2_N0_C0>]]

i.data ("1") != r.data ("x") → repeat-count+=1, restart

input=I2 regex=R2 stack=[[I0 <I2_R2_N1_C0>]]

r == GroupOpen → r+=1

input=I2 regex=R3 stack=[[I0 <I2_R2_N1_C0>]]

r == RepeatOpen → r=r.find(RepeatClose)+1

input=I2 regex=R8 stack=[[I0 <I2_R2_N1_C0,I2_R4_N0_C0>]]

r == GroupClose → r+=1

input=I2 regex=R9 stack=[[I0 <I2_R2_N1_C0,I2_R4_N0_C0>]]

r == RepeatClose → r+=1

input=I2 regex=R10 stack=[[I0 <I2_R2_N1_C0,I2_R4_N0_C0>]]

i.data ("1") != r.data ("x") → repeat-count+=1, restart

input=I2 regex=R4 stack=[[I0 <I2_R2_N1_C0,I2_R4_N1_C0>]]

r == GroupOpen → r+=1

input=I2 regex=R5 stack=[[I0 <I2_R2_N1_C0,I2_R4_N1_C0>]]

i.data == r.data == "." → i+=1; r+=1

input=I2 regex=R6 stack=[[I0 <I2_R2_N1_C0,I2_R4_N1_C0>]]

r == GroupClose → r+=1

input=I2 regex=R7 stack=[[I0 <I2_R2_N1_C0,I2_R4_N1_C0>]]

r == RepeatClose → done, repeating, r+=1

input=I2 regex=R8 stack=[[I0 <I2_R2_N1_C0,I2_R4_N1_C1>]]

r == GroupClose → r+=1

input=I2 regex=R9 stack=[[I0 <I2_R2_N1_C0,I2_R4_N1_C1>]]

r == RepeatClose → done, repeating, r+=1

input=I2 regex=R10 stack=[[I0 <I2_R2_N1_C0,I2_R4_N1_C1>]]

i.data ("b") != r.data ("a") → stop (no more repeat is possible)

How to implement repeat?

A Short Repeating Pattern

/ab*ba/.match("aa")

/ab*ba/.match("aba")

/ab*ba/.match("abba")

A Longer Repeating Pattern

/(ab)*a/.match("aba")

Two repeating patterns with wildcards!

/.*a.*b/.match("abab")

/x((.)*)*x/.match("0x1x2x3")

/.a.b/.match("abab")

/x((.))x/.match("0x1x2x3")