Copyright (c) 2015-, All Rights Reserved by Kwanghoon Choi
(아래 강의 노트를 자유롭게 이용하되 다른 웹 사이트 등을 통한 배포를 금합니다.)
The C Programming Language 2nd Ed. by Kerninghan & Ritchie ( Ch.3, expand )
expand함수는 두 개의 char 배열 인자 s1과 s2를 받아 s1에 있는 문자열을 s2로 복사한다. 단, s1에 a-z나 0-9와 같은 문자열 축약 표기가 나타나면 이것을 풀어서 abc...xyz나 012...789를 s2에 복사한다.
void expand(char s1[], char s2[]);
문자열 s1의 각 문자를 하나씩 따라가면서 문자열 축약 표기를 고려해서 s2에 복사한다. 맨 처음 expand 함수가 호출되었을 때 상태를 EMPTY라고 하자. 이 상태에서 알파벳(a,...,z,A,...,Z)도 아니고 숫자(0,...,9)가 아니면 s2에 그대로 복사한다.
상태 STATE1에서 s1의 앞 문자를 읽어 s2로 복사하고 다른 상태 STATE2와 남은 s1의 문자열로 변경되는 과정을 STATE1: s1 ==> STATE2: s1'으로 표기하자. 문자열 표기법 c,s는 맨 처음 문자가 c이고 나머지가 s라는 의미로 약속하자.
[분석1]
EMPTY:'\0' ==> END (s2에 '\0'를 추가)
EMPTY: c,s ==> ALPHA,c : s (c가 'A'~'Z' 또는 'a'~'z'에 속하면)
EMPTY: c,s ==> DIGIT,c : s (c가 '0'~'9'에 속하면)
EMPTY: c,s ==> EMPTY : s (c가 알파벳도 아니고 숫자도 아니면, s2에 c를 추가)예를 들어, expand의 첫번째 문자열 s1이 "abc-ghi4-9!!"라고 가정하자.
[예제1]
EMPTY :'a',"bc-ghi4-9!!" (s2= )
==> ALPHA,'a' : 'b',"c-ghi4-9!!" (s2= )
알파벳 문자 c0로 시작하는 부분에 도달하면, 즉 상태가 ALPHA이고 그 알파벳은 c0인 경우다.
[분석2]
ALPHA,c0:'\0' ==> END (s2에 c0와 '\0'을 추가)
ALPHA,c0: '-',s ==> ALPHA_HYPHEN,c0 : s
ALPHA,c0: c,s ==> ALPHA,c : s (c가 'A'~'Z' 또는 'a'~'z'에 속하면, c0를 s2에 추가)
ALPHA,c0: c,s ==> DIGIT,c : s (c가 '0'~'9'에 속하면, c0를 s2에 추가)
ALPHA,c0: c,s ==> EMPTY : s (c가 하이픈, 알파벳, 숫자가 아니면, s2에 c0와 c를 추가)앞에서 들었던 예제를 이어가면,
[예제2]
ALPHA,'a' : 'b',"c-ghi4-9!!" (s2= )
==> ALPHA,'b' : "c-ghi4-9!!" (s2='a' )
==> ALPHA,'c' : "-ghi4-9!!" (s2='a','b' )
==> ALPHA_HYPHEN,'c' : 'g',"hi4-9!!" (s2='a','b' )알파벳 문자 c0와 -이 연달아 나오는 부분에 도달하면 ALPHA_HYPHEN 상태와 c0 문자인 경우다.
[분석3]
ALPHA_HYPHEN,c0:'\0' ==> END (s2에 c0와 '\0'를 추가)
ALPHA_HYPHEN,c0: c,s ==> ALPHA,c : s (c가 'A'~'Z' 또는 'a'~'z'에 속하고 c0 <= c이면, c0,...,ck,c 중 c0부터 ck를 s2에 추가)
ALPHA_HYPHEN,c0: c,s ==> ALPHA,c : s (c가 'A'~'Z' 또는 'a'~'z'에 속하고 c0 > c이면, c0와 '-'을 s2에 추가)
ALPHA_HYPHEN,c0: c,s ==> DIGIT,c : s (c가 '0'~'9'에 속하면, c0와 '-'을 s2에 추가)
ALPHA_HYPHEN,c0: c,s ==> EMPTY : s (c가 알파벳도 아니고 숫자도 아니면, c0,'-',c를 s2에 추가)앞에서 들었던 예제에 ALPHA_HYPEN 상태에 대한 규칙을 적용해보면,
[예제3]
ALPHA_HYPHEN,'c' : 'g',"hi4-9!!" (s2='a','b' )
==> ALPHA,'g' : 'h',"i4-9!!" (s2='a','b','c','d','e','f' )
==> ALPHA,'h' : 'i', "4-9!!" (s2='a','b','c','d','e','f','g' )
==> ALPHA,'i' : '4', "-9!!" (s2='a','b','c','d','e','f','g','h' )
==> DIGIT,'4' : '-', "9!!" (s2='a','b','c','d','e','f','g','h','i' )
숫자 문자 c0로 시작하는 부분에 도달하면, 즉 상태가 DIGIT이고 그 알파벳은 c0인 경우다.
[분석4]
DIGIT,c0:'\0' ==> END (s2에 c0와 '\0'를 추가)
DIGIT,c0: '-',s ==> DIGIT_HYPHEN,c0 : s
DIGIT,c0: c,s ==> ALPHA,c : s (c가 'A'~'Z' 또는 'a'~'z'에 속하면, c0를 s2에 추가)
DIGIT,c0: c,s ==> DIGIT,c : s (c가 '0'~'9'에 속하면, c0를 s2에 추가)
DIGIT,c0: c,s ==> EMPTY : s (c가 하이픈, 알파벳, 숫자가 아니면, s2에 c0와 c를 추가)
이번에는 DIGIT 상태에 대한 규칙을 적용해보면,
[예제4]
DIGIT,'4' : '-', "9!!" (s2='a','b','c','d','e','f','g','h','i' )
==> DIGIT_HYPHEN,'4' : '9', "!!" (s2='a','b','c','d','e','f','g','h','i' )
숫자와 -이 연달아 나오는 부분에 도달하면 DIGIT_HYPHEN 상태와 c0 문자인 경우다.
[분석5]
DIGIT_HYPHEN,c0:'\0' ==> END (s2에 c0와 '\0'를 추가)
DIGIT_HYPHEN,c0: c,s ==> ALPHA,c : s (c가 'A'~'Z' 또는 'a'~'z'에 속하면, c0와 '-'를 s2에 추가)
DIGIT_HYPHEN,c0: c,s ==> DIGIT,c : s (c가 '0'~'9'에 속하고 c0<=c이면, c0,...,ck,c 중 c0부터 ck를 s2에 추가)
DIGIT_HYPHEN,c0: c,s ==> DIGIT,c : s (c가 '0'~'9'에 속하고 c0>c이면, c0와 '-'을 s2에 추가)
DIGIT_HYPHEN,c0: c,s ==> EMPTY : s (c가 알파벳도 아니고 숫자도 아니면, c0,'-',c을 s2에 추가)마지막으로 DIGIT_HYPEN 상태에 대한 규칙(과 기타 규칙)을 적용해보면,
[예제5]
DIGIT_HYPHEN,'4' : '9', "!!" (s2='a','b','c','d','e','f','g','h','i' )
==> DIGIT_HYPHEN,'4' : '9', "!!" (s2='a','b','c','d','e','f','g','h','i','4','5','6','7','8' )
==> DIGIT,'9' : '!', "!" (s2='a','b','c','d','e','f','g','h','i','4','5','6','7','8' )
==> EMPTY : '!', "" (s2='a','b','c','d','e','f','g','h','i','4','5','6','7','8',9','!' )
==> EMPTY : '\0' (s2='a','b','c','d','e','f','g','h','i','4','5','6','7','8',9','!','!' )
==> EMPTY : END (s2='a','b','c','d','e','f','g','h','i','4','5','6','7','8',9','!','!','\0' )
단어 세기 프로그램이나 주석 제거 프로그램의 경우와 비교할 때 차이점은 상태에 따라 보관해야할 인자가 있다는 점이다. EMPTY 상태의 경우는 보관할 인자가 없지만, ALPHA,c0나 DIGIT,c0, ALPHA_HYPHEN,c0, DIGIT_HYPHEN,c0와 같이 그 외의 상태에서는 문자를 따로 보관해야 한다.
위에서 분석한 모든 경우([분석1] ~ [분석5])를 C코드로 옮겨보면 아래와 같다.
[끝]