shell이란 껍질을 뜻하며, 커널을 감싸고 있다는 의미에서 붙은 이름이다. 쉘은 사용자의 목적인 응용프로그램의 실행을 편하게 하기 위한 적절한 실행환경을 제공하는 프로그램이다. 운영체제의 핵심인 커널에 서비스를 요청하는, 일종의 클라이언트라고 생각할 수도 있다. 우리는 MiniShell에서는 이 shell의 일부를 구현해야 한다.
하지만, 우리의 shell은 단순히 실행 환경만을 제공하는 프로그램이 아니었으니, shell은 shellscript라는 프로그래밍 언어를 실행시키는 인터프리터다. 인터프리터란 코드를 문자열의 형태로 입력으로 받아서 해당 코드를 실행하는 프로그램이다. 대표적으로 python, node.js, 등이 인터프리터를 기반으로 동작하는 언어다. 따라서, 우리의 shell도 마찬가지로 shell script라는 프로그래밍 언어를 해석하고, 실행해야 한다.
일반적인 인터프리터는 코드를 실행하기 위해서 다음의 과정을 수행한다.
input : 실행하고자 하는 코드를 문자열의 형태로 읽어들임. 일반적으로, 개행으로 구분되는 라인 단위의 입력을 받아 그에 해당하는 동작을 수행하고 다음 라인 입력을 대기한다.
Lexing : 입력받은 코드를 특정 문자(연산자, 키워드, 등)를 기준으로 분리하여 의미를 갖는 최소 단위로 구분하는 작업. 이렇게 얻어진 단위를 token이라 부른다. 최종적으로 token의 배열을 획득한다. lexical analysis 또는 tokenize라고 부르기도 함. 이후 과정에서 이들 token이 어떠한 방식으로 결합되는 지에 따라서 다른 해석이 가능함.
Parsing : 코드를 해석하는 작업. 렉싱 결과 획득한 token을 문법에 맞게 결합하여 의미를 갖는 구조로 재구성하는 과정. 토큰들의 결합은 tree가 되는데, 주로 이진트리가 선택됨. 이 트리를 추상 구문 트리(abstract syntax tree, ast)라고 함. 즉 단순한 token의 나열에서, 규칙적으로 결합된 ast를 생성하는 과정임.
Evaluating : 생성된 구문 트리를 순회하면서 해당 트리가 표현하는 문법구조에 따른 동작을 수행한다.
트리의 순회를 마쳤으면, 다시 0번으로 돌아가 입력을 기다린다.
1, 2번 과정을 수행하는 프로그램 혹은 서브루틴을 흔히 파서(parser)라 한다. 토큰을 어떤 순서로, 어떻게 결합하는 지가 곧 파서의 성능을 결정하며, 보다 효율적이고 정밀한 해석을 위해서 다양한 파싱 알고리즘이 고안되었다. 현재는 파서를 생성하는 툴이 개발되어, 보통 사람이 파서를 구현하는 일은 거의 없게 되었다.
초창기 파싱 알고리즘은 재귀 하향식 파싱 알고리즘이었다(이하 재귀 하향 파서). 재귀 하향 파서는 우선순위가 높은 상위의 문법에서 시작하여 하위의 문법으로, 구문 전체가 해석이 될 때 까지 모든 문법을 적용해보는 알고리즘이다. 일반적으로 모든 문법의 패턴(토큰의 조합)에 대응하는 해석 함수를 준비하고, 각각의 경우에 대해서 해석 함수를 호출하는 방식으로 이루어진다. 만일 해당 해석 함수로 해당 토큰에 대한 해석에 성공하면, 이후 다음 토큰에 대해서 재귀적으로 해석 함수를 호출한다. 해당 해석 함수로 해당 토큰에 대한 해석이 실패한다면 다음 하위 문법의 해석 함수를 호출한다.
해당 알고리즘은 가능한 모든 문법 패턴에 대해서 해석을 시도한다는 점에서 완전 탐색 알고리즘이다. 재귀 하향식 파서는 해당 구문에 문법적 오류가 있어 해석이 불가능한 상황을 만나면, 다음 문법으로 해석을 시도해야 하고 이는 필연적으로 back-tracking을 의미한다. 이러한 back-tracking 과정에는 기존의 해석(즉 생성한 ast)을 모두 취소(즉 ast를 삭제)하는 과정을 포함한다. 이러한 백트래킹은 다음과 같은 문제를 갖는다.