minishell의 파싱 과정을 정리한 글

전체 과정

순서도

초기화

시그널 및 터미널 설정

시그널 설정
- SIGQUIT(^\) : 시그널을 무시
- SIGINT(^C) : 새 프롬프트를 표시
터미널 설정
- tcgetattr, tcsetattr 과 c_lfag를 이용하여 터미널에서 특수제어문자(^C, ^\)가 출력되지 않도록 한다.

환경 변수 저장

자료 구조

단방향 연결 리스트

  
  typedef struct s_env
  {
  	char	*initial_line;
  	char	*key;
  	char	*value;
  } t_env;

  
  typedef struct s_list
  {
  	void	*content;
  	t_list	*next;
  } t_list;

구현 방법
- 명령행 인자에서 받은 envp(2차원 배열)를 돌며 값을 복사한다.
- = 를 기준으로 좌우를 나누어 각각 key, value에 저장하고 기존 문자열은 initial line에 저장한다.
- SHLVL 값을 1 증가시킨다.
예외 처리
- SHLVL 값이 음수인 경우
  - 0으로 초기화한다.
- SHLVL 값이 숫자가 아닌 경우
  - 1로 초기화한다.
- key에 SHLVL이 없는 경우. (Nested shell을 실행할 때, 이전 셸에서 SHLVL 변수를 unset한 경우가 있을 수 있음.)
  - 새롭게 SHLVL 노드를 만든 후, 값을 1로 초기화한다.

입력 받기

input = readline("minishell$ ");

예외사항

입력을 다시 받는 경우
- bash는 1.엔터, 2.공백, 3.SIGINT(ctrl+c)를 받으면 새 프롬프트를 띄우고 history에는 저장하지 않는다.
- 따라서 다음의 입력을 받은 경우에는 add_history를 하지 않고 다시 readline을 표시한다.
  - 문자열의 0번 인덱스가 null 문자인 경우
  - 문자열이 공백문자로만 이루어진 경우(null 문자 제외)
- signal 함수를 통해 시그널 핸들러를 설정해주어 SIGINT를 받은 경우 새 프롬프트를 띄울 수 있도록 한다.
입력을 이어서 받는 경우
- 따옴표가 짝이 맞지 않으면 계속해서 입력을 받는다.
- 따옴표가 짝이 맞지 않는 상태에서 EOF를 받게 되면 에러 메시지를 출력하고 새 프롬프트를 띄운다.
셸을 종료하는 경우
- 입력이 EOF인 경우 터미널 설정을 되돌리고 exit한다.

파싱 과정

미니셸의 파싱 과정은 bash의 동작방식을 기본으로 하였다.

Tokenization (토큰화)

입력받은 input을 최소한의 단위인 토큰으로 분리

자료 구조
- 단방향 연결 리스트
1 2 3 4 5 typedef struct s_token { int type; char str; } t_token;
- 각 노드의 content 멤버가 t_token이라는 노드를 가리키는 연결리스트로 구성됨.

# define T_WORD 1
# define T_PIPE 2
# define T_REDIRECT 3
# define T_HEREDOC 4

토큰은 메타문자들을 기준으로 나누었다.

메타문자(metacharacter)란?
- 따옴표로 감싸져 있지 않은 경우, 단어를 구분짓는 문자를 의미한다.
- 종류 : 스페이스, 탭, 개행문자, |, &, ;, (, ), <, >.

위와 같이 토큰이 operator인 경우(pipe, redirection, heredoc)와 그렇지 않은 경우(word)로 나누었다.

heredoc의 경우 트리 구조로 파싱을 하기 전에 미리 처리를 해주어야 하기 때문에 다른 리다이렉션과 구분하였다.

Syntax Check (문법 검사)

shell에서 입력을 파싱하고 명령어를 실행시키기 위해 만족해야 하는 규칙을 확인

토큰이 pipe인 경우
- pipe만 입력한 경우
- pipe 두 개가 연달아 나온 경우
토큰이 redirection인 경우
- 뒤에 pipe가 있는 경우
- redirection 두 개가 연달아 나온 경우

문법 오류가 있는 경우 exit code를 258로 설정하고 새 입력을 받는다.

Here Document

토큰에 << 이 존재하는 경우 처리

here document (히어 도큐먼트)란?
- 의미
  - 문자열을 프로그래밍 언어 중에 그대로 포함시키기 위한 방법
- 사용법
  - << 뒤에 식별자를 선언하고 원하는 문자열을 쓴 후에 식별자로 끝낸다.
구현 방식
- 토큰이 << 인 경우 임시파일을 생성
- 프로세스를 생성하고 자식 프로세스에서 입력을 받는다.
- 임시파일에는 식별자가 입력될 때까지 입력받은 내용을 쓴다.
- 입력이 끝나면 << 토큰은 < 토큰으로 변경하고 식별자 토큰은 임시파일로 변경한다.

Variable Expansion (환경 변수 확장)

$(variable) 형태로 들어온 입력에 대해 대응되는 value로 변환

구현 방식

Word Split (단어 분리)

확장된 문자열에 대해 IFS를 기준으로 단어를 분리

구현 방식
- 환경 변수에서 IFS를 찾는다. 없는 경우 기본값인 공백, 탭, 개행문자로 설정한다.
- IFS를 만나면 skip, IFS가 아닌 문자를 만나면 IFS를 만날 때까지의 문자를 저장하여 기존 문자열과 바꾼다.
- 노드를 새로 이어준다.

Quote Removal (따옴표 제거)

토큰에서 가장 바깥에 있는 따옴표 쌍을 제거

구현 방식
- 제거할 따옴표의 위치를 저장할 배열을 만들고 0으로 초기화한다.
- 따옴표를 만나면 해당 인덱스의 요소를 1로 변경하고 같은 종류의 따옴표를 만날 때까지 인덱스를 증가시킨 뒤 해당 위치의 요소를 1로 변경한다. (이 과정에서 만난 다른 종류의 따옴표는 제거되지 않는다.)
- 새롭게 할당한 문자열에 기존 문자열에서 앞서 저장한 배열의 요소가 0인 인덱스에 해당하는 문자를 복사한다.

Tree Parsing (트리 구조 파싱)

토큰으로 구성한 연결 리스트로 추상 구문 트리(Abstract Syntax Tree, AST) 구성

파싱은 재귀 하향식으로 진행함.

  
typedef struct s_node_cmd
{
	char	*file_path;
	char	**argv;
} t_node_cmd;

  
typedef struct s_node_red
{
	int		redirect_type;
	char	*file_name;
} t_node_red;

  
typedef struct s_node_reds
{
	t_node_red	*n_red;
	t_node_reds	*n_reds;
} t_node_reds;

  
typedef struct s_node_exec
{
	t_node_reds	*n_reds;
	t_node_cmd	*n_cmd;
} t_node_exec;

  
typedef struct s_node_pipe
{
	t_node_exec	*n_exec;
	t_node_pipe	*n_pipe;
} t_node_pipe;

Ref.

Shell Operation (Bash Reference Manual)
히어닥 HEREDOC
미니쉘(minishell) 과제 - 트리 구조로 파싱하기

Minishell ③ 구현 과정