World: r3wp

in the file i posted is a function REGSET that converts small bit 
of regex to bitset, it's syntax seems to be easier than charset's 
syntax (charset [#"a" - #"z" #"0" - #"9"] vs regset "a-z0-9")

Very nice Boleslav! What regex engine/syntax are you going for compatibility 
with (if any)?


Charset syntax is probably that way because it's a dialect, and Carl 
wanted a string as input to be easy, without escapes and such; just 
my guess.

Graham, the best book I know of on regexs is Jeff Friedl's 'Mastering 
Regular Expressions'. He has an email validating regex (i.e. it just 
matches the RFC822 spec for an email address) which is almost 5K 
IIRC.

Thanks Gregg. I started with some examples from http://regular-expressions.info, 
just to see, if I can do it, so after fixing bugs and adding some 
feature still missing, I'll see what next, if anything. There are 
already some incompatibilities - carret ^  cannot be used in rebol 
strings the way it's used in regex, so i'm using tilde ~ instead.

There are several different regex dialects. Are you following one 
of those, or making another?

(Running commentary as I read your code)

You should wrap your code in a context.

You should seperate the regex compilation phase from its application 
phase, and just write a wrapper that calls both in order. The compilation 
phase is often more complex than just applying the results, so if 
you are using the regex repeatedly you should just compile it once.

i like regset, in theory. You seem to be applying block parse syntax 
to strings - it could be simpler.

I wanted to do some basic regex set, some common denominator, partly 
as an exrcesise in parse and partly to stop people looking at rebol 
saying "it has no regex". so now it has ;)
So I'm not sure what dialect of regex is the best one.

Block parse syntax to strings - you mean that char! ? Yes, it's probably 
not doing anything, the code needs some cleanup.
I plan to wrap it in context, yes.

The char! 1 is useless. I am looking at that code now (reworking 
it).

Oldes, I though about just a translator from regex to parse rules 
and I'm not sure it will be easy, I'm using my 'tail-parse that matches 
rules in reversed order that is better for regex syntax. Maybe there's 
some other way.

Reverse order is better? I think you aren't backtracking right in 
your generated rules.

this is the problem with [some "a" "a"]. This is equivalent of "a*a" 
in regex which is perfectly valid, but problematic in parse. This 
is simple example, but it can get quite complicated so I'm not sure 
I can handle all cases. The reversed order seemed simpler. But you 
will probably prove me wrong :)

Are you supporting grouping? Haven't gotten to that point in the 
code yet.

Do regex dialects support decreasing character ranges in their sets?

grouping - just the bitsets created with regset, groups like [cat|dog] 
not yet supported

Which regex dialect does grouping with [ and ], I thought they used 
( and ).

Are you supporting . wildcard characters?

oh yes you're right...just an old rebol habit, using square brackets 
everywhere :)

wildcards - well dot is any character except newline

Right now it should support regex according tohttp://www.regular-expressions.info/quickstart.html

more or less

BTW, "a*a" is directly equivalent to [any "a" "a"], not some.

It still won't work directly.

Rebolek, I am rewriting the regset function. Do you want to support 
decreasing ranges or do you want the characters to be added individually 
lick they are with charset? I can do either.

