아래 문법에 대한 파싱 테이블을 구조체 배열에 저장한 후, 현재 토큰과 상태에 따라 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;
}컴파일에 사용된 g++ 버전과 컴파일 과정
id+id+id$을 파싱하는 과정
id*(id+id)$을 파싱하는 과정