[cpp] LR 파싱 테이블을 사용해서 직접 S/R 파서 만들기

아래 문법에 대한 파싱 테이블을 구조체 배열에 저장한 후, 현재 토큰과 상태에 따라 shift/reduce 과정을 반복하는 파서입니다. 스택은 모두 stl의 벡터를 사용해서 구현되었으며, 구현을 단순화 하기 위해서 파서 과정의 오류 처리는 모두 생략하였습니다.
문법

E -> E + T | T

T -> T * F | F

F -> (E) | id
get_tok함수가 입력받은 문자열을 스캐닝하는 함수이며, do_reduce함수가 reduce를 수행하는 함수입니다. 그리고 main 함수의 가장 큰 while문이 전체 파서 알고리즘을 표현하고 있습니다.
#include <stdio.h>  
#include <vector>  
  
using namespace std;  
  
#undef TRUE  
#undef FALSE  
  
#define TRUE        1  
#define FALSE       0  
  
#define SHIFT       1  
#define REDUCE      2  
#define GOTO        4  
#define ACCEPT      8  
  
#define ID          1  
#define SERR        -1  
  
#define TABLE\_SIZE  (sizeof(TABLE)/sizeof(PTABLE))  
#define RTABLE\_SIZE (sizeof(RTABLE)/sizeof(RDTABLE))  
  
typedef struct \_PTABLE  
{  
    int state;      // 현재 상태  
    int tok;        // 입력 토큰  
    int atype;      // 행동 타입  
    int nstate;     // 다은 상태  
    
} PTABLE, \*PPTABLE;  
  
typedef struct \_RDTABLE  
{  
      
    int     cnpop;  
    int     cnpush;  
    char    tok;  
  
} RDTABLE, \*PRDTABLE;  
  
  
// 교제에 나와있는 문법에 대한 LR 파싱 테이블  
PTABLE TABLE[] = {  
      
    {0,     ID,     SHIFT,      5},  
    {0,     '(',    SHIFT,      4},  
    {0,     'E',    GOTO,       1},  
    {0,     'T',    GOTO,       2},  
    {0,     'F',    GOTO,       3},  
      
    {1,     '+',    SHIFT,      6},  
    {1,     '$',    ACCEPT,     0},  
  
    {2,     '+',    REDUCE,     2},  
    {2,     '\*',    SHIFT,      7},  
    {2,     ')',    REDUCE,     2},  
    {2,     '$',    REDUCE,     2},  
      
    {3,     '+',    REDUCE,     4},  
    {3,     '\*',    REDUCE,     4},  
    {3,     ')',    REDUCE,     4},  
    {3,     '$',    REDUCE,     4},  
  
    {4,     ID,     SHIFT,      5},  
    {4,     '(',    SHIFT,      4},  
    {4,     'E',    GOTO,       8},  
    {4,     'T',    GOTO,       2},  
    {4,     'F',    GOTO,       3},  
  
    {5,     '+',    REDUCE,     6},  
    {5,     '\*',    REDUCE,     6},  
    {5,     ')',    REDUCE,     6},  
    {5,     '$',    REDUCE,     6},  
  
    {6,     ID,     SHIFT,      5},  
    {6,     '(',    SHIFT,      4},  
    {6,     'T',    GOTO,       9},  
    {6,     'F',    GOTO,       3},  
  
    {7,     ID,     SHIFT,      5},  
    {7,     '(',    SHIFT,      4},  
    {7,     'F',    GOTO,       10},  
  
    {8,     '+',    SHIFT,      6},  
    {8,     ')',    SHIFT,      11},  
  
    {9,     '+',    REDUCE,     1},  
    {9,     '\*',    SHIFT,      7},  
    {9,     ')',    REDUCE,     1},  
    {9,     '$',    REDUCE,     1},  
      
  
    {10,    '+',    REDUCE,     3},  
    {10,    '\*',    REDUCE,     3},  
    {10,    ')',    REDUCE,     3},  
    {10,    '$',    REDUCE,     3},  
  
  
    {11,    '+',    REDUCE,     5},  
    {11,    '\*',    REDUCE,     5},  
    {11,    ')',    REDUCE,     5},  
    {11,    '$',    REDUCE,     5},  
  
};  
  
// 리듀스시에 작업해야 할 내용을 담은 테이블  
RDTABLE RTABLE[] = {  
    {0,},  
  
    {3, 1, 'E'},  
    {1, 1, 'E'},  
    {3, 1, 'T'},  
    {1, 1, 'T'},  
    {3, 1, 'F'},  
    {1, 1, 'F'}  
};  
  
