ENE4014 프로그래밍 언어

총평

학부 3학년 프로그래밍 언어 수업의 과제 두 개다. Homework1은 C++로 FSA/DFA 변환, LR 파싱 테이블 구동기, 정규식→NFA→DFA 매처를 만드는 것이고(각 50점), Homework2는 Haskell로 소수 찾기·동전 뒤집기·직소 스도쿠를 푸는 것이다(30/30/40점). 전체 24커밋, 2017-05-29부터 2017-06-15까지 18일. 벤더링된 외부 코드도, 커밋된 빌드 산출물도, 시크릿도 없다. 레포 위생 자체는 깨끗하다.

직접 빌드하고 돌려본 결과, README에 적힌 예제 입력은 여섯 문항 전부 정확히 통과한다. 정규식 매처는 명세의 다섯 예제(ab|cd, a(b|c)d, a.*b, (a(b.c)*|de)f, [abc]*def)를 예시된 문자열 그대로 맞히고, LR 파서는 제공된 표현식 문법 표에서 (I+I)*I를 받아들이고 I+·()·I)를 거절한다. 여기까지는 진짜로 동작하는 코드다.

문제는 그 바깥이다. 가장 치명적인 것은 FSA의 인식 언어가 입력 파일의 행 순서에 따라 달라진다는 것이다. 같은 오토마톤에서 #(엡실론) 전이 한 줄의 위치만 바꾸면 ab가 거절됐다가 수용된다. 부분집합 구성(subset construction)이라고 부를 수 없는 구현이다. 정규식 쪽에서는 *가 연속되면 상태가 서로 병합되어 a*b*가 ba를 받아들인다. LR 파서는 표에 없는 상태를 만나면 find() 결과를 검사하지 않고 역참조해 SIGSEGV로 죽는다. 셋 다 재현했다.

가장 잘한 것은 커밋 94ba7d6의 "Fix fsa error"다. 엡실론 폐포 재귀의 방문 검사가 상태 번호 집합에 배열 인덱스를 찾고 있던 실제 버그를 스스로 발견해 고쳤다. 남이 지적해주지 않으면 못 찾는 종류의 버그다. Homework2에서는 parseSection이 인자를 무시하고 전역 테스트 상수를 읽던 버그를 역시 스스로 잡았다(2804029).

Haskell 과제에 .py 파일이 같이 들어 있는 건 사실이지만, git 타임스탬프상 파이썬이 나중이다. 프로토타입이 아니라 디버깅용 역이식물이고, 제출물을 파이썬으로 바꿔치기한 흔적은 없다. 대신 진짜 문제는 따로 있다 — 스도쿠 Haskell 코드의 자료 모델이 가변 격자 파이썬 풀이 그대로다.

과제	주제	핵심 판정	등급
1-1 · 50pt	FSA → DFA 변환	제공 데이터 4종은 통과. 그러나 인식 언어가 입력 파일 행 순서에 의존	C+
1-2 · 50pt	LR 파싱 테이블 구동	shift/reduce/goto/accept/error 전부 정확. 표에 없는 상태에서 세그폴트	B+
1-3 · 50pt	정규식 → DFA	명세 예제 5종 전부 통과. `*`가 연속되면 상태 병합	B-
2-1 · 30pt	소수 찾기	지연 무한 리스트 + `take`. 관용적이지만 소수 판정이 O(n)	B+
2-2 · 30pt	동전 뒤집기	항상 종료·항상 전부 H. 그러나 명세 예제 3개 중 1개가 불일치	B-
2-3 · 40pt	직소 스도쿠	예제 퍼즐 정답. 센티널·인덱싱 등 자료 모델이 파이썬 이식	B-

Homework 1 — C++ : FSA, LR 파서, 정규식

스켈레톤(*_main.cc)이 주어지고 fsa.cc, lr_parser.cc/.h, regexp_matcher.cc를 채우는 과제다. 마감일(2017-05-31) 당일 새벽 06:32부터 23:28까지, 열네 개 커밋으로 전부 작성됐다. make는 경고 없이 통과한다(Apple clang 21, -std=c++0x).

치명적

FSA가 인식하는 언어가 입력 파일의 행 순서에 따라 달라진다

