미니쉘(minishell) 과제 - 트리 구조로 파싱하기

미니쉘(minishell)은 팀 프로젝트였기에 팀원 분과 같이 진행을 하였습니다. 저는 파싱 부분을 담당했으며, 팀원 분은 빌트인 함수 구현을 담당해주셨습니다.

간단하게 저희의 파싱 방식과 FlowChart를 공유해보겠습니다. 이 글이 치트 sheet 가 되는건 원치 않습니다. 파싱트리의 대략적인 감을 잡을 잡으시는데 도움이 되길 바라겠습니다. 문제시 연락해주세요.
실제 bash의 동작방식과 다르며, 저희만의 쉘을 만들었기 때문에 이를 참고하시고 읽어주시면 감사하겠습니다. 

 

minishell 하시는 모든 분들 파이팅입니다 ~~~!

 

사전 조사

먼저 파싱(parsing) 이란 것을 조사할 필요가 있었습니다. 

컴퓨터 과학에서 파싱((syntactic) parsing)은 일련의 문자열을 의미 있는 토큰(token)으로 분해하고 이들로 이루어진 파스 트리(parse tree)를 만드는 과정을 말한다.
출처: 위키백과

위키백과를 인용해서 보았을 때,  1. 파싱은 문자열을 의미가 있는 토큰이라는 단위로 분리

2. 트리형태로 만드는 과정, 이렇게 두 부분으로 나눌 수 있다고 생각했습니다. 

 

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

파싱을 사용하는 대표적인 예제를 검색해보면 컴파일러가 나옵니다. 위 그림은 소스코드를 컴파일하여 머신에서 실행 가능한 타깃 코드로 컴파일하는 과정을 나타내고 있습니다. 소스코드를 컴파일러가 원하는 형태로 가공하는 과정을 거치고 있습니다.

 

컴파일러에서 어휘(Lexical) 분석과 구문(Syntax)분석을 단계를 거칩니다. 이 과정에서 토큰화하고, 파스 트리를 만드는 작업이 이루어지게 됩니다. 몇몇 예제 코드와 쉘을 구현한 블로그 글을 조사한 결과, 보통 어휘 분석과 구문 분석을 거쳐서 터미널로 입력된 값들을 파싱 트리 구조로 만드는 것을 확인하였습니다.

 

이를 참고하여 저희 쉘도 어휘 분석과정에서 명령어들을 토큰화 시키고, 구문 분석에서 오류가 없는지 체크한 뒤 트리로 파싱 하도록 구조를 잡았습니다.

 

 

파싱 파트 개발 진행 순서

1. leadline 호출하여 line 읽기

2. line을 적절하게 split 하기 (큰따옴표 작은따옴표 처리까지)

3. split 된 문자열에게 의미(type)를 부여하여 토큰화 시키는 과정 구현

4. 팀원과 함께 구문 (syntax) 문법 정의

5. 구문(syntax) 문법이 맞는지 체크하는 기능 구현

6. 구문(syntax) 문법에 맞추어 트리구조로 파싱 (재귀 하향 파서)

7. 전위 순회 탐색으로 명령어 프로세스 실행하도록 하기

8. 리다이렉션도 순차적으로 탐색하도록 구현

9. 파이프도 순차적으로 탐색하도록 구현

 

위와 같은 순서로 개발을 진행하였습니다. 

 

Minishell FlowChart 

표현을 위해 중간에 일부 생략되어 있는 부분이 있긴 하지만, 전체적인 흐름은 위와 같습니다.

 

 

어휘 분석 (lexcial analysis) 단계

/*
 * token
 */

# define T_NULL 0
# define T_WORD 1
# define T_PIPE 2
# define T_REDIRECT 3
# define T_DOUBLE_QUOTES 4
# define T_SINGLE_QUOTES 5
typedef struct s_token {
	int	type;
	char	*str;
}	t_token;

어휘 분석(lexcial analysis) 단계 에서는 터미널에 들어온 입력 값들을 토큰화 시키는 과정을 수행합니다. 저희 팀의 경우 구조체를 만들어 토큰을 분리하였습니다. 

 

 

input: ls -al < a | grep "" 

str: [ls, -al, <, a, |, grep, "", NULL]
type: [WORD, WORD, REDIRECT, WORD, PIPE, WORD, WORD, NULL]

예를 들어 ls -al < a | grep "" 라는 입력이 올 경우 문자열을 적절하게 분리(split) 한 뒤 각 문자열에 맞게 의미를 부여합니다. 

 

이곳에서 부여한 의미(제 코드에서는 type)는 문법 분석(syntax analysis) 단계에서 사용되게 됩니다.

 

 

문법 분석 (syntax analysis) 단계

하향식 구문 분석은 루트로부터 터미널 노드 쪽으로 파스 트리를 구성하는 것으로 입력 문자열에 대한 좌측 유도 과정이다. 
위키백과: 하향식 구문 분석

재귀 하향 파서는 상호 순환 절차의 집합으로 이루어진 하향식 구문 분석 이다. 한 절차는 문법의 한 생성 규칙을 처리한다. 따라서 프로그램의 구조는 문법을 반영한 모양이 된다.
위키백과: 재귀 하향 파서

문법 분석 방법에는 상향식 파싱, 하향식 파싱이 존재했었습니다.

하향식 파싱을 재귀적으로 구현한 재귀 하향 파서가 코드 구현이 직관적이라 이를 택했습니다.

 

syntax 문법 규칙 정의

구문 분석을 하기 위해서 저희만의 문법 구조를 만들 필요가 있었습니다.

Shell Grammar Rules를 참고하여 구현해야하는 부분의 문법을 가져와서 구현해야 하는 minishell 문법 구조에 맞게 수정하였습니다. 

 

<pipeline>     ::= <cmd>
               |   <pipeline> '|' <cmd>

<cmd>          ::= <simple_cmd> 
               |   <simple_cmd> <redirects>

<simple_cmd>   ::= <file_path>
               |   <argv>

<argv>         ::= <file_path> <args>

<redirects>    ::= <io_redirect>
                |  <redirects> <io_redirect>

<io_redirect>  ::= '<'   <filename>
                |  '<<'  <filename>
                |  '>'   <filename>
                |  '>>'  <filename>

<args>        ::= WORD 
                | <args> WORD

<filename>    ::= WORD

<file_path>   ::= WORD

 

정확하게 저희가 정의한것이 BNF 문법의 표준이라 하기에 부족한 점이 많지만 유사하게 작성해보았습니다.

 

 

void	syntax_pipeline()
{
	syntax_cmd();
	if (token.type == T_PIPE)
		syntax_pipeline();
}

void	syntax_cmd()
{
	syntax_simple_cmd();
	if (token.type == T_REDIRECT)
		syntax_redirects();
}

void	syntax_redirects()
{
	syntax_io_redirect();
	if (token.type == T_REDIRECT)
		syntax_redirects();
}

void	syntax_io_redirect()
{
	if (token.type == T_REDIRECT && tokens.type == T_WORD)
		;
	else
		return (Fail);
}

void	syntax_simple_cmd()
{
	if (token.type == T_WORD)
	{
		if (token.type == T_WORD)
			;
	}
	else
		return (Fail);
}

문법 규칙을 토대로 하여, 햐향식 재귀로 문법을 검사하고, 위와 같이 트리구조로 파싱 하는 코드를 작성하였습니다. 

 

 

Parse Tree / 구문 트리

ls -a -l >> a < b > c | grep "" | cat << x > y

위의 명령어를 문법에 맞추어 트리 구조로 파싱 하면, 그림과 같이 나오게 됩니다. 

 

void	search_tree(t_ast *node)
{
	execute_tree(node);
	if (node->left != NULL)
		search_tree(node->left);
	if (node->right != NULL)
		search_tree(node->right);
}

트리를 전위 순회 탐색하여 명령어를 수행 시키도록 하였습니다. 

 

 

 

이런 트리구조를 짜는데 직관적으로 도움이 되었던 자료

- https://stackoverflow.com/questions/52666511/create-an-ast-from-bash-in-c

- https://slidetodoc.com/interpreter-source-program-input-interpreter-output-basic-lisp/

- https://www.python2.net/questions-691732.ht

 

 

 

 

추가 팁, GitHub CI 도입

GitHub Action을 사용해서 지속적으로 코드가 병합될 때마다 문제가 없는지 체크했습니다. 로컬에서 체크한다고 해도 실수해서 올리는 경우가 가끔 발생했기 때문에 이를 확인하기 위해 도입했습니다.