Minishell (1) — 파싱: 토큰화 · 따옴표 · env 확장, 그리고 tree 였으면 좋았을 것

Minishell 시리즈

1. 파싱과 tree 구조 회고 ← 현재
2. 실행 구조: fork · pipe · heredoc · signal

42 Seoul 의 minishell. bash 를 C 로 다시 쓰는 과제를 2인 1조로 진행했다. 내가 맡은 건 파서 파트 — 입력 한 줄을 받아 토큰으로 자르고, 따옴표 규칙을 적용하고, 환경변수를 확장하고, 문법 오류를 잡아내는 부분. 실행 쪽(fork/pipe/heredoc/signal) 은 페어가 짰다.

이 글은 내가 짠 파싱을 복기하면서, “지금 다시 하면 뭘 다르게 할까” 에 대한 답을 정리한 것. 결론부터: AST 로 짰어야 했다. 왜인지 따라가 본다.

Shell 이 파서에게 요구하는 것

bash 한 줄의 life-cycle:

입력 → 토큰화 → 구문 분석 → 확장 → 리다이렉션 설정 → 실행 → 대기

파서의 책임은 앞 세 단계다: 토큰화, 구문 분석, 확장. 여기서 나오는 결과물이 실행기에게 “이 명령을 이렇게 돌려라” 라는 명세서 가 된다.

Minishell 재현 범위:

• 파이프 |, 리다이렉션 < > >> <<
• $VAR, $? 확장, 단/이중 따옴표 규칙
• 빌트인 7종 (cd, echo, pwd, export, unset, env, exit)
• 시그널 (SIGINT · SIGQUIT, heredoc 중 Ctrl+C)
• &&, ||, ;, 서브쉘, 와일드카드, 잡 컨트롤은 ❌

&& 가 없어서 논리적 기교는 없고, 파이프 한 겹 + 리다이렉션 + heredoc 까지만 처리한다.

토큰화 — 따옴표 상태머신

shell 토큰화가 일반 split 과 다른 유일한 지점은 따옴표 안은 한 덩어리 라는 규칙.

echo "hello | world"   → ["echo", "\"hello | world\""]
echo hello | world     → ["echo", "hello", "|", "world"]

같은 | 인데 따옴표 위치에 따라 해석이 180도 갈린다. 그래서 토크나이저는 따옴표 상태 를 들고 다니는 상태머신이 된다.

// src/parsing_split_utils.c
size_t split_by_char(char *input, size_t len, size_t i, char *quote)
{
    while (i < len) {
        if (input[i] == '\'' || input[i] == '\"') {
            if (!*quote)               *quote = input[i];    // 진입
            else if (*quote == input[i]) *quote = 0;           // 탈출
            else { i++; continue; }                             // 다른 종 안
            i++;
            continue;
        }
        if (!*quote && (is_special_t(input[i]) || input[i] == ' '))
            break;                     // 따옴표 밖 + 특수문자/공백 → 경계
        i++;
    }
    return i;
}

quote 가 0 이면 일반 모드, ' 또는 " 면 따옴표 내부. 따옴표 내부에서는 공백도 | 도 다 그냥 문자.

특수문자 정의:

char is_special_t(char c) {
    return (c == '<' || c == '>' || c == '|' || c == ',' || c == '\t');
}

그래서 ls>file 이 ["ls", ">", "file"] 로 갈라진다. bash 도 똑같다.

환경변수 확장 — 파싱 직후 문자열 치환

토큰이 나온 뒤 $VAR / $? 를 교체한다. 따옴표 규칙이 한 번 더 얽힌다.

한 토큰을 훑으며 따옴표 상태를 추적:

// src/parsing_env.c
while ((*str) && (*str)[idx]) {
    if (!is_in_quotes((*str)[idx], &in_single_quote, &in_double_quote)) {
        if (handle_dollar_question(str, idx, in_single_quote))
            did_replace = true;
        else if (!in_single_quote && (*str)[idx] == '$' &&
                 is_alpha_num((*str)[idx + 1]))
            replace_variable(str, idx, env, in_double_quote);
    }
    idx++;
}