// 토큰 스캐너  
// 토큰을 저장하고 있는 문자열과, 해당 토큰을 제거할지 입력  
char get\_tok(char \*\*str, int remove)  
{  
    int tok = SERR;  
    int rstep = 0;  
      
    if(\*str == NULL)  
        return SERR;  
  
    if(\*\*str == '\0')  
        return SERR;  
  
    if(\*\*str == 'i' && \*(\*str+1) == 'd')  
    {  
        rstep = 2;  
        tok = ID;  
    }  
    else if(\*\*str == '\*' || \*\*str == '+'   
            || \*\*str == '(' || \*\*str == ')' || \*\*str == '$')  
    {  
        rstep = 1;  
        tok = \*\*str;  
    }  
  
    if(remove)  
        \*str += rstep;  
  
    return tok;  
}  
  
// 상태와 토큰에 해당하는 스택 출력  
void print\_stack(vector<int> &State, vector<char> &Token)  
{  
    char buffer[4096], tmp[80];  
    sprintf(buffer, "%d ", State.front());  
      
    for(int i=0; i<Token.size(); ++i)  
    {  
        if(Token[i] == ID)  
            sprintf(tmp, "id %d ", State[i+1]);  
        else  
            sprintf(tmp, "%c %d ", Token[i], State[i+1]);  
        strcat(buffer, tmp);  
          
    }  
  
    printf("%-40s", buffer);  
  
}  
  
// 확장 트리 출력  
void print\_rtrace(vector<int> &rtrace)  
{  
    char \*msg[] = {  
        NULL,  
        "E -> E + T \n",  
        "E -> T     \n",  
        "T -> T \* F \n",  
        "T -> F\n",  
        "F -> (E)\n",  
        "F -> id\n"  
    };  
  
    printf("\n\n확장 과정\n");  
    for(int i=rtrace.size()-1; i>=0; --i)  
        printf("%s", msg[rtrace[i]]);  
}  
  
// 리듀스 작업 수행  
void do\_reduce(vector<int> &State, vector<char> &Token, int order)  
{  
    for(int i=0; i<RTABLE[order].cnpop; ++i)  
    {  
        State.pop\_back();  
        Token.pop\_back();  
    }  
    Token.push\_back(RTABLE[order].tok);  
  
    int s = State.back();     
    char tok = Token.back();  
  
    for(int i=0; i<TABLE\_SIZE; ++i)  
    {  
        if(TABLE[i].state == s && TABLE[i].tok == tok)  
        {  
            State.push\_back(TABLE[i].nstate);  
            break;  
        }  
    }  
  
      
}  
              
int main()  
{  
    vector<int> State;  
    vector<char> Token;  
    vector<int> rtrace;  
    int curstate;  
    char buffer[4096];  
    int end = FALSE;  
    int tok;  
    char \*ptr;  
  
    State.push\_back(0);  
      
    printf("입력 ==> ");  
    gets(buffer);  
    ptr = buffer;  
  
    while((tok = get\_tok(&ptr, FALSE)) != SERR && !end)  
    {  
        curstate = State.back();  
  
        print\_stack(State, Token);  
        printf("%20s", ptr);  
  
        for(int i=0; i<TABLE\_SIZE; ++i)  
        {  
            // 테이블을 순회하면서, 현재 상태와 토큰에 맞는 행동을 결정한다.  
            if(TABLE[i].state == curstate && TABLE[i].tok == tok)  
            {  
                switch(TABLE[i].atype)  
                {  
                // accept 상태  
                case ACCEPT:  
                    printf(" (Accept)\n");  
                    end = TRUE;  
                    break;  
  
                // shift 상태  
                case SHIFT:  
                    Token.push\_back(tok);  
                    State.push\_back(TABLE[i].nstate);  
  
                    get\_tok(&ptr, TRUE);  
  
                    printf(" (Shift %d)\n", TABLE[i].nstate);  
                    break;  
  
                // reduce 상태  
                case REDUCE:  
                    do\_reduce(State, Token, TABLE[i].nstate);  
                    rtrace.push\_back(TABLE[i].nstate);  
                    printf(" (Reduce %d)\n", TABLE[i].nstate);  
                    break;  
                }  
                  
                break;  
            }  
              
        }  
    }  
  
    // 결과 출력  
    print\_rtrace(rtrace);  
  
    return 0;  
}