; Version with support for decreasing ranges
regset: func [expression /local out negate? b e x] [
    negate?: false
    out: make bitset! []
    parse/all expression [
        opt ["~" (negate?: true)]
        some [
            "-" (insert out #"-") |
            b: skip "-" e: skip (
                b: first b  e: first e
                loop 1 + (
                    either b > e [b - x: e] [e - x: b]
                ) [
                    insert out x
                    x: 1 + x
                ]
            ) |
            x: skip (insert out first x)
        ]
    ]
    if negate? [out: complement out]
    out
]

; Version without support for decreasing ranges
regset: func [expression /local out negate? b e x] [
    negate?: false
    out: make bitset! []
    parse/all expression [
        opt ["~" (negate?: true)]
        some [
            "-" (insert out #"-") |
            b: skip "-" e: skip (
                b: first b  e: first e
                either b > e [
                    insert insert insert out b #"-" e
                ] [
                    loop 1 + e - b [
                        insert out b
                        b: 1 + b
                    ]
                ]
            ) |
            x: skip (insert out first x)
        ]
    ]
    if negate? [out: complement out]
    out
]

Most of the changes were made to make it faster and to use less memory 
overhead.

- It is faster for parse to match a one-character string than a character 
value.
- Insert is faster than union, and makes no temporaries.

- If you are capturing a single character, I think [a: skip (a: first 
a)] is faster than [copy a skip (a: first a)].

- Path access is slower than the equivalent native, so [first a] 
instead of [a/1].

- The fastest loop is loop, even with the math to calculate the number 
of times.

I may end up with the wrong data type to do the [x: 1 + x] rather 
than [x: x + 1], same with b in the second version.

Aside from the one-time bind, repeat may be faster than loop with 
a self-incremented index.

I haven't tried to support escaped characters or subrange checks 
yet. The subrange check may be faster to support by copy/part on 
the source, or faster yet by inlining the code into the greater regex 
engine. I'm not sure how the helper variables would be affected by 
the tasking support of R3, but they sure aren't reentrant on R2.

The standard backtracking of parse only happens upon alternation. 
To support the *, + and ? behavior of regexes, you either have to 
roll your own backtracking or have the compiler convert to using 
first and follow sets. In contrast to how your links describe the 
behavior of regex engines, it might be easier to make parse support 
lazy rather than greedy behavior of its iterators - they are greedy 
by default, but so much so that the first and follow sets shouldn't 
overlap.

It might be a good idea to run a peephole optimizer on the patterns 
before compiling them, to convert ones like "a*a" to "aa*".

It looks like repeat doesn't bind its argument, so it is definitely 
faster in this case.

; Version with support for decreasing ranges
regset: func [expression /local out negate? b e x] [
    negate?: false
    out: make bitset! []
    parse/all expression [
        opt ["~" (negate?: true)]
        some [
            "-" (insert out #"-") |
            b: skip "-" e: skip (
                b: first b  e: first e
                either b > e [
                    insert out e
                    repeat x b - e [insert out e + x]
                ] [
                    insert out b
                    repeat x e - b [insert out b + x]
                ]
            ) |
            x: skip (insert out first x)
        ]
    ]
    if negate? [out: complement out]
    out
]

; Version without support for decreasing ranges
regset: func [expression /local out negate? b e x] [
    negate?: false
    out: make bitset! []
    parse/all expression [
        opt ["~" (negate?: true)]
        some [
            "-" (insert out #"-") |
            b: skip "-" e: skip (
                b: first b  e: first e
                either b > e [
                    insert insert insert out b #"-" e
                ] [
                    insert out b
                    repeat x e - b [insert out b + x]
                ]
            ) |
            x: skip (insert out first x)
        ]
    ]
    if negate? [out: complement out]
    out
]

; Slightly faster
bitset-to-string: func [b [bitset!] /local s x] [
    s: copy either find b 0 ["^(00)"] [""]
    repeat x 255 [
        if find b x [append s to-char x]
    ]
    s
]

I'll look more at this tomorrow.

Hi Brian, thanks for support, I was out for a sleep :)

BrianH, what ? Repeat does bind its argument, doesn't it ?
>> repeat n 4 []
>> n
** Script Error: n has no value
** Near: n

Yeah, so it does. I wonder why the docs don't say (will be local) 
like it does for foreach. It still ends up faster than loop when 
you have to keep track of an index or a counter.

Brian, you've stated that  "It is faster for parse to match a one-character 
string than a character value." It seems to me that the opposite 
statement is true. (matching a char! is faster than matching a on-character 
string!)

It seems to me that the opposite _should_ be true, but parse converts 
the character to a string before matching it - no conversion is performed 
for string values. It's just one of those weird things.

This is one of those things that I actually profiled to determine 
for sure. Strange, but true.

my measurements show:

>> time-block [parse "a" ["a"]] 0.05
== 3.83615493774414E-7
>> time-block [parse "a" [#"a"]] 0.05
== 3.61204147338867E-7

, i.e. the opposite

Which version? Nevermind, my timing differences may just be a multitasking 
artifact.

>> rebol/version
== 1.3.2.3.1

Strange. When I tested before the difference turned out to be about 
the same as the overhead of string conversion. Quite the cooincidence. 
I guess I should have repeated my timings more :(

Too small a sample for a busy computer.

use can use time-block to make sure (it's on my site)

you can use...