이론없이 컴파일러 만들기 꿈파일러 3
구문분석이란
이전 장에서 토큰화가 무엇인지 알아봤다. 토큰화과정만으로는 우리가 할 수 있는 것이 거의 없다.
위키 인용
컴퓨터 과학에서 파싱((syntactic) parsing)은 일련의 문자열을 의미있는 토큰(token)으로 분해하고 이들로 이루어진 파스 트리(parse tree)를 만드는 과정을 말한다.
- 하향식 구문 분석(top-down parsing)
- 상향식 구문 분석(bottom-up parsing)
구문분석에는 정말 크게 분류하면 아래와 같은 방법이 있다. 이 중에서 우리는 가장 구현하기 쉬운 하향식 구문 분석을 선택하겠다.
구문분석 하는 방법
처음부터 while 문 if 문 function 에 대해서 다루면 좋겠지만 컴파일러를 이제 막 만들어보고 싶다는 생각을 가졌다면 걷기는 커녕 기어다니기도 힘든 지경일거다. 파싱 구현에 대해 감을 가장 쉽게 잡을 수 있고, 제일 구현하기 쉬운 형태의 예제를 구현하면서 점차 절차지향적 프로그래밍에서 사용되는 while, if 문으로 확장할 것이다.
1차 구문분석의 예제
간단한 수식을 입력 받아 계산된 결과를 보여주는 프로그램을 작성해본다. 사칙연산을 지원하고 세미콜론(;)을 만나면 값을 출력하는 간단한 예제를 만들어보자.
(200 + 12) * 34 + 56 - 100;
200 + 12 * 34 + 56 - 100;
200 + (12 * 34) + 56 - 100;
-100;
1 + -5;
-(1 + -5);
-(1 + -5)*4 + 100 * 3;
1 * -100;
1 * -100 + 30 / 3 - (1 + -3) - (10 + 1030 + 30) * 3 * 2 -((123 + 30));
(1 * -100 + 30 / 3 - (1 + -3) - (10 + 1030 + 30) * 3 * 2 -((123 + 30)));
(1 * -100 + 30 / 3 - (1 + -3) - (10 + 1030 + 30) * 3 * 2 -((123 + 30))) * 3 - 100;
100 - -100;
100 - (-100);
100 - (-100 + 1 - 3 * 10 / 2 / 5 - 10 + 3838 - 1003 + 13) - 3 - 1- 3;
위는 우리가 올바르게 통과해야할 수식의 목록이다.
구현사항을 보면 만만치 않아보인다. 하지만 귀찮을 뿐이지 난이도가 높은 작업이 아니다. 차근차근 접근해보자.
그 전에 잠깐! Context Free Grammar 문법을 표현하는 방식중 하나인 배커스-나우르(BNF) 표기법에 약간이라도 알아야 한다. https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%BB%A4%EC%8A%A4-%EB%82%98%EC%9A%B0%EB%A5%B4_%ED%91%9C%EA%B8%B0%EB%B2%95
BNF
<E> ::= <E> + <T> | <E> - <T> | <T>
<T> ::= <F> * <T> | <F> / <T> | <F>
<F> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
위 문법을 이용하면 사칙연산에 대한 규칙을 표현할 수 있을 것만 같다. 세상일 쉬운거 없다. 위 문법은 사칙연산에 대한 우선순위를 표현은 되지만, 프로그래밍으로 표현하기에 무한 재귀함수호출에 걸린다(좌항을 함수라고 치고 구문분석을 구현할 경우). 나중에 구현부를 직접 보면 감이 올거다.
프로그래밍으로 구현하기에 BNF 는 부족한점이 여러모로 많다. 그래서 EBNF 표기법을 이용하면 프로그래밍으로 구현하기 적합한 형태로 바꿀 수 있다. EBNF 에서 여러가지 확장된 표현이 있지만, 우리는 이것저것 공부할 시간 없다. 필요한 것만 소개한다.
EBNF 에서는 {}, [], (a|b) 표현이 있다. 각각 0번이상 반복, 생략가능, a or b 양자택일. 사칙연산 표현을 EBNF 으로 표기해보자.
EBNF
<E> ::= <T> { ('+' | '-') <T> }
<T> ::= <F> { ('*' | '/') <F> }
<F> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
이제 좌항을 함수라고 했을 때, 우항에 좌항이 표현되지 않는다. 이는 곧 프로그래밍으로 구현했을 때 직접 재귀호출이 걸리지 않는 것을 의미한다.
이제 실제 사칙연산에 대한 EBNF 를 작성해보자.
<stmt> ::= <add_expr> ';'
<add_expr> ::= <mult_expr> { ('+' | '-') <mult_expr> }
<mult_expr> ::= <sign_expr> { ('*' | '/') <sign_expr> }
<sign_expr> ::= ['-'] <factor_expr>
<factor_expr> ::= <N> | '(' <add_expr> ')'
<N> ::= number
우선순위가 높은게 뒤로 배치된다. 평가할 우선순위가 제일 높은 숫자, 괄호() 가 제일 뒤에 배치되며 맨 처음
어떻게 구현할까? 사람마다 다르지만 나는 우선순위가 높은 것 부터 먼저 작성한다. 그러면 다 만들지 않고도 테스트가 가능하다.
// begin: 파싱을 시작할 문자의 위치
// end: unused
// bi: unused
// return: 다음 파싱할 토큰의 위치, 실패시 -1
int KParser::_factor_expr(int begin, int end, BlockInfo bi) {
int i = begin;
TokenType tokenType = m_tokens[i].tokenType;
if(tokenType == TokenType::integer) {
m_totalCode.push_back(m_tokens[i].str);
i++;
} else if(tokenType == TokenType::lparen) {
int tryI = i + 1;
int t = _add_expr(tryI, end, bi);
if(t < 0) {
char buf[256];
sprintf(buf, "line[%d]: 표현식의 오류.\n", m_tokens[tryI].line);
m_errorMsgs.push_back(buf);
return -1;
}
if(m_tokens[t].tokenType != TokenType::rparen) {
char buf[256];
sprintf(buf, "line[%d]: 닫는 괄호가 빠졌습니다.\n", m_tokens[tryI].line);
m_errorMsgs.push_back(buf);
return -1;
}
i = t + 1;
}
else {
return -1;
}
return i;
}
( add_expr ) 때문에 우선순위 반대로 작성하는것이 여의치 않기 때문에 실제 구현시에는 ( add_expr ) 부분은 생략하고 나중에 완성시킨다. factor_expr 구현은 단순하다. terminal 문자가 바로 있기 때문에 최종적으로 평가할 스택에 넣기만 하면 된다.
<mult_expr> ::= <sign_expr> { ('*' | '/') <sign_expr> }
<sign_expr> ::= ['-'] <factor_expr>
구현을 살펴보자.
int KParser::_mul_expr(int begin, int end, BlockInfo bi) {
int i = begin;
std::string leftValue = m_tokens[i].str;
int t = _sign_expr(i, end, bi);
if (t < 0) {
return -1;
}
i = t;
while (1) {
int tryI = i;
auto tokenValue = m_tokens[tryI].tokenType;
t = _mul_op(tryI, end, bi);
if(t < 0) {
break;
}
tryI++;
std::string rightValue = m_tokens[tryI].str;
t = _sign_expr(tryI, end, bi);
if (t < 0) {
break;
}
if(tokenValue == TokenType::mult) {
m_totalCode.push_back("mult");
} else if(tokenValue == TokenType::devide) {
m_totalCode.push_back("div");
}
i = t;
}
return i;
}
int KParser::_sign_expr(int begin, int end, BlockInfo bi) {
int i = begin;
bool isMinus = false;
if(m_tokens[i].tokenType == TokenType::minus) {
isMinus = true;
i++;
}
int t = _factor_expr(i, end, bi);
if(t < 0) {
return -1;
}
if (isMinus) {
m_totalCode.push_back("sign");
}
return t;
}
EBNF 명세 그대로 구현한 모습을 알 수 있다. 말 그대로 - 문자는 옵션으로 처리하고, 부호 단일 명령이기 때문에 바로 명령스택에 sign 을 넣는다. 다음으로 mult_expr 를 보면 명세대로 구현하되 sign_expr 부분은 말 그대로 다른 함수 호출로 퉁치는 모습이다. 그러니까 현재 작성하는 문법에 집중하면 되고 다른 non-terminal 이 등장하면 그냥 함수 호출로 대체시키면 된다. 그런 다음 *, / 가 들어온 경우에 실행스택에 mult, div 문자열을 넣는다.
이런식으로 EBNF 를 정의한 후 거꾸로 따라 올라가면서 구현하면 된다. 실행 스택에 들어간 명령어는 스택머신에 의해 수행된다.
스택머신은 숫자를 두개 혹은 한개를 입력받아 결과를 다시 스택에 넣는 기계라고 생각하면 된다. 예를 들면
# stack (왼쪽이 top):
push A # A
push B # B A
push C # C B A
sub # B-C A
mult # A*(B-C)
push D # D A*(B-C)
push E # E D A*(B-C)
add # D+E A*(B-C)
add # A*(B-C)+(D+E)
스택머신에서 push 명령어는 top 에 값을 채우는 것이고 연산자를 만나면 두개를 연산해서 스택에 다시 넣는다.
(200 + 12) * 34 + 56 - 100 는
200
12
add
34
mult
56
add
100
sub
처럼 스택이 만들어지고 스택 기반의 간단한 머신을 만들고 값을 출력하면 된다. 구현은 매우 간단하다.
for(auto i: m_totalCode) {
// tt++;
// printf("eip[%3d]: %s\n", tt, i.c_str());
if (i == "add") {
int a, b;
a = calc[calc.size() - 1];
calc.pop_back();
b = calc[calc.size() - 1];
calc.pop_back();
calc.push_back(a + b);
} else if (i == "mult") {
int a, b;
a = calc[calc.size() - 1];
calc.pop_back();
b = calc[calc.size() - 1];
calc.pop_back();
calc.push_back(a * b);
} else if (i == "div") {
int a, b;
a = calc[calc.size() - 1];
calc.pop_back();
b = calc[calc.size() - 1];
calc.pop_back();
calc.push_back(b / a);
} else if (i == "sub") {
int a, b;
a = calc[calc.size() - 1];
calc.pop_back();
b = calc[calc.size() - 1];
calc.pop_back();
calc.push_back(b - a);
} else if (i == ";") {
printf("result %d\n", calc[0]);
calc.clear();
} else if (i == "sign") {
int a;
a = calc[calc.size() - 1];
calc.pop_back();
calc.push_back(-a);
} else {
calc.push_back(std::stoi(i));
}
}
전체 완성된 소스는 git clone https://github.com/hsnks100/dreampiler.git 의 tutorial2
이제 실제 프로그래밍 언어를 만들기 위한 기초적인 체력이 되었다. 간단한 계산기지만 괄호 및 부호를 고려한 계산기를 만드는것은 매우 중요한 과정이니 실제로 코딩해봐야한다.
다음장부터는 실제 실제 프로그래밍언어를 만들기 위해 어떤게 필요한지 알아보겠다.