next_lambda는 어떤 상태의 엡실론 전이들이 그 상태의 블록 맨 앞에 연속해서 놓여 있다고 가정한다. 첫 줄이 엡실론이 아니면 즉시 break하고, 그 상태의 엡실론 폐포는 통째로 누락된다. 이건 정렬 요구사항이 아니라 그냥 숨은 전제다 — 명세 어디에도 입력 파일이 정렬되어 있다는 말은 없다.

Homework1/fsa.cc:110–112

for (auto element : vector<FSATableElement>(begin + start, end)) {
    if (not element.str.empty() or element.state != current)
        break;   // ← 상태의 첫 행이 엡실론이 아니면 폐포를 통째로 포기

같은 오토마톤(1 -a→ 2, 2 -z→ 2, 2 -ε→ 3, 3 -b→ 4, 수용상태 4)을 행 순서만 바꿔 두 파일로 만들어 돌린 결과다. 위는 2 2 z가 먼저, 아래는 2 3 #이 먼저다.

$ printf '4\n1 2 a\n2 2 z\n2 3 #\n3 4 b\n' | ./fsa t1.txt
input: 'ab'  = X          input: 'azb' = X
$ printf '4\n1 2 a\n2 3 #\n2 2 z\n3 4 b\n' | ./fsa t1b.txt
input: 'ab'  = O          input: 'azb' = O

제공된 data/fsa10.txt·fsa11.txt와 README 예제가 우연히 엡실론 행을 앞에 두고 있어서 이 버그가 드러나지 않는다. isAccept 끝에 붙은 사후 엡실론 폐포(fsa.cc:179–185)가 마지막 상태에 대해서만 한 번 더 보정해 주기 때문에 짧은 예제에서는 더더욱 티가 안 난다. 채점 데이터가 하나만 달랐어도 그대로 터졌을 코드다.

치명적

NFA 판별이 "직전 행"만 비교한다 — 떨어져 있는 비결정성을 놓친다

isNFA()는 비결정성을 찾기 위해 각 행을 바로 앞 행 하나와만 비교한다. pElements가 매 반복마다 덮어쓰이기 때문이다. (1,a)→2와 (1,a)→3 사이에 (1,b)→1 한 줄만 끼어 있으면 DFA로 오판하고, buildDFA()는 부분집합 구성을 하지 않은 채 {2,3} 같은 다중 상태를 표에 넣는다. 그런데 표의 키는 단일 상태 집합뿐이라, 다음 글자에서 조회가 실패하고 조용히 거절한다.

Homework1/fsa.cc:55–64

for (auto ch : element.str) {
    if (pElements.state != NOT_INIT) {
        if (pElements.state == element.state &&
            pElements.str[0] == ch) {
            return true;
        }
    }
    pElements = element;          // ← 직전 한 행만 기억. 그 이전은 전부 잊는다
    pElements.str[0] = ch;
}

# 1-a→2, 1-b→1, 1-a→3, 2-b→4, 3-b→4  (수용상태 4).  'ab'와 'bab'는 수용되어야 한다.
$ printf '4\n1 2 a\n1 1 b\n1 3 a\n2 4 b\n3 4 b\n' | ./fsa t2.txt
input: 'ab'  = X          input: 'bab' = X       # 두 'a' 행이 떨어져 있음 → DFA로 오판
$ printf '4\n1 2 a\n1 3 a\n1 1 b\n2 4 b\n3 4 b\n' | ./fsa t2b.txt
input: 'ab'  = O          input: 'bab' = O       # 두 'a' 행이 붙어 있음 → NFA로 인식

과제 요구사항은 "RunFSA와 BuildFSA가 DFA와 NFA 정의를 모두 처리할 것"이다. 처리하긴 하는데, 어느 쪽으로 처리할지를 파일 안의 줄 순서가 결정한다.

중대

`elements[j]` 범위 밖 읽기 — ASan으로 재현

j는 element.next_state를 시작 상태로 갖는 첫 원소의 인덱스를 찾는 루프의 결과다. 그런 원소가 없으면(= 나가는 전이가 없는 상태, 즉 대개 수용 상태) j == elements.size()가 되는데, 그 값으로 바로 elements[j].str을 읽는다. 같은 파일 105행의 next_lambda 진입부에는 if (start >= elements.size()) return; 가드가 있는데 여기엔 없다.

Homework1/fsa.cc:120–129

int j;
for (j = 0; j < elements.size(); j++) {
    if (elements[j].state == element.next_state) {
        break;
    }
}                                  // ← 못 찾으면 j == elements.size()

if (elements[j].str.empty()) {     // ← 그대로 범위 밖 읽기
    next_lambda(from, j);
}

$ g++ -std=c++11 -g -fsanitize=address -o re_asan regexp_main.cc regexp_matcher.cc fsa.cc
$ echo a | ./re_asan '(a)'
ERROR: AddressSanitizer: heap-buffer-overflow ... READ of size 1
  #3 FiniteStateAutomaton::next_lambda(...) const fsa.cc:127
  #4 FiniteStateAutomaton::next_string(...)  fsa.cc:88
  #8 BuildRegExpMatcher(char const*, RegExpMatcher*) regexp_matcher.cc:35

정규식 (a) — 명세 예제보다 단순한 입력 — 하나로 터진다. 릴리스 빌드에서는 대개 조용히 지나가기 때문에 제출 당시엔 드러나지 않았을 것이다.

중대

LR 파서: `find()` 결과를 검사 없이 역참조 → SIGSEGV

안쪽 find(nextInput)은 end()와 제대로 비교해서 오류 입력을 false로 돌려준다. 그런데 바깥쪽 parse_table.find(stack[stack_index])는 검사 없이 ->second를 한다. 표에 행이 하나도 없는 상태로 shift되는 순간 널 역참조다. 같은 패턴이 68행·76행의 rules.find(ruleNum)->second에도 있다.

Homework1/lr_parser.cc:53–55

auto it = parse_table.find(stack[stack_index])->second.find(nextInput);

if (it != parse_table.find(stack[stack_index])->second.end()) {

$ printf '2 1\n0 a S 5\n0 $ A 0\n1 -1 1\n' > bad.txt      # 상태 5에 해당하는 행이 없는 표
$ echo a | ./lr_parser bad.txt ; echo $?
139                                                      # SIGSEGV
# ASan: stack-buffer-overflow READ ... #3 LRParser::run(...) lr_parser.cc:53

같은 이유로 46행의 str[str_index]도 경계 검사가 없다. 제공된 표는 상태 0–11이 모두 등장하므로 data/test_parser.txt로는 절대 재현되지 않는다.

중대

정규식: ``가 연속되면 상태가 병합되어 `ab*`가 `ba`를 받아들인다

* 처리는 직전 상태와 현재 상태 사이에 양방향 엡실론 간선을 놓는다. 별표가 하나면 "건너뛰기 + 되돌아가기"로 올바르게 동작하지만, 양방향 엡실론은 두 상태를 동치로 만든다. 별표 붙은 항목이 연달아 나오면 그 동치 관계가 전이적으로 번져서, a*b*의 상태 1·2·3이 전부 한 덩어리가 되고 결과물은 (a|b)*가 된다.

Homework1/regexp_matcher.cc:100–107

} else if (regexp[index] == '*') {
    for (auto pState : prev) {
        for (auto cState : current) {
            elements->push_back(Element(cState, pState, "#"));
            elements->push_back(Element(pState, cState, "#"));
        }                          // ← 양방향 → prev ≡ current 로 병합됨
    }
    next = current;

$ ./regexp 'a*b*'     ba → O    (거절되어야 함)     aabb → O    ab → O
$ ./regexp 'a*b*c'    bac → O   (거절되어야 함)
$ ./regexp 'a*b'      ba → X    bab → X            # 별표가 하나면 정상
$ ./regexp 'ab*c'     acb → X   abcb → X           # 정상
$ ./regexp '(ab)*c'   ac  → X   ababc → O          # 정상

명세의 다섯 예제에는 별표가 연속되는 패턴이 없어서 전부 통과한다. 톰슨 구성처럼 별표마다 새 상태를 만들었다면 생기지 않았을 문제다.

경미

정규식 파서의 실제 지원 범위와 오류 처리

확인한 지원 연산자: 리터럴 a-z, ., [...], |, *, (), 그리고 명세에 없는 +와 ?(109–123행)까지. 우선순위는 |가 가장 낮게 올바르게 처리된다(ab|cd가 abcd를 거절, ab*|c가 abb와 c를 모두 수용).

다만 .는 "any character"가 아니라 a–z 26자 전개다(61행). ./regexp 'a.b'에 aAb·a1b를 넣으면 거절된다. 그리고 지원하지 않는 문자를 만나면 REGEX_ERROR, 즉 exit(1)이 전부다 — 메시지 한 줄도 없이 프로세스가 사라진다. [a-c], A, a1, (ab, ab) 모두 무음 종료(rc=1)를 확인했다. regexp_matcher.cc:35의 new FiniteStateAutomaton은 대응하는 delete가 없다.

Homework1/regexp_matcher.h:22

#define REGEX_ERROR exit(1);

경미

죽은 매크로와 남은 라벨

#define lambda '#'가 fsa.h:19와 regexp_matcher.h:19에 중복 정의되어 있으나 어디에서도 쓰이지 않는다(엡실론은 fsa_main.cc:41에서 빈 문자열로 변환된다). lr_parser.cc:10–12의 LOG는 DISABLE_LOG false로 켜져 있는데 그 파일에서 한 번도 호출되지 않는다 — 같은 매크로가 fsa.cc:8에서는 true다. 그리고 Homework1 디렉터리의 파일 여섯 개가 헤더 주석에 // PL homework: hw2가 달려 있다(lr_parser.h:1, regexp_matcher.h:1 등). lr_parser.h는 "구조를 직접 설계하라"는 지시로 실제 수정한 파일인데도 라벨이 그대로다.

잘한 것

커밋 94ba7d6 "Fix fsa error" — 엡실론 폐포 재귀의 방문 검사가 from.find(j), 즉 상태 번호 집합에서 배열 인덱스 j를 찾고 있었다. 타입이 둘 다 int라 컴파일러가 잡아주지 않는 종류의 버그다. 이걸 스스로 찾아내 from.find(element.next_state) 검사를 삽입 이전에 두는 올바른 형태로 고쳤다.

LR 파서의 구동 루프는 정말로 맞다. lr_parser.cc:37–96은 97줄짜리 파일 하나로 shift(심볼+상태 2칸 push), reduce(num_rhs*2칸 pop 후 lhs를 다음 입력으로 재주입), goto, accept, 그리고 표 미적중 시 error를 전부 정확히 구현한다. 제공된 표현식 문법 표로 I, I+I, I*I, I+I*I, (I+I)*I, ((I))를 수용하고 I+, (), I), x, 빈 문자열을 거절하는 것을 확인했다.

BuildRegExpMatcher의 정렬(regexp_matcher.cc:13–23)은 "#"이 'a'보다 작다는 성질을 이용해 엡실론 전이를 각 상태 블록 맨 앞으로 보낸다. 그 덕분에 정규식 경로만은 위의 "행 순서 의존" 버그를 우연히 피해 간다. 의도적이었다면 영리한 우회고, 아니었다면 운이 좋았다.

Homework 2 — Haskell : 소수, 동전, 스도쿠

이 환경에는 ghc/runghc/stack이 없다. Haskell 코드는 컴파일·실행으로 검증하지 못했다. 대신 세 파일을 파이썬으로 1:1 전사해 알고리즘 의미를 확인했고, 아래 실행 결과는 모두 그 전사본에서 나온 것이다(타입 검사·레이아웃 규칙 통과 여부는 미검증). 커밋된 sudoku.py는 실제로 실행해 확인했다.

중대

.py 파일의 정체: 프로토타입이 아니라 나중에 만든 역이식물

git 타임스탬프가 명확하다. prime.hs·coin.hs는 2017-06-10 05:33, sudoku.hs는 2017-06-13 07:06에 들어왔고, coin.py·sudoku.py는 그 뒤인 2017-06-13 18:03(커밋 db6e888 "Update python code")에 한꺼번에 추가됐다. 파이썬이 먼저 있었다는 증거는 없다. 제출물을 파이썬으로 바꿔치기한 것도 아니다.

다만 남겨둔 채로 제출한 건 그대로 감점 요인이다. 과제 명세는 "Optionally zip the source code (ONLY .hs files)"라고 못 박는다. 게다가 coin.py는 Python 2 전용이라 지금은 아예 실행되지 않고, sudoku.py는 b7c5fed "remove test var"에서 .hs에서 지웠던 하드코딩 테스트 데이터(varList/blkList)를 그대로 들고 있다. 정리하다 만 파일이 최종 제출에 남은 것이다.

$ python3 -c "import coin; coin.flipCoin('HT')"
TypeError: 'map' object is not reversible          # coin.py:14 — Python 2 전용

$ python3 sudoku.py                                 # sudoku.py 는 정상 동작
True
[6, 7, 3, 1, 4, 8, 2, 9, 5]  ...                    # 행/열/블록 제약 전부 검증 통과

참고로 sudoku.py의 findNextCellToFill / isValid(grid, i, j, e) / solveSudoku(grid, i=0, j=0)라는 함수 분해와 이름은 널리 퍼진 파이썬 스도쿠 풀이 스니펫과 일치한다. 여기에 blk 인자를 덧붙여 직소 규칙으로 고친 형태다 — 추정이며 원본을 특정하지는 않았다.

중대

`flipCoin "THTHTH"`가 명세 예제와 다른 수열을 낸다

전략은 "맨 위가 H면 1장만 뒤집고, 아니면 가장 아래쪽 T까지 뒤집는다"이다. coin.hs:11–15의 count 정의가 그것이다. 명세의 세 예제 중 "HT"→[1,2,0]과 "HTTH"→[1,3,0]은 정확히 맞지만, 세 번째가 어긋난다.

Homework2/coin.hs:11–15

where count = if last coins
        then 1
        else case (False `elemIndex` coins) of
            Just n -> length coins - n
            Nothing -> 0            -- 도달 불가: 위 가드의 all (==True) 가 이미 처리

flipCoin 'HT'     : got=[1,2,0]        spec=[1,2,0]        match=True
flipCoin 'HTTH'   : got=[1,3,0]        spec=[1,3,0]        match=True
flipCoin 'THTHTH' : got=[5,1,4,1,2,0]  spec=[5,3,1,2,4,0]  match=False   (결과는 'HHHHHH')

n=2..10 전수 검사(2046개 입력): 실패 0건 — 항상 종료하고 항상 전부 H가 된다.
최장 수열: 'HHHHHTTTTT' → 18회 (최소 2회면 충분)

답이 틀린 건 아니다. 전수 검사 결과 언제나 모든 동전을 H로 만들고 종료한다. 하지만 명세가 요구하는 출력이 유일한지 최소인지가 불분명한 상태에서, 주어진 예제 셋 중 하나를 재현하지 못한다. 예제를 그대로 돌려보는 TA에게는 오답으로 찍힌다. 전략 자체도 최소와는 거리가 멀어서 "HHHHHTTTTT"에 18회를 쓴다(맨 위 5장 뒤집고 전체를 뒤집으면 2회).

중대

스도쿠: 하스켈 문법을 입은 가변 격자 자료 모델

질문이 "명령형 스타일인가"라면 답은 절반만 그렇다. 코드는 순수하고, 재귀적이고, 지연 평가를 제대로 쓴다 — sudokuRec의 valid는 9개 분기를 전부 계산하지 않고 null valid/head valid가 첫 성공까지만 강제하므로 사실상 조기 종료 백트래킹이다(where 바인딩이라 두 번 계산되지도 않는다). do 블록도 IORef도 없다.

문제는 자료 모델이다. Maybe를 쓸 줄 알면서(25–29행에서 Map.lookup을 case ... of Just/Nothing으로 받는다) 정작 "다음 빈 칸"의 부재는 (0, -1)이라는 C 스타일 센티널로 표현하고, 성공/실패는 Maybe [[Int]]가 아니라 (Bool, [[Int]]) 튜플로 나른다. setMatrix는 take/drop으로 리스트를 두 겹 쪼개 붙여 grid[i][j] = e를 흉내내고, matrix!!x!!y가 도처에 있다. 파이썬 풀이의 가변 격자를 그대로 옮긴 설계다.

Homework2/sudoku.hs:11–16

nextStep :: [[Int]] -> (Int, Int) -> (Int, Int)
nextStep matrix coord = if null valid
    then (0, -1)                       -- ← Maybe 대신 센티널 좌표
    else head valid
        where valid = [(x, y) | x <- drop (fst coord) ([0..8] ++ [0..8]),
                                y <- drop (snd coord) ([0..8] ++ [0..8]), matrix!!x!!y == 0]

[0..8] ++ [0..8]을 drop하는 순회는 파이썬의 (range(9)*2)[i:i+9]를 옮긴 것인데, 파이썬은 [i:i+9]로 정확히 9칸을 자르는 반면 Haskell 쪽은 상한을 안 둬서 최대 18칸을 돈다. 매 칸 탐색이 최대 324회 !! 조회를 하는 셈이다. 9×9라 실제로는 문제가 안 되지만(전사본에서 252회 재귀, 0.00초) 의도한 순회는 아니다.

Homework2/sudoku.hs:41–42

flatten :: [[a]] -> [a]
flatten xs = (\z n -> foldr (\x y -> foldr z y x) n xs) (:) []

concat이다. Prelude에 이미 있다. 그리고 이 파일의 import Data.List(3행)는 쓰이는 심볼이 하나도 없다 — 사용된 filter, head, null, take, drop, foldr, zip, elem, all, any는 전부 Prelude 소속이다.

경미

초기 단서를 검증하지 않는다

squigglySudoku는 길이 81만 확인하고(46–47행) 주어진 값들이 서로 모순되는지는 보지 않는다. nextStep이 첫 호출에서 빈 칸을 못 찾으면 즉시 (True, matrix)이므로, 81칸이 전부 채워진 격자는 그것이 규칙 위반이어도 그대로 "해답"으로 반환된다.

squigglySudoku (replicate 81 1) blkList
  → [1,1,1,1,1,1,1,1,1, ...]        # 모든 칸이 1인 격자가 '해답'으로 통과

경미

소수 판정이 O(n)이고, 음수 N은 오류 대신 0으로 대체된다

prime n은 [1..n] 전체를 훑어 약수 리스트를 끝까지 만든 뒤 == [1, n]로 비교한다. 조기 종료도, sqrt n 상한도 없다. 후보 하나당 O(n)이므로 findingPrimes 1000000 5 같은 입력은 사실상 멈춘다. 명세가 성능을 요구하지 않으므로 등급을 크게 깎지는 않았다.

명세는 "Report error if inputs is not correct"인데, m < 0은 error를 던지는 반면 n < 0은 조용히 0부터 세기 시작한다. findingPrimes -5 3이 [2,3,5]를 돌려준다 — 오류 보고가 아니다.

Homework2/prime.hs:2, 6–8

prime n = [x | x <- [1..n], n `mod` x == 0] == [1, n]
...
    | m < 0     = error "Can't find M primes where m < 0"
    | n < 0     = take m [x | x <- [0..], prime x]   -- ← 오류가 아니라 0으로 대체
    | otherwise = take m [x | x <- [n..], prime x]

잘한 것

커밋 2804029 "Fix error handle"에서 잡은 parseSection 버그. 원래 코드는 zip [0..] blkList였다 — 인자 list를 무시하고 파일 상단의 전역 테스트 상수를 읽고 있었다. b7c5fed로 그 전역을 지우자 드러났을 버그이고, 같은 커밋에서 zip [0..] list로 바로잡았다. 마감 직전(6/15 01:42)에 스스로 찾아낸 실질적 수정이다.

prime.hs는 이 레포에서 가장 하스켈다운 코드다. 지연 무한 리스트 [x | x <- [n..], prime x]에 take m을 씌우는 구성은 "M개 찾기"를 명령형 카운터 없이 표현하는 정확한 관용구다. 명세의 두 예제(2 5→[2,3,5,7,11], 6 6→[7,11,13,17,19,23]) 모두 재현했다.

스도쿠 백트래킹이 실제로 푼다. 전사본으로 명세의 예제 퍼즐을 돌려 81칸 해답을 얻었고, 초기 단서 보존·행/열/직소 블록 제약을 모두 별도로 검증했다. 4bdc398 "Fix sudoku return flattern array"에서 반환 타입이 [[Int]]였던 것(명세는 81개 평탄 리스트)을 스스로 알아채고 고친 흔적도 있다.

반복되는 패턴

"주어진 예제가 통과하면 끝"이라는 종료 조건. 여섯 문항 모두 README의 예제 입력을 정확히 통과하고, 여섯 중 셋은 예제에서 한 칸만 벗어나면 무너진다. FSA는 제공된 data/*.txt가 우연히 엡실론 행을 앞에 둬서, 정규식은 예제에 연속 별표가 없어서, LR 파서는 제공된 표에 빠진 상태가 없어서 각각 결함이 가려진다. 자기 입력을 하나만 더 만들어 봤다면 전부 발견됐을 것들이다.
인덱스로 자료구조의 불변식을 대체한다. fsa.cc의 next_lambda는 "엡실론 전이가 상태 블록 앞에 온다"는 배열 순서를 폐포 알고리즘의 전제로 삼고, isNFA는 "직전 한 행"이라는 슬라이딩 창으로 전역 속성을 판정하며, sudoku.hs는 Maybe 대신 (0,-1) 좌표를 센티널로 쓴다. 셋 다 "이 자리에 이게 있을 것"이라는 암묵적 가정이고, 셋 다 컴파일러가 못 잡는다.
find() / 인덱스 탐색 루프의 실패 경로를 안 쓴다. lr_parser.cc:53,55,68,76의 미검사 ->second, fsa.cc:127의 elements[j] 범위 밖 읽기가 같은 형태다. 후자는 바로 몇 줄 위 105행에 동일한 가드가 이미 있는데도 빠뜨렸다.
표준 라이브러리 대신 손으로 다시 짠다. concat 자리에 flatten, and/or 자리에 all (==True)/any (==True), map not 자리에 (\x -> not x) `map`. 틀리지는 않지만 언어를 아직 손에 익히는 중이라는 신호다.
정리는 하는데 끝까지 하지 않는다. lambda 매크로는 정의만 두 번 되고 안 쓰이고, lr_parser.cc의 LOG는 켜진 채 호출되지 않으며, Homework1 파일 여섯 개가 // PL homework: hw2 라벨을 달고 있고, sudoku.hs에서 지운 테스트 상수가 sudoku.py에는 그대로 남았다. 한편 .o·실행 파일·시크릿·대용량 데이터는 하나도 커밋되지 않았다 — 위생의 큰 줄기는 잡혀 있고 잔가지가 남는다.

지금 손본다면

next_lambda를 진짜 엡실론 폐포로 다시 쓴다. 워크리스트 하나와 방문 집합 하나면 20줄이다. 배열 순서 가정과 elements[j] 범위 밖 읽기가 동시에 사라지고, isAccept 끝의 사후 보정 루프(179–185행)도 같이 지울 수 있다. 이 레포에서 비용 대비 효과가 가장 큰 수정이다.
isNFA()를 버리고 항상 부분집합 구성을 돌린다. DFA는 부분집합 구성의 특수한 경우일 뿐이므로 분기 자체가 필요 없다. buildDFA()가 통째로 사라지고 "직전 한 행 비교" 판별 버그도 같이 사라진다.
*를 톰슨 구성으로 바꾼다. 별표마다 새 진입/퇴출 상태를 만들어 건너뛰기 간선과 되돌아가기 간선을 그 위에 놓으면 인접 별표끼리 상태가 병합되지 않는다. a*b*가 ba를 거절하게 된다.
find() 반환값을 전부 검사한다. lr_parser.cc 네 곳에 == end() 분기를 넣고 false를 돌려주면 세그폴트가 정상적인 거절로 바뀐다. 같은 김에 46행의 str[str_index]에 길이 검사를 붙인다.
.py 두 개를 지우고 sudoku.hs의 Maybe를 복구한다. nextStep :: [[Int]] -> (Int,Int) -> Maybe (Int,Int), sudokuRec :: ... -> Maybe [[Int]]로 바꾸면 (0,-1) 센티널과 (Bool, [[Int]]) 튜플이 동시에 없어지고, 이 과제의 출제 의도에 훨씬 가까워진다. flatten은 concat으로, import Data.List는 삭제.