실제 치환은 env_replace → get_new_str — $VAR 영역을 env 값으로 갈아끼운 새 문자열로 교체.

파싱 단계에서 이미 문자열 치환을 끝내버린다. 실행기는 env 를 더 볼 일이 없다. 단, heredoc 은 예외 — 실행 시점에 사용자 입력을 받으면서 확장해야 하므로 두 번째 expander 가 heredoc.c 에 따로 있다. 이게 나중에 후회 포인트.

핵심 선택 — t_mini[] flat 배열

토큰이 나오면 어디에 담는가. 내 선택은 이거였다.

typedef struct s_mini {
    char **command;     // ["ls", "-l", NULL]
    int    cmd_size;
    int    cnt;         // 파이프라인 전체 수
    int    input_fd, output_fd, origin_in, origin_out;
    int    is_heredoc, is_signal, builtin_cnt, echo_fail, doc_cnt, delete;
} t_mini;

파이프(|) 기준으로 자른 결과를 t_mini 배열에 넣는다. ls -l | grep .c | wc -l 이면:

┌──────────────────┬──────────────────┬──────────────────┬──────────┐
│ mini[0]          │ mini[1]          │ mini[2]          │ mini[3]  │
│ ["ls","-l"]      │ ["grep",".c"]    │ ["wc","-l"]      │ NULL     │
└──────────────────┴──────────────────┴──────────────────┴──────────┘
                        flat array                         sentinel

put_struct 가 | 마다 segment 를 잘라 채운다. 단순하고 빠르다 — 오후 한 나절이면 돌아간다. 실행기는 for (i=0; i<cnt; i++) 한 줄로 순회.

순수 파이프라인 만 있다면 이 구조가 이상적이다.

삐걱거림 — 리다이렉션이 섞이는 순간

shell 은 이런 것도 써야 한다.

cat << EOF > /tmp/x
ls -l > out.txt | grep .c
< in.txt cat > out.txt

flat command 배열 안에 리다이렉션 토큰과 타겟이 섞여 있다:

command: ["cat", "<<", "EOF", ">", "/tmp/x"]

이 상태로 cat 을 exec 에 넘기면 <<, EOF, >, /tmp/x 를 전부 자기 argv 로 인식한다. 그래서 리다이렉션 토큰을 배열에서 NULL 로 덮어쓰고, 실행 직전 cmd_realoc 이 NULL 을 걸러서 argv 를 재조립하는 trick 이 필요하다.

// src/redirection_util.c
void set_cmd_null(t_mini *data, int start, int end)
{
    // command[start..end] 를 NULL 로 덮음
}

// src/process_utils.c
while (++i < data->cmd_size)
    if (data->command[i]) new_token[++j] = ft_strdup(data->command[i]);

작동은 한다. 그런데 여러 리다이렉션의 순서 규칙 이 애매해지고, 문법 검사도 “토큰 배열을 돌면서 인덱스 왼쪽/오른쪽이 뭔지 확인” 하는 패턴이 된다.

// src/parsing_check_utils.c
if (current[0] == '<' && next && (next[0] == '<' || next[0] == '>')) {
    ft_putstr_fd("Error: parse error near `<'\n", 2);
    return true;
}

parsing_check_*.c 안이 거의 전부 이런 인덱스 놀이다.

Bash 가 쓰는 구조 — AST

bash 는 parse.y (Yacc) 로 트리를 만든다. 골자:

pipeline:
  simple_command
  pipeline '|' simple_command

simple_command:
  command_word_list  redirection_list?

ls -l > a | wc 의 트리:

       Pipeline
      /        \
   Cmd           Cmd
   argv: ls -l   argv: wc
   redir:        redir:
     > a

각 Cmd 노드가 argv 와 리다이렉션 리스트 를 별개 필드 로 든다. 리다이렉션은 순서대로 줄지어 있고, 실행 시 그 순서대로 open + dup2.

이 구조의 장점:

1. argv 와 리다이렉션이 섞이지 않는다 — set_cmd_null trick 불필요
2. 리다이렉션 순서가 자연스럽게 보존 — 리스트 순서가 apply 순서
3. heredoc / subshell / compound command 가 같은 모델로 확장
4. 문법 에러가 노드 단위 — 인덱스 놀이 없음
5. &&, || 추가가 노드 타입 하나 — flat 은 레이어 전부 다시 짜야 함

Flat 구조가 실제로 남긴 빚

1. Expander 가 두 벌

일반 토큰의 $VAR 는 파싱 직후 치환. Heredoc 은 입력 시점에 치환. 로직은 거의 같은데 파일도 다르고 구현도 따로 논다 (parsing_env.c vs heredoc.c). AST 였다면 expand(Word, env) 함수 한 벌이 Word(Expandable) 리스트를 받아 처리.

2. 검사 로직이 배열 탐색

”< 뒤에 > 가 오면 에러” 같은 규칙이 인덱스 순회로 구현됨. AST 라면 “Redir 노드의 target 이 비어있다” 한 줄.

3. 리다이렉션과 파이프가 같은 레벨에서 엉킴

실행기의 set_re_and_pipe 는 리다이렉션 실패 (input_fd == -1) 를 감지해서 “이번 명령 스킵 + 다음 파이프로” 같은 임시 플래그로 흘린다. AST 였다면 “Redir 열기 실패 → 이 Cmd 노드 전체 중단, 다음 Pipe 자식으로” 가 구조적으로 깔끔.

4. 순서 보장이 구조가 아니라 토큰 배열 순서에 의존

> a > b > c cmd

dup2 가 덮어쓰기라 자연스럽게 c 만 살아남지만, 이건 우연히 맞는 것이지 구조가 보장하는 게 아니다. 복잡한 케이스 (2>&1 같은 fd 복제) 가 들어오면 바로 깨진다. 과제 범위에선 괜찮지만 확장성이 없다.

왜 처음부터 AST 로 안 했나

솔직히 말하면 파서를 몰랐기 때문이다.

• Recursive descent / Yacc 본 적 없었다
• “shell 은 한 줄이라 간단하지 않을까” 라고 생각했다
• 첫 동작하는 버전을 빨리 띄우는 게 중요해 보였다

flat 으로 시작해서 순수 파이프만 있을 때 문제가 없었다. 리다이렉션이 들어오면서 삐걱거리기 시작했고, heredoc 에서 expander 가 갈라졌고, 여러 리다이렉션을 맞추면서 trick 이 늘어났다. 매 단계마다 “지금 조금만 기우면 돌아간다” 였고, 돌아보면 누적된 기울기가 상당하다.

다시 한다면

enum node_type { CMD, PIPE, REDIR_IN, REDIR_OUT, REDIR_APPEND, HEREDOC };

typedef struct s_node {
    int              type;
    struct s_node   *left, *right;   // PIPE 용
    char           **argv;           // CMD 용
    char            *target;         // REDIR / HEREDOC 용
    struct s_node   *next_redir;     // CMD 에 붙는 redir 체인
} t_node;

실행기는 타입 기반 재귀 dispatch:

int exec(t_node *n, t_env *env, int in, int out);

Expander 한 벌, 문법 검사 노드 단위, heredoc 은 HEREDOC 노드에 Word(Expandable) 리스트. &&/|| 확장은 AND/OR 노드 추가로 끝.

한 줄 교훈

“flat 이 지금 더 간단해 보인다” 는 느낌은 대부분, 뒤에 나올 문법을 아직 안 만난 상태다.

shell 처럼 여러 축(파이프, 리다이렉션, 확장, 제어)이 겹치는 언어는 초반에 AST 비용을 내는 게 장기적으로 싸다. bash 가 그렇게 생긴 이유가 있었던 거다.

다음 편은 페어가 짠 실행부 (fork/pipe/heredoc/signal) 가 이 파서 위에서 어떻게 돌아가는지. 그리고 그게 내 flat 구조 때문에 어떤 trick 을 감수해야 했는지.

Part 2 — 실행 구조: fork · pipe · heredoc · signal