[minishell] C 언어로 나만의 작은 쉘 만들기

2022.03.06 ~ 2022.04.14 진행.

minishell

42 Seoul 2서클 과제로 bash 의 간단한 몇 가지 기능을 구현한다.

주요 기능에는 redirection (<, <<, >, >>) 과 pipe (|)처리, 환경변수 설정 및 사용, exit status, built-in command, signal 처리가 있다.

 

내가 주로 담당한 부분은 커맨드의 파싱 처리 부분이었으므로 파싱 과정에 대해서 다룰 것이다.

 

 

파싱에 앞서 고려할 점

처리 순서

쉘 커맨드가 들어왔을 때 파싱 후 어떤 순서로 처리되어야 하는 지를 고려해야 한다.

 

예를 들어 <a echo -n <<lim1 "a b c" d  >b1 >b2 라는 커맨드가 있다면 실행될 커맨드는 redirection 이 아닌 것 중 가장 앞에 등장하는 토큰인 "echo" 이다.

echo 의 in 으로 들어갈 것은 <a 와 <<lim1 이다. <a 는 a라는 파일을 input 으로 받는다는 뜻이고, <<lim1 은 "lim1" 이라는 문자열을 delimeter 로 받아들이는 heredoc 이다. 리다이렉션은 앞에서 부터 순서대로 처리되기 때문에 최종적으로 echo의  input 으로 들어가는 것은 <<lim1 에서 받은 Input 일 것이다. 

echo 의 out 이 출력될 곳은 >b1 >b2 에 의해서 b2 라는 파일이 된다.

나머지 토큰들은 echo 의 인자로 처리된다.

 

파이프와 리다이렉션은 커맨드가 실행되기 전에 최종 input 을 받을 fd 와 output 을 출력할 fd 를 결정해야 한다. 따라서 처리 순서는 파이프 및 리다이렉션 -> 커맨드 실행이 되어야 한다.

 

 

자료구조 선택

연결리스트와 AST 중 커맨드 처리의 편의성을 위해 이진트리 형태로 AST (Abstract Syntax Tree) 를 구현하는 것을 선택하였다. 파싱 과정에서 token 종류를 분류하고 분류된 종료에 따라 sub-tree를 다르게 추가하여 커맨드 실행 시에는 pre-order 만으로 적절히 처리할 수 있다.

 

minishell grammar

/* -------------------------------------------------------
   The grammar symbols
   ------------------------------------------------------- */
%token  WORD
%token  NAME
%token  IO_NUMBER

/* -------------------------------------------------------
   The Grammar
   ------------------------------------------------------- */

program          : pipeseq
                 ;
pipeseq          :             command
                 | pipeseq '|' command
                 ;
command          : redirection simple_command
                 |             redirection
                 |             simple_command
                 ;
simple_command   : name
                 | name argv
                 ;
name             : WORD
                 ;
argv             : arg
                 | argv arg
                 ;
arg              : WORD
                 ;
redirection      : redirection io_rdr
                 | redirection io_here
                 ;
io_rdr           : '<'       filename
                 | '>'       filename
                 | '>>'      filename
                 ;
io_here          : '<<'      filename
                 ;
filename         : WORD
                 ;

Shell grammar 를 참고하여 최종적으로 미니쉘에 필요한 구문을 이와 같이 정리하였다. 

 

AST 로 표현하면 다음과 같다.

  											PIPESEQ
  								CMD							PIPESEQ
  					RDR						SIMPLE_CMD					(omit)
  	IO_HERE|IO_REDI			RDR			NAME		ARGV
  	SYMBOL		FNAME		(omit)		(null)		(null)
 	(null)		(null)

 

 

1차적으로는 WORD, PIPE, SYMBOL(heredoc 제외한 리다이렉션) , SYMBOL_HERE (heredoc) 의 네 가지 종류로 토큰화 한다.

토큰은 white space 나 symbol (WORD 제외 모든 토큰) 으로 나뉠 수 있다. 

2차적으로 토큰화 된 커맨드 리스트를 순회하면서 AST 를 생성한다. 이 과정에서 syntax 검사도 이루어진다.

 

 

syntax 검사 및 AST 생성 과정

올바른 syntax인지 검사하는 단계 - 위 grammar를 참고하여 검사한다.

1. SYMBOL(redirection), SYMBOL_HERE 뒤에 WORD인지 검사.
2. PIPE 앞, 뒤로 command(WORD, SYMBOL)인지 검사.
   • | , | aaa , aaa | 와 같은 경우는 에러로 처리된다.
3. heredoc처리 - delimiter 가 null일 수도 있음에 주의한다.
   • quote 처리를 먼저 하고 heredoc 등 처리
   • “” ‘’ 가 있으면 redirection 아니고 word 이다. ( echo hello ">file" 의 결과는 "hello >file" 이라는 문자열이 프린트되는 것이다.)
4. 환경변수 치환
   • heredoc 이면 뒤 WORD는 환경변수 처리 하지 않는다.
     • <<"$a"'$a' 하면 $a$a 가 delimiter.
   • heredoc 뒤가 아닌 WORD는 ‘’ 안에 있는 환경변수는 처리하지 않는다. 그 외는 처리한다.

int	check_syntax(t_token **head, t_ast **ptr)
{
	int		result;

	if ((*head)->type == PIPE)
	{
		result = check_pipe(*head, *ptr);
		*ptr = (*ptr)->right;
	}
	else if ((*head)->type == SYMBOL || (*head)->type == SYMBOL_HERE)
	{
		result = check_rdr(*head, (*ptr)->left);
		if (!result)
			*head = (*head)->next;
	}
	else
		result = check_word(*head, (*ptr)->left);
	return (result);
}

토큰의 종류 별로 검사를 다르게 실행한다.

 

 

 

Repository

https://github.com/strawberryShell/minishell

GitHub - strawberryShell/minishell: strawberry is delicious

 

Refs

https://www.tutorialspoint.com/compiler_design/compiler_design_phases_of_compiler.htm

Compiler Design - Phases of Compiler

https://www.leafcats.com/250

리눅스 명령 라인 파싱과 쉘 명령어 타입

https://wiki.bash-hackers.org/syntax/arith_expr

Arithmetic expressions [Bash Hackers Wiki]

https://dev.to/oyagci/generating-a-parse-tree-from-a-shell-grammar-f1

Generating a parse tree from a shell grammar