괴짜 프로그래머의 일상사~@@ - LR 파싱 테이블을 사용해서 직접 S/R 파서 만들기

LR 파싱 테이블을 사용해서 직접 S/R 파서 만들기 :: 2007/06/13 16:30

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

문법
1. E -> E + T | T
2. T -> T * F | F
3. 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;
}

컴파일에 사용된 g++ 버전과 컴파일 과정

id+id+id$을 파싱하는 과정

id*(id+id)$을 파싱하는 과정

(0)

(0)

스폰서	글타래 관련 글 C 컴파일러의 포인터 해석 (1000) Recursive Descent 파싱~ (1000) 최근 글 Only Hope...(32) 구글 놀 공모전...(40) 압축은 어려워 ... ㅠㅜ(239) 2주간 인기 글 평화로운 전사(265) 압축은 어려워 ... ㅠㅜ(239) 예비군 데이...(163)

reduce, S/R 파서, shift, 컴파일러, 파싱

2196명이 보았고, 댓글 한개가 달렸습니다!!!
받은 트랙백이 없고, ...

Trackback Address :: http://www.jiniya.net/tt/trackback/517

< PREV | 1| ... 137|138|139|140|141|142|143|144|145| ... 564| NEXT >

LR 파싱 테이블을 사용해서 직접 S/R 파서 만들기 :: 2007/06/13 16:30

Informed

Category

Photo Log

Tags

Recent Entries

Recent Comments

Recent Trackbacks

Calendar

Archive

Link Site

« 2008/11 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30