6 minute read

구문분석이란

이전 장에서 토큰화가 무엇인지 알아봤다. 토큰화과정만으로는 우리가 할 수 있는 것이 거의 없다.

위키 인용

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

image

  • 하향식 구문 분석(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

이제 실제 프로그래밍 언어를 만들기 위한 기초적인 체력이 되었다. 간단한 계산기지만 괄호 및 부호를 고려한 계산기를 만드는것은 매우 중요한 과정이니 실제로 코딩해봐야한다.

다음장부터는 실제 실제 프로그래밍언어를 만들기 위해 어떤게 필요한지 알아보겠다.

Updated: