Pattern Matching

Regular expression 이 [[ ]] 명령에 한에서 제한적으로 사용할 수 있다면 glob 문자 ( *, ?, [ ] ) 를 이용하는 패턴 매칭은 쉘 스크립트 전반에서 사용할 수 있습니다.

filename matching ( globbing )
case 문 에서
매개변수 확장에서 ( substring removal, search and replace )
[[ ]] 명령에서

Glob 문자의 의미

문자	의미
*	empty 를 포함해 모든 문자와 매칭됩니다. ( regex: `.*` )
?	임의의 문자 하나와 매칭됩니다. ( regex: `.`)
[ . . . ]	bracket 표현식 내의 하나의 문자와 매칭됩니다.

Bracket 표현식

표현식	의미
[XYZ]	X or Y or Z 문자에 대해 매칭됩니다.
[X-Z]	위 표현식을 `-` 문자를 이용해 range 로 나타낼수 있습니다.
[[:class:]]	POSIX character class 와 매칭됩니다.
[^ . . . ] [! . . . ]	`^` , `!` 문자는 NOT 을 의미합니다. 가령 [^XYZ] 이라면 XYZ 이외의 문자와 매칭됩니다.

- 를 일반 문자로 사용할 때는 두 문자 사이에 위치하지 않게 마지막에 위치시키면 되고 ], [ 문자는 처음에 위치시키면 됩니다.

Character Classes

문자들을 비슷한 의미를 가진 그룹으로 나누어놓은 것이 character classes 입니다. [[:alnum:]] 의미는 [ ] bracket 표현식 내에서 [:alnum:] 이라는 클래스가 사용되어 결과적으로 [A-Za-z0-9] 의미를 가지게 됩니다. 따라서 [[:upper:][:digit:]] 의 의미는 [A-Z0-9] 와 같게 됩니다.

Class	Represented	Description
[[:alnum:]]	`[A-Za-z0-9]`	Alphanumeric characters
[[:alpha:]]	`[A-Za-z]`	Alphabetic characters
[[:lower:]]	`[a-z]`	Lower-case alphabetic characters
[[:upper:]]	`[A-Z]`	Upper-case alphabetic characters
[[:digit:]]	`[0-9]`	Numeric characters
[[:xdigit:]]	`[0-9a-fA-F]`	Hexadecimal digit characters
[[:space:]]	`[ \t\n\v\f\r]`	All whitespace chars (form feed \x0c)
[[:blank:]]	`[ \t]`	Space, tab only
[[:punct:]]	`[!@#$%^&*(){}[]...]`	키보드에 있는 숫자, 대,소문자 빼고 모든 문자
[[:graph:]]	`[!-~]`	Printable and visible characters (ASCII 테이블에서 `!` 부터 `~` 까지)
[[:print:]]	`[ -~]`	Printable (non-Control) characters (ASCII 테이블에서 `space` 부터 `~` 까지)
[[:cntrl:]]	`[\x00-\x19\x7F]`	Control characters

[[:graph:]] 와 [[:print:]] 는 space 를 포함하고 안 하고 차이

사용예 )

$ ls
address.class  address.java  read.c  read.h  write.c  write.h

$ ls *.[ch]      # 확장자가 1 문자 이고 'c' 또는 'h' 인 파일
$ ls *.?         # 확장자가 1 문자인 파일
read.c  read.h  write.c  write.h

$ ls *.[^c]      # 확장자가 1 문자 이고 'c' 가 아닌 파일
read.h write.h

$ ls *.??*       # 확장자가 2 문자 이상인 파일
address.class  address.java
.............................................................

$ AA="inventory.tar.gz"

$ [[ $AA == *.tar.gz ]]; echo $?
0
$ [[ $AA == inventory.tar.?? ]]; echo $?
0

# 패턴에 공백을 사용하려면 escape 합니다.
$ AA='hello dog cat world'

$ [[ $AA == *dog\ cat* ]]; echo $?
0

Extended Pattern

glob 문자를 이용하는 패턴매칭은 매칭 능력이 제한적입니다. 이때 확장패턴을 함께 사용하면 regex 과 같은 매칭을 할 수 있습니다. 확장패턴 기능은 bash 에서만 제공되는 기능으로 [[ ]] 명령에서는 기본적으로 항상 사용할 수 있지만 prompt 상이나 shell 스크립트 파일을 실행할 때는 disable 됩니다. 이때는 shopt -s extglob 옵션을 이용해 enable 할 수 있습니다.

아래 테이블을 보면 사용 문법이 틀려서 그렇지 regex 에서 제공하는 기능과 같습니다.

표현식	의미
?(<PATTERN-LIST>)	주어진 패턴이 zero or one 발생하면 매칭됩니다.
*(<PATTERN-LIST>)	주어진 패턴이 zero or more 발생하면 매칭됩니다.
+(<PATTERN-LIST>)	주어진 패턴이 one or more 발생하면 매칭됩니다.
@(<PATTERN-LIST>)	주어진 패턴이 one 발생하면 매칭됩니다.
!(<PATTERN-LIST>)	`!` 문자는 not 의 의미로 주어진 패턴과 일치하지 않으면 매칭됩니다. ( 주의: empty 일 경우도 매칭에 포함됩니다. )

# 확장패턴 에서는 알파벳 문자 자리에 ?, *, [...] 패턴이 올수있다.
$ [[ abc == @(axc|ayc|a?c) ]] && echo yes     # @( )
yes
$ [[ abxc == ab?(x|y|z)c ]] && echo yes       # ?( )
yes
$ [[ abxyc == ab+(x|y|z)c ]] && echo yes      # +( )
yes

사용예 )

# *.jpg 파일을 제외하고 전부
$ echo !(*.jpg)

# *.jpg , *.gif , *.png 파일을 제외하고 전부 
$ echo !(*.jpg|*.gif|*.png)

--------------------------------------------

# 디렉토리에서 숫자로된 파일만 선택
$ echo ./+([0-9])
./0001 ./0002 ./0003 ...

$ echo ./foo+([0-9])
./foo12 ./foo123 ./foo1234 ...

--------------------------------------------

# ?(make) 은 make 가 zero or one 발생하면 매칭
$ [[ --file == @(-f|--?(make)file) ]] && echo yes
yes
[[ --makefile == @(-f|--?(make)file) ]] && echo yes
yes
$ [[ "-f" == @(-f|--?(make)file) ]] && echo yes
yes

------------------------------------------------

$ foo=127.0.0.1
$ [[ $(< /etc/hosts) == *$foo+([[:blank:]])localhost* ]] && echo yes
yes
# 위 명령은 다음 명령과 실행 결과가 같습니다.
$ cat /etc/hosts | grep -Eq "$foo[[:blank:]]+localhost" && echo yes
yes

----------------------------------------------

$ path='../..//./'
$ [[ $path == @(./|../|/) ]]; echo $?     # @( )
1
$ [[ $path == +(./|../|/) ]]; echo $?     # +( )
0

----------------------------------------------

# empty 값 매칭은 다음과같은 방법을 사용하면 됩니다.
$ foo=""
$ [[ $foo == ?(+([0-9])) ]] && echo yes      # ?( ) 사용
yes
$ [[ $foo == @(+([0-9])|'') ]] && echo yes   # "" or '' 사용
yes
$ [[ $foo == @(+([0-9])|) ]] && echo yes     # OK
yes

----------------------------------------------

$ AA=apple
$ [[ $AA == @(ba*(na)|a+(p)le) ]]; echo $?
0

$ AA=banana
$ [[ $AA == @(ba*(na)|a+(p)le) ]]; echo $?
0

$ AA=applebanana
$ [[ $AA == @(ba*(na)|a+(p)le) ]]; echo $?
1
$ [[ $AA == +(ba*(na)|a+(p)le) ]]; echo $?
0

패턴값에 변수를 사용할수도 있습니다.

# @(${methods// /|}) 는 결과가 @(GET|POST|PUT|HEAD...) 가 된다.

local i methods="GET POST PUT HEAD DELETE PATCH OPTIONS CONNECT TRACE"
for (( i = 1; i < ${#COMP_WORDS[@]}; i++ )); do
    [[ ${COMP_WORDS[i]} == @(${methods// /|}) ]] && break
done

확장패턴은 다음과 같이 nesting 해서 사용하는 것도 가능합니다.

$ val=aaxx
$ [[ $val == aa@(xx|yy@(1|2|3)) ]] && echo yes
yes

$ val=aayy
$ [[ $val == aa@(xx|yy@(1|2|3)) ]] && echo yes
$

$ val=aayy2
$ [[ $val == aa@(xx|yy@(1|2|3)) ]] && echo yes
yes

$ [[ "d" == @(a|b|@(c|@(d|e))) ]] && echo yes     # 다음 두 식은 같은 결과가 된다.
yes
$ [[ "d" == [abcde] ]] && echo yes
yes

확장패턴을 사용할땐 공백도 값에 포함되므로 주의해야 합니다.

$ val="--aa"

$ [[ $val == @(--aa|--bb) ]] && echo yes
yes
$ [[ $val == @( --aa|--bb) ]] && echo yes
$
$ [[ $val == @(--aa |--bb) ]] && echo yes
$

확장패턴 사용시 주의할 점

확장패턴을 매개변수 확장과 함께 사용할 경우 경우에 따라서 속도가 많이 느려질 수 있습니다. 이와같은 경우는 다른 방법을 사용해야 합니다. 이것은 regex 이 아니라 simple pattern matcher 라서 그렇다고 하는데 개선이 필요하다고 생각됩니다. 그리고 처리하려는 스트링의 사이즈가 클 경우는 외부 명령을 실행해서라도 ( 예를들면 sed ) regex 로 처리하는게 속도가 더 잘 나옵니다.

# 입력값에서 연이어지는 space, tab, newline 문자들을 하나의 space 로 치환하는 작업.

$ help=$( find --help )                 # "find --help" 출력값이 그렇게 큰것도 아닌데

$ echo "${help//+([$' \t\n'])/ }"       # 처리하지 못하고 정지해 버린다.

$ echo "${help//[$' \t\n']/ }"          # 확장패턴을 제거하면 문제가 없다.

$ help=$( find --help | head -n10 )     # 아주 작은 값에서만 겨우 동작.

$ echo "${help//+([$' \t\n'])/ }"
----------------------------------------

$ help=$( set -f; echo $help )          # 이럴경우는 다른방법을 사용하는게 빠르다.

$ help=$( <<< $help sed -Ez 's/[ \t\n]+/ /g' )

Quiz

* glob 문자를 이용해 현재 디렉토리에 있는 파일을 선택할 경우 기본적으로 . 으로 시작하는 hidden 파일은 선택되지 않는데요. hidden 파일도 선택하려면 어떻게 할까요?

# 현재 디렉토리 구성이 다음과 같을 경우
$ ls -a
./  ../  .aaa/  .bbb/  .ccc/  bar/  foo/  zoo/  .hidden.txt  file1.txt  file2.txt

$ for file in *; do echo "$file"; done             # hidden 이 아닌 모든 파일 선택
bar
file1.txt
file2.txt
foo
zoo

$ for file in .*[^.]*; do echo "$file"; done       # 모든 hidden 파일 선택
.aaa                                               # '...' '....' 같은 파일도 포함하려면
.bbb                                               # .*[^.]* ...*
.ccc
.hidden.txt

$ for file in * .*[^.]*; do echo "$file"; done     # hidden 파일 포함, 모든 파일 선택
bar
file1.txt
file2.txt
foo
zoo
.aaa
.bbb
.ccc
.hidden.txt

2 .

/usr/bin 디렉토리에서 qemu-* 파일을 리스팅 해보면 다음과 같은 형태의 실행파일 이름이 존재하는데요. 이중에서 이름 중간에 -system- 이 존재하지 않는 파일만 선택하려면 어떻게 할까요?

$ ls -l /usr/bin/qemu-*
. . .
/usr/bin/qemu-hppa                 /usr/bin/qemu-system-aarch64
/usr/bin/qemu-hppa-static          /usr/bin/qemu-system-alpha
/usr/bin/qemu-i386                 /usr/bin/qemu-system-arm
/usr/bin/qemu-i386-static          /usr/bin/qemu-system-avr
. . .

첫 번째와 같이 하면 안됩니다. 왜냐하면 !(system-) 패턴은 empty 일 경우도 매칭에 포함되기 때문입니다.

$ ls /usr/bin/qemu-!(system-)* | wc -l        # 틀린 방법
106

$ ls /usr/bin/qemu-* | wc -l
106

---------------------------------------

$ ls /usr/bin/qemu-!(system-*) | wc -l        # 맞는 방법
73

3 .

명령 라인에서 사용되는 옵션에는 -a ( short 옵션 ) 과 --foo ( long 옵션 ) 이 있습니다. 이중에서 short 옵션은 여러개를 붙여서 사용할 수가 있는데요. 가령 -a -b -c 세 개의 옵션이 있고 이중에서 -b 가 옵션 인수를 갖는다면 -acb 123 와 같이 작성할 수 있습니다.

스크립트에서 옵션을 처리할때 -b 옵션에서 사용되는 인수값 123 을 구하려면 -b 123 , -ab 123 , -cb 123 , -cab 123 와 같은 경우를 모두 처리해야 하는데요 어떻게 하면 될까요?

# 만약에 -d 옵션도 옵션 인수를 갖는다면 -!(-*)[bd] 와 같이 하면 되겠죠
foo() {
    if [[ $1 == -!(-*)b ]]; then        # !( ) 확장패턴 사용
        echo "-${1: -1} 옵션의 값은 $2 입니다."
    fi
}

# -!(-*)b 해석하는 방법
# 1. 먼저 -acb 옵션 스트링에서 처음과 마지막 문자가 각각 "-", "b" 이어야 한다.
# 2. 그다음 사이에있는 값이 "-*" 와 매칭이 안되면 된다.
--------------------------------------------------------

$ foo -b 123                              $ foo -ba 123
-b 옵션의 값은 123 입니다.                    $

$ foo -ab 123                             $ foo -abc 123
-b 옵션의 값은 123 입니다.                    $

$ foo -cb 123                             $ foo --b 123        # long 옵션도
-b 옵션의 값은 123 입니다.                    $                    # 매칭이 되면 안된다.

$ foo -cab 123                            $ foo --acb 123
-b 옵션의 값은 123 입니다.                    $

이번에는 옵션인수 값을 구하는 것이 아니라 단순히 특정 옵션이 설정되어 있는지 체크하는 것입니다.

bar() {
    if [[ $1 == -!(-*)b* ]]; then
        echo "-b 옵션이 설정되어 있습니다."
    fi
}
----------------------------------------------------

$ bar -b                                  $ bar --b
-b 옵션이 설정되어 있습니다.                   $

$ bar -ab                                 $ bar --ab
-b 옵션이 설정되어 있습니다.                   $

$ bar -abc                                $ bar --abc
-b 옵션이 설정되어 있습니다.                   $

4 .

*, ?, [ ] glob 문자를 이용하는 패턴매칭을 C 언어로 작성해 보는것입니다. 매칭에 성공하면 yes 를 출력하고 실패할 경우 no 를 출력하면 됩니다. 간단히 하기위해 [ ] 표현식은 [abcd] 형태만 구현합니다.

패턴매칭을 이용한 substitution 은 다음 주소에서 볼 수 있습니다.
https://gist.github.com/mug896/f4ea12b8cee4a707edf13fe4b7641496

$ gcc pattern.c

$ ./a.out 

Usage: ./a.out 'string' 'pattern'

$ ./a.out 'foobar' 'foo*'              $ ./a.out 'abcc' '*[xya]*[xyc]'
yes                                    yes
$ ./a.out 'foobar' '*bar'              $ ./a.out 'abcc' '*[xya]*[xyc]?'
yes                                    yes
$ ./a.out 'foobar' '*oba*'             $ ./a.out 'abcc' '*[xya]*[xyc]??'
yes                                    no
$ ./a.out 'foobar' 'fo*ar'
yes

$ [[ 'abcc' == *[xya]*[xyc]?? ]] && echo yes || echo no    # 맞는지 테스트
no

이런 종류의 프로그램은 되도록이면 strlen() 함수를 사용하지 않는쪽으로 작성하는게 좋습니다.

참고사이트: https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool matchhere(char *str, char *pat);

bool matchstar(char *str, char *pat)
{
    for ( int i = 0; str[i] != '\0'; i++) {
        if (matchhere(str + i, pat))
            return true;
    }
    return false;
}

bool matchhere(char *str, char *pat)
{
    int i = 0, j = 0;
    for ( ; str[i] != '\0' && pat[j] != '\0'; i++, j++)
    {
        if (pat[j] == '?') 
            continue;
        else if (pat[j] == '[') {
            bool match = false;
            for (j++; pat[j] != '\0' && pat[j] != ']'; j++)
                if (str[i] == pat[j]) match = true;
            if (! match) return false;
        }
        else if (pat[j] == '*') {
            while (pat[j] == '*') j++;
            if (pat[j] == '\0') return true;
            return matchstar(str + i, pat + j);
        }
        else if (str[i] != pat[j]) 
            return false;
    }
    while (pat[j] == '*') j++;
    return (str[i] == '\0' && pat[j] == '\0');
}

bool match(char *str, char *pat)
{
    if (str[0] == '\0' && pat[0] == '\0')
        return true;
    return matchhere(str, pat);
}

void usage(char *cmd)
{
    fprintf(stderr, "\nUsage: %s 'string' 'pattern'\n\n", cmd); 
    exit(1);
}

int main(int argc, char *argv[]) 
{
    if (argc < 3) usage(argv[0]);
    if (match(argv[1], argv[2])) {
        puts("yes");
        return 0;
    } else {
        puts("no");
        return 1;
    }
}

아래는 위와 동일한 코드인데 array 대신에 포인터를 사용한 것입니다. str[i] 와 같은 형태를 *str 로 바꾸기만 하면됩니다. 그러면 i, j 같은 인덱스 변수도 필요없고 좀 더 간단해 집니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool matchhere(char *str, char *pat);

bool matchstar(char *str, char *pat)
{
    for ( ; *str != '\0'; str++) {
        if (matchhere(str, pat))
            return true;
    }
    return false;
}

bool matchhere(char *str, char *pat)
{
    for ( ; *str != '\0' && *pat != '\0'; str++, pat++)
    {
        if (*pat == '?') 
            continue;
        else if (*pat == '[') {
            bool match = false;
            for (pat++; *pat != '\0' && *pat != ']'; pat++)
                if (*str == *pat) match = true;
            if (! match) return false;
        }
        else if (*pat == '*') {
            while (*pat == '*') pat++;
            if (*pat == '\0') return true;
            return matchstar(str, pat);
        }
        else if (*str != *pat) 
            return false;
    }
    while (*pat == '*') pat++;
    return (*str == '\0' && *pat == '\0');
}

bool match(char *str, char *pat)
{
    if (*str == '\0' && *pat == '\0')
        return true;
    return matchhere(str, pat);
}

void usage(char *cmd)
{
    fprintf(stderr, "\nUsage: %s 'string' 'pattern'\n\n", cmd); 
    exit(1);
}

int main(int argc, char *argv[]) 
{
    if (argc < 3) usage(argv[0]);
    if (match(argv[1], argv[2])) {
        puts("yes");
        return 0;
    } else {
        puts("no");
        return 1;
    }
}

uftrace 명령을 이용하면 함수 호출 관계를 한눈에 볼 수 있습니다. [사용법]

# -O2 최적화 옵션을 적용하면 출력 결과가 달라지는 것을 볼 수 있습니다.
$ gcc -pg -g -O2 pattern.c 

$ uftrace -a ./a.out 'abcc' '*[xya]*[xyc]??' 
no
# DURATION     TID     FUNCTION
   2.164 us [  5783] | __monstartup();
   0.903 us [  5783] | __cxa_atexit();
            [  5783] | main(3, 0x7ffc4044b658) {
            [  5783] |   match("abcc", "*[xya]*[xyc]??") {
            [  5783] |     matchhere("abcc", "*[xya]*[xyc]??") {
            [  5783] |       matchhere("abcc", "[xya]*[xyc]??") {
   2.397 us [  5783] |         matchhere("bcc", "[xyc]??") = 0;
   0.309 us [  5783] |         matchhere("cc", "[xyc]??") = 0;
   0.241 us [  5783] |         matchhere("c", "[xyc]??") = 0;
   4.690 us [  5783] |       } = 0; /* matchhere */
   0.282 us [  5783] |       matchhere("bcc", "[xya]*[xyc]??") = 0;
   0.198 us [  5783] |       matchhere("cc", "[xya]*[xyc]??") = 0;
   0.200 us [  5783] |       matchhere("c", "[xya]*[xyc]??") = 0;
   6.660 us [  5783] |     } = 0; /* matchhere */
 140.324 us [  5783] |   } = 0; /* match */
  14.180 us [  5783] |   puts("no") = 3;
 157.326 us [  5783] | } = 0; /* main */