Today's Question:  What are you most afraid of as a programmer?        GIVE A SHOUT

Technical Article => Programming =>  Algorithm

How regular expression works

  Peter      2012-06-25 05:23:41      1,771    0    0

Rob Pike wrote 30 lines of codes to realize a simple regular expression matcher in his book The practice of Programming. This piece of code is really cool. Let's take a look at the code.

Meaning of different characters.

Character
Meaning
c
General character
.
Match any single character
^
Match start of a string
$
Match end of a string

*

Match zero or many occurrences of a character


/*match :Test the regexp in text*/
int match(char* regexp,char* text)
{
    if(regexp[0] == '^')
        return matchhere(regexp+1,text);
    do{ /*Check the string even if it is an empty string*/
        if(matchhere(regexp,text))
            return 1;
    }while(*text++ !='\0');
    return 0;
}
/*matchhere :Test regexp at the beginning of text*/
int matchhere(char* regexp,char* text)
{
    if(regexp[0] == '\0')
        return 1;
    if(regexp[1] == '*')
        return matchstar(regexp[0],regexp+2,text);
    if(regexp[0] == '$' && regexp[1] == '\0')
        return *text == '\0';
    if(*text != '\0' && (regexp[0] == '.' || regexp[0] == *text))
        return matchhere(regexp+1,text+1);
    return 0;
}
/*matchstar :Match zero or many occurrences of character c in text*/
int matchstar(int c,char* regexp,char* text)
{
    do{
        if(matchhere(regexp,text))
            return 1;
    }while(*text != '\0' && (*text++ == c || c == '.'));
    return 0;
}

Source : http://blog.csdn.net/denieljean/article/details/6611661

C REGULAR EXPRESSION IMPLEMENTATION ROB PIKE

  SAVE AS PDF   MARK AS READ   MARK AS IMPORTANT

Share on Facebook  Share on Twitter  Share on Google+  Share on Weibo  Share on Reddit  Share on Digg  Share on Tumblr    Delicious

  RELATED


  0 COMMENT


No comment for this article.


  WRITE ARTICLE

Objects belong to our generation

By sonic0002
What are you using to listen to music today? iPod, iPhone or other MP3 players? Have you ever seen the above object? Have you ever seen above music cassette tapes in real? I believe these are the objects beloging to people born in 70s and 80s. Do you know what are the connection between the above tw