사용 개념: 정규 표현식의 기본 다섯 식, 우선순위, 대수 법칙.
말로 된 토큰 설명을 식으로 옮기는 문제는 같은 차례로 푼다. ① 토막 나누기: 설명을 “처음에 오는 것, 그다음에 오는 것”으로 끊는다 ② 토막마다 고르기: 그 자리에 올 수 있는 것을 |로 잇는다 ③ 횟수 정하기: 그 토막이 몇 번 오는지에 따라 그대로, *, +, 또는 \(\epsilon\)과의 선택을 고른다 ④ 맞는 예와 틀린 예 넣어 보기1.
문제 2~4는 자주 쓰는 토큰 셋(정수, 식별자, 실수)이다. \(digit = 0 \mid 1 \mid \cdots \mid 9\), \(letter = a \mid \cdots \mid z \mid A \mid \cdots \mid Z\)로 둔다.
문제 p1 · 우선순위 읽기
a|bc*에 괄호를 모두 채워 쓰고, 이 식이 가리키는 문자열 가운데 길이 3 이하인 것을 모두 쓰라. ac, bcbc는 여기에 드는가?
풀이 전략: 가장 먼저 묶이는 것부터 안쪽 괄호를 친다. 반복 → 연결 → 선택 순서다.
답
- 반복 묶기:
*는 바로 앞의c에만 걸린다.a|b(c*). - 연결 묶기:
b와(c*)를 잇는다.a|(b(c*)). - 선택: 맨 바깥이
|다. “a 하나” 또는 “b 뒤에 c가 0번 이상”. - 늘어놓기:
a,b,bc,bcc.
ac는 들지 않는다. (a|b)c*로 읽었을 때만 든다. bcbc도 들지 않는다. a|(bc)*로 읽었을 때만 든다.
변형: ab*|c와 (ab)*|c에서 abab는 어느 쪽에 드는가? (답: 뒤쪽에만 든다.)
문제 p2 · 정수
“정수는 숫자가 하나 이상 이어진 것이다(0, 11, 1530)”를 기본 다섯 식만으로 적으라.
풀이 전략: “하나 이상”은 +다. 기본 식에는 +가 없으므로 \(r^+ = rr^*\)로 푼다.
답
- 토막 나누기: 토막은 “숫자” 하나뿐이다.
- 횟수 정하기: 하나 이상이므로 \(digit^+\).
- 기본 식으로: \(Integer = digit\;digit^*\).
- 넣어 보기:
0,11,1530은 맞는다. 빈 문자열은 맞지 않는다.007도 맞는다. 설명이 “숫자가 하나 이상”이라고만 했기 때문이다.
변형: 앞에 쓸데없는 0이 붙지 않는 정수(0은 되고 007은 안 된다)를 적으라.
변형의 답
\(0 \mid nonzero\;digit^*\), 여기서 \(nonzero = 1 \mid 2 \mid \cdots \mid 9\). “0 하나”이거나 “0이 아닌 숫자로 시작해 숫자가 이어진 것”이다.
문제 p3 · 식별자
“식별자는 글자, 숫자, 밑줄이 하나 이상 이어진 것이고 숫자로 시작하지 않는다(aaa, i, funcAtoB, _var, main, variable123)”를 적으라.
풀이 전략: “~로 시작하지 않는다” 같은 조건은 첫 자리를 따로 떼어 토막 둘로 나눈다.
답
- 토막 나누기: 첫 글자 하나, 그리고 나머지.
- 토막마다 고르기: 첫 글자는 \(letter \mid \_\). 나머지 자리는 \(letter \mid digit \mid \_\).
- 횟수 정하기: 첫 글자는 한 번. 나머지는 없어도 되므로
*. - 식: \(Identifier = (letter \mid \_)(letter \mid digit \mid \_)^*\).
- 넣어 보기: 예 여섯 개가 모두 맞는다.
123variable은 첫 자리에서 걸린다.
흔한 오답은 \((letter \mid digit \mid \_)^+\)다. 숫자로 시작하는 것까지 받는다.
문제 p4 · 실수
다음이 모두 맞는 식을 적으라: 0.5, 3.14, -6.111, 1.0E+3, 100.0, -10.53E-1, 9.123E3.
풀이 전략: 예를 나란히 놓고 “늘 있는 토막”과 “있을 때도 없을 때도 있는 토막”을 가른다. 있어도 없어도 되는 토막은 \(\epsilon\)과의 선택으로 적는다.
답
- 토막 나누기: 부호 / 점 앞의 숫자들 / 점 / 점 뒤의 숫자들 / 지수.
- 부호:
-가 있거나 없다. \((- \mid \epsilon)\). - 숫자들: 점 앞뒤 모두 하나 이상. \(digit^+\;.\;digit^+\).
- 지수: 통째로 있거나 없다. 있으면
E, 있거나 없는 부호(+또는-), 숫자 하나 이상. \((\epsilon \mid E(+ \mid - \mid \epsilon)\,digit^+)\). - 식: \(Float = (- \mid \epsilon)\;digit^+\;.\;digit^+\;(\epsilon \mid E(+ \mid - \mid \epsilon)\,digit^+)\).
- 넣어 보기: 일곱 예가 모두 맞는다.
5,.5,5.,1.0E는 맞지 않는다.
답은 하나가 아니다. 예만으로는 .5나 +1.0을 받을지 정해지지 않는다. 받게 하려면 그 토막의 횟수와 선택지를 바꾼다1.
문제 p5 · 법칙으로 줄이기
(가) \((a \mid \epsilon)^*\)를 더 짧게 쓰라. (나) \((a^*)^*b \mid (a^*)^*c\)를 더 짧게 쓰라. (다) \((a \mid b)^*\)와 \(a^* \mid b^*\)는 같은가?
풀이 전략: 대수 법칙 표에서 모양이 맞는 줄을 찾아 한 번에 하나씩 쓴다. 같은지 아닌지는 한쪽에만 드는 문자열을 찾아본다.
답
(가) \(a^*\). 반복 안의 \(\epsilon\)은 빼도 된다(\(r^* = (r \mid \epsilon)^*\)).
(나) 멱등: \((a^*)^* = a^*\)이므로 \(a^*b \mid a^*c\). 분배를 거꾸로: \(a^*(b \mid c)\).
(다) 다르다. ab는 \((a \mid b)^*\)에는 들고 \(a^* \mid b^*\)에는 들지 않는다. 앞의 식은 자리마다 a와 b를 새로 고르고, 뒤의 식은 a만 되풀이하거나 b만 되풀이한다.
변형: \(ab \mid ac \mid a\)를 분배 법칙으로 묶으라. (답: \(a(b \mid c \mid \epsilon)\). 마지막 \(a\)는 \(a\epsilon\)으로 본다.)
문제 p6 · 실전 표기를 기본 식으로
파이썬 re의 표기를 기본 다섯 식으로 풀어 쓰라. 알파벳은 \(\{a, b\}\)다. (가) a?b+ (나) [ab]{2} (다) (ab){1,2}
풀이 전략: ?는 \(\epsilon\)과의 선택, +는 \(rr^*\), [ ]는 |로 잇기, {n}은 \(n\)번 이어 쓰기로 바꾼다.
답
(가) \((a \mid \epsilon)bb^*\)
(나) \((a \mid b)(a \mid b)\)
(다) \(ab \mid abab\). 또는 \(ab(ab \mid \epsilon)\).