Minishell - LCRS hierarchy & BNF production rules

LCRS hierarchy & BNF production rules

 

 

개요

 아! 보너스는 건드리는 것이 아니었던 것입니다. 만만히 보아 한 달을 예상했던 과제는 몸집이 불어나 태산 같은 잔해가 되어버렸습니다.

 

 사실 저는 구현 부를 담당했기 때문에, 처음부터 막막하지는 않았습니다. 팀원은 한 달 내내 울더군요. 그런데 결국 해내던데요? 제가 할 수 없는 부분은 버스를 타는 것입니다.

 

 이 과제를 준비하면서 가장 중요한 것은 출발 준비를 철저히 하는 것입니다. 자료를 이 잡듯 샅샅이 뒤져서 구현 부에서 밑 빠진 독에 물 붓지 않도록 시작하셔야 합니다.

 

 보너스를 하려면 트리 구조를 사용하는 것이 일반적입니다. 입력받은 한 줄을 의미 있는 단위로 나누어 트리구조에 예쁘게 담고 구현 부에서 트리 구조를 탐색하여 명령 단위를 추출하고 실행하는 것이 목표입니다.

---

 

1. LCRS hierarchy - Left Child Right Sibling 계층 구조

 

 해당 트리 구조를 의도하고 도입한 것이 아닌, 이후 설명할 BNF 룰에 따라 자료 구조를 만들다 발견한 개념입니다. BNF를 따라 의미 단위를 나누다 보면 자연스럽게 LCRS 계층 구조를 형성하게 됩니다.

 

 LCRS 트리는 트리 기반의 계층적 데이터 구조를 구현하는 데 사용됩니다. 이러한 데이터 구조는 문서 구조, 디렉토리 구조, 파싱 트리 등과 같은 다양한 응용 분야에서 활용됩니다.

 

 

 커맨드 라인의 의미 단위(토큰)는 다음과 같은 형상을 띄게 됩니다. root node에 대해서 left는 child node(하위, 종속적, 의존적)이며 각각의 node에 대해서 right는 sibling(동위, 독립적)입니다.

 

 이제 이 개념을 가지고 BNF rules을 살펴 봅시다.

 

2. BNF production rules

원본은 여기서 확인하실 수 있습니다: https://cmdse.github.io/pages/appendix/bash-grammar.html

 

#BNF RULE#
단, '|'는 파이프를 의미하고 |는 'or'를 의미합니다.
<REDIRECTION> ::= '<'<WORD> | '>'<WORD> | '<<'<WORD> | '>>'<WORD>
<SIMPLE_COMMAND_ELEMENT> ::= <WORD> | <REDIRECTION>
<REDIRECTION_LIST> ::= <REDIRECTION> | <REDIRECTION_LIST><REDIRECTION>
<SIMPLE_COMMAND> ::= <SIMPLE_COMMAND_ELEMENT> | <SIMPLE_COMMAND><SIMPLE_COMMAND_ELEMENT>
<COMMAND> ::= <SIMPLE_COMMAND> | <SUBSHELL> | <SUBSHELL><REDIRECTION_LIST>
<PIPELINE> ::= <PIPELINE> '|' <PIPELINE> | <COMMAND>
<LIST> ::= <LIST>'&&'<LIST> | <LIST>'||'<LIST> | <PIPELINE>
<SUBSHELL> ::= '('<LIST>')'

bash의 grammer는 매우 방대합니다. 그 중에서 과제에 해당하는 내용으로 축약하여 정리한 것입니다.

 

BNF RULE에 부합하지 않는 문법은 반드시 syntax error로 처리합니다.

 

 SUBSHELL은 일단 제외하고, 커맨드 라인 한 줄은 반드시 LIST에서 시작합니다. LIST는 and_if 혹은 or_if 기호가 존재하지 않는다면, 반드시 하나의 PIPELINE을 갖습니다. LIST가 재귀적으로 반복되더라도 반드시 PIPELINE으로 귀결됩니다. 따라서 LIST는 and_if, or_if, PIPELINE을 자식으로 가지며, 이들은 같은 계층입니다.

ex) <ls && pwd>는 하나의 LIST이며 결국, ls와 pwd는 PIPELINE이고 &&(and_if)와 같은 계층입니다.

AND_IF 예시

 PIPELINE은 PIPE가 존재하지 않는다면, 반드시 하나의 COMMAND를 갖습니다 LIST와 마찬가지로, PIPELINE이 재귀적으로 반복되더라도 반드시 COMMAND로 귀결됩니다. 따라서 PIPELINE은 PIPE와 COMMAND를 자식으로 가지며, 이들은 같은 계층입니다.

ex) <ls | cat>는 하나의 PIPELINE이며 결국, ls와 cat은 COMMAND이고 |(PIPE)와 같은 계층입니다.

PIPE 예시

COMMAND는 SIMPLE_COMMAND이거나 SUBSHELL입니다. 그런데 SUBSHELL은 양쪽으로 괄호를 반드시 보유하므로, 괄호가 없다면 반드시 SIMPLE_COMMAND입니다. SUBSHELL이었다면 REDIRECTION_LIST가 있는지 없는지로 분기점이 나뉘며, LIST를 자식으로 갖습니다.

ex) <ls>는 하나의 COMMAND이며 결국, ls는 SIMPLE_COMMAND입니다.

COMMAND 예시

ex) <'('ls')'>는 하나의 SUBSHELL이며 결국, LIST부터 다시 시작하여 SIMPLE_COMMAND로 귀결될 것입니다.

SUBSHELL 예시

SIMPLE_COMMAND는 SIMPLE_COMMAND_ELEMENT이거나 SIMPLE_COMMAND - SIMPLE_COMMAND_ELEMENT입니다.

ex) <ls -al>은 하나의 SIMPLE_COMMAND이며 결국, SIMPLE_COMMAND(ls) - SIMPLE_COMMAND_ELEMENT(-al)를 거쳐

둘 다 SIMPLE_COMMAND_ELEMENT가 됩니다.

SIMPLE_COMMAND_ELEMENT 예시

결과적으로 WORD만 남게 됩니다. REDIRECTION_LIST는 일련의 REDIRECTION을 자식으로 갖는 부모이며, 이 역시 REDIRECTION 문자와 WORD로 남습니다.

REDIRECTION 예시

구조를 간단하게 보기 위하여 하위 개념으로 갈수록 생략된 부분이 있습니다.

 

마치며

 트리 구조를 잘 만드셨다면 구현 부에서 어려움이 없으실 겁니다. 재귀 하향 방식으로 트리 구조를 만들 수 밖에 없기 때문에, 구현 부 역시 재귀 하향 방식으로 실행을 이어나가시면 됩니다.