wildcard matching in rexx

No Language here - just algorithms!
Previous topicNext topic

Topic Author
enrico-sorichetti
Global Moderator
Global Moderator
Posts: 887
Joined: Wed Sep 11, 2013 3:57 pm

wildcard matching in rexx

Post by enrico-sorichetti » Mon Sep 05, 2016 5:05 am

the * matches 0 or more chars
the ? matches 1 char

Code: Select all

#! /usr/bin/env rexx

Trace "O"
signal  on  novalue name novalue
signal  on  halt    name halt
signal  on  syntax  name syntax
numeric digits 8

    Pattern = 'A?C*D??E*'
    String  = 'ABCxxDyyEzz'

    Say "match( '"String"',  '"Pattern"') =>" match( String,  Pattern)

    Pattern = 'A?C*D??E*'
    String  = 'ABCxxDyyyEzz'
    Say "match( '"String"',  '"Pattern"') =>" match( String,  Pattern)

    Pattern = 'A?C*D??E*'
    String  = 'ABCxxDyyEzz'
    stages  = compile(pattern)
    Say "fastmatch( '"String"',  '"stages"') =>" fastmatch( String,  stages)

    Pattern = 'A?C*D??E*'
    String  = 'ABCxxDyyyEzz'
    stages  = compile(pattern)
    Say "fastmatch( '"String"',  '"stages"') =>" fastmatch( String,  stages)

exit
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
match:procedure
    -- trace "I"
    parse arg string, pattern, ?char, ?wild, ?escape
    if  ?char = "" then ,
        ?char = "?"
    if  ?wild = "" then ,
        ?wild = "*"
    if  ?escape = "" then ,
        ?escape = "\"

    stages  = compile(pattern, ?char, ?wild, ?escape)

    string  = string || "ff"x
    strlen  = length(string)
    index   = 1

    do while ( stages \= "" )
        parse var stages func parm stages
        interpret "index = "func"('"string"','"strlen"','"parm"','"index"')"
        -- Trace "O"
        if  index = (-1)  then ,
            return 0
    end
    return 1

return 0

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
fastmatch:procedure
    -- trace "I"
    parse arg string, stages

    string  = string || "ff"x
    strlen  = length(string)
    index   = 1

    do while ( stages \= "" )
        parse var stages func parm stages
        interpret "index = "func"('"string"','"strlen"','"parm"','"index"')"
        if  index = (-1)  then ,
            return 0
    end
    return 1

return 0

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
chklen:
    -- Trace "I"
    parse arg ?string, . , ?strlen, .

    if  length(?string) < ?strlen then ,
        return (-1)
    return  1

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
compare :
    -- Trace "I"
    parse arg ?string, ?strlen, ?needle, ?index

    if  ?index + length(?needle) - 1 > ?strlen  then ,
        return (-1)

    if  substr(?string, ?index, length(?needle)) = ?needle then ,
        return ?index + length(?needle)

return (-1)

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
advance:
    -- Trace "I"

    parse arg ?string, ?strlen, ?count, ?index,

    if  ?index + ?count - 1 <= ?strlen then ,
        return ?index + ?count

return (-1)

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
locate:
    -- Trace "I"

    parse arg ?string, ?strlen, ?needle, ?index

    if  ?index + length(?needle) - 1 > ?strlen  then ,
        return (-1)

    ?chindx = pos(?needle, ?string, ?index)
    if  ?chindx >= ?index then ,
        return ?chindx + length(?needle)

return (-1)

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
compile:procedure
    -- trace "I"
    parse arg pattern, ?char, ?wild, ?escape
    if  ?char = "" then ,
        ?char = "?"
    if  ?wild = "" then ,
        ?wild = "*"
    if  ?escape = "" then ,
        ?escape = "\"

    pattern = pattern || "ff"x

    strlen = 0
    stages = ""

    escape = 0
    dofind = 0
    doskip = 0

    token = ""
    index = 1
    do while ( index <= length(pattern) )

        ch = substr(pattern, index, 1)

        if escape then do
            escape = 0
            strlen += 1
            if  doskip > 0 then do
                stages = stages "advance" doskip
                doskip = 0
            end
            if  dofind > 0 then do
                stages = stages "locate" token
                dofind = 0
                iterate
            end
            token = token || ch
            index +=1
            iterate
        end

        if  ch = ?escape then do
            escape = 1
            index += 1
            iterate
        end

        select
            when ( ch = ?wild ) then do
                if  token \= "" then do
                    stages = stages "compare " token
                    token = ""
                end
                dofind += 1
            end
            when ( ch = ?char) then do
                strlen += 1
                if  token \= "" then do
                    stages = stages "compare " token
                    token = ""
                end
                doskip += 1
            end
            otherwise do
                strlen += 1
                if  doskip > 0 then do
                    stages = stages "advance" doskip
                    doskip = 0
                end
                if  dofind > 0 then do
                    stages = stages "locate" ch
                    dofind = 0
                    index +=1
                    iterate
                end
                token = token || ch
            end
        end
        index += 1
    end

    if  index \= length(pattern) + 1 then ,
        return -1

    if  token \= "" then ,
        stages = stages "compare " token

    stages = "chklen" strlen stages

    return space(stages)

return  (-1)

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
logic_error:
say  "** "copies("- ",35)
say  "** Logic error at line '"sigl"' "
say  "** "
exit

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
syntax:
say  "** "copies("- ",35)
say  "** ON syntax  trapped, line '"sigl"' var '"condition("D")"' "
say  "** "
exit

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
novalue:
say  "** "copies("- ",35)
say  "** ON novalue trapped, line '"sigl"' var '"condition("D")"' "
say  "** "
exit

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
halt
say  "** "copies("- ",35)
say  "** ON halt    trapped, line '"sigl"' var '"condition("D")"' "
say  "** "
exit

quick and dirty,
it compiles the pattern, and then executes the result


cheers
enrico
When I tell somebody to RTFM or STFW I usually have the page open in another tab/window of my browser,
so that I am sure that the information requested can be reached with a very small effort 8-)


Imran Lamba
Registered Member
Posts: 13
Joined: Tue Jan 19, 2016 11:49 am

Re: wildcard matching in rexx

Post by Imran Lamba » Tue Sep 06, 2016 8:28 pm

enrico-sorichetti wrote: it compiles the pattern, and then executes the result
I am sorry but I did not understand this, What is the meaning of "compiles"?




Topic Author
enrico-sorichetti
Global Moderator
Global Moderator
Posts: 887
Joined: Wed Sep 11, 2013 3:57 pm

Re: wildcard matching in rexx

Post by enrico-sorichetti » Tue Sep 06, 2016 9:00 pm

I am sorry but I did not understand this, What is the meaning of "compiles"?
it analyses the pattern and builds a sequence of stages to be carried on against the string to be checked

forget about the position for a while
the pattern "A%B"
will compile to
strcmp A advance 1 strcmp B


the pattern "A*B"
will compile to
strcmp A locate B

I will shortly edit my post with an updated script


cheers
enrico
When I tell somebody to RTFM or STFW I usually have the page open in another tab/window of my browser,
so that I am sure that the information requested can be reached with a very small effort 8-)


Imran Lamba
Registered Member
Posts: 13
Joined: Tue Jan 19, 2016 11:49 am

Re: wildcard matching in rexx

Post by Imran Lamba » Tue Sep 06, 2016 10:07 pm

Thanks Enrico. That's an advance use of REXX... I'm trying to understand it... :)




Topic Author
enrico-sorichetti
Global Moderator
Global Moderator
Posts: 887
Joined: Wed Sep 11, 2013 3:57 pm

Re: wildcard matching in rexx

Post by enrico-sorichetti » Thu Sep 08, 2016 10:26 pm

Not that advanced ( from a REXX utilisation point of view ) :)
it uses very little of the REXX power - just the basics functions

it is more an attempt to prototype an alternate approach to wildcard matching
in a way that could be easily ported to a different language
COBOL, PL/1, probably FORTRAN


cheers
enrico
When I tell somebody to RTFM or STFW I usually have the page open in another tab/window of my browser,
so that I am sure that the information requested can be reached with a very small effort 8-)

Previous topicNext topic

Return to “Programming Algorithms.”