C언어의 Parser는 문법과 테이블들로 이루어진다.
아래는 LR Parsing의 문법과 테이블들이다.
Action Table
1. Si
Si는 총 세 가지 동작을 순차적으로 수행 한다.
1) token 을 stack에 push
2) state number 을 stack에 push
3) 새로운 token 읽기
2. Ri
Ri 는 문법 규칙을 사용하여 reduce 작업을 수행한다. 여기서 reduce는 ‘다시 되돌리다’ 라는 의미이다.
Ri생성 규칙을 A→α라고 한다면, (여기서 α는 right hand side의 길이 == 심볼 개수를 의미한다.)
1) 2α개 만큼 stack에서 삭제 (α개의 상태 번호+ α개의 심볼)
2) A를 stack에 push
3) goto[stack_top][A] 을 stack에 push
생성 규칙이 총 6개이기 때문에 R은 1부터 6까지 존재한다.
- 규칙 E→E+T에서 α=3 (E, +, T)이므로 스택에서 6개 요소 삭제
- 규칙 F→(E)에서 α=3 ((, E, ))이므로 스택에서 6개 요소 삭제
추가적으로 만약 수식의 값 계산이 필요하다면(value stack) R1부터 R6일 때 아래와 같은 코드로 동작한다.
switch (i) {
case 1: value[top]=value[old_top+1], value[old_top+3];
break;
case 2: value[top]=value[old_top+1];
break;
case 3: value[top]=value[old_top+1], value[old_top+3];
break;
case 4: value[top]=value[old_top+1];
break;
case 5: value[top]=value[old_top+2];
break;
case 6: value[top]=value[old_top+1];
break;
default: yyerror("parsing table error");
break;
}
3. acc
EOF 즉, 프로그램이 정상적으로 종류되었다는 의미이다.
4. error
Action Table의 공백을 의미한다.
예를 들어 0행에서는 n, ‘(’ 를 제외하고 다른 토큰이 나왔을 경우 오류라는 뜻이다.
예를 들어 (1+2)*3$ 를 계산해본다고 하면 이는 아래와 같이 동작한다.
먼저 가장 먼저 stack에 0을 푸시한다. 이는 항상 상태번호 0번부터 시작한다는 것을 의미한다.
1. stack 에 0을 push
2. 다음 토큰은 '('으로, action[0][(] 확인
이는 S4이므로
1) token인 '(' 를 stack에 push
2) state number, 4를 stack에 push
3) 새로운 토큰 읽기, 여기서 읽은 토큰은 n
3. 새로운 토큰은 n으로 action[4][n] 확인
이는 S5이므로
1) token인 n을 stack에 push
2) state number, 4를 stack에 push
3) 새로운 토큰 읽기, 여기서 읽은 토큰은 +
4. 새로운 토큰은 +로 action[5][+] 확인
이는 R6이므로 생성 규칙 6번에 따라 A는 F(F->n을 reduce하면, n->F) 이고, α는 1이다(심볼은 n으로 1개).
1) 2α (여기서는 2) 만큼 stack에서 삭제 - n, 5 두 개 삭제
2) F를 stack에 push
3) goto[4][F] (==3) 를 stack에 push
5. 여기서 새로운 토큰은 아직 +로 action[3][+] 확인
이는 R4이므로 생성 규칙 4번에 따라 A는 T(T->F를 reduce하면, F->T) 이고, α는 1이다(심볼은 F로 1개).
1) 2α (여기서는 2) 만큼 stack에서 삭제 - F, 3 두 개 삭제
2) T를 stack에 push
3) goto[4][T] (==2) 를 stack에 push
6. 아직도 새로운 토큰은 +로 action[2][+] 확인
이는 R2이므로 생성 규칙 2번에 따라 A는 T(E->T를 reduce하면, T->E) 이고, α는 1이다(심볼은 F로 1개).
1) 2α (여기서는 2) 만큼 stack에서 삭제 - T, 2 두 개 삭제
2) E를 stack에 push
3) goto[4][E] (==8) 를 stack에 push
7. 토큰은 +로 action[8][+] 확인
이는 S6이므로
1) token인 '+' 를 stack에 push
2) state number, 6을 stack에 push
3) 새로운 토큰 읽기, 여기서 읽은 토큰은 n
8. 새로운 토큰은 n으로 action[6][n] 확인
이는 S5이므로
1) token인 n을 stack에 push
2) state number, 5을 stack에 push
3) 새로운 토큰 읽기, 여기서 읽은 토큰은 ')'
9. 새로운 토큰은 ')'로 action[5][)] 확인
이는 R6이므로 생성 규칙 6번에 따라 A는 F(F->n을 reduce하면, n->F) 이고, α는 1이다(심볼은 n으로 1개).
1) 2α (여기서는 2) 만큼 stack에서 삭제 - n, 5 두 개 삭제
2) F를 stack에 push
3) goto[6][F] (==3) 를 stack에 push
10. 여기서 새로운 토큰은 아직 ')'로 action[3][)] 확인
이는 R4이므로 생성 규칙 4번에 따라 A는 T(T->F를 reduce하면, F->T) 이고, α는 1이다(심볼은 F로 1개).
1) 2α (여기서는 2) 만큼 stack에서 삭제 - F, 3 두 개 삭제
2) T를 stack에 push
3) goto[6][T] (==9) 를 stack에 push
11. 토큰은 여전히 ) 로 action[9][)] 확인
이는 R1이므로 생성 규칙 1번에 따라 A는 E(E-> E+T를 reduce하면, T->E) 이고, α는 3이다(심볼은 E, +, T로 3개).
1) 2α (여기서는 6) 만큼 stack에서 삭제 - T, 9, +, 6, E, 8 여섯 개 삭제
2) E를 stack에 push
3) goto[4][E] (==8) 를 stack에 push
12. action[8][)] 확인
13. 여기서 새로운 토큰은 '*'로 action[8][*] 확인
이는 R5이므로 생성 규칙 5번에 따라 A는 F(F->E를 reduce하면, E->F) 이고, α는 3이다(심볼은 (, E, ) 로 3개).
1) 2α (여기서는 6) 만큼 stack에서 삭제 - ), 11, E, 8, (, 4 여섯 개 삭제
2) F를 stack에 push
3) goto[0][F] (==3) 를 stack에 push
14. action[3][*] 확인
이는 R4이므로 생성 규칙 4번에 따라 A는 T(T->F를 reduce하면, F->T) 이고, α는 1이다(심볼은 T로 1개).
1) 2α (여기서는 2) 만큼 stack에서 삭제 - F, 3 두 개 삭제
2) T를 stack에 push
3) goto[0][T] (==2) 를 stack에 push
15. action[2][*] 확인
이는 S7이므로
1) token인 '*'을 stack에 push
2) state number, 7을 stack에 push
3) 새로운 토큰 읽기, 여기서 읽은 토큰은 n
16. action[7][n] 확인
이는 S5이므로
1) token인 n을 stack에 push
2) state number, 5을 stack에 push
3) 새로운 토큰 읽기, 여기서 읽은 토큰은 $
17. action[5][$] 확인
이는 R6이므로 생성 규칙 6번에 따라 A는 F(F->n을 reduce하면, n->F) 이고, α는 1이다(심볼은 n으로 1개).
1) 2α (여기서는 2) 만큼 stack에서 삭제 - n, 5 두 개 삭제
2) F를 stack에 push
3) goto[7][F] (==10) 를 stack에 push
17. action[10][$] 확인
이는 R3이므로 생성 규칙 3번에 따라 A는 T(T->F*T를 reduce하면, F->T) 이고, α는 3이다(심볼은 F, *, T로 3개).
1) 2α (여기서는 6) 만큼 stack에서 삭제 - F, 10, *, 7, T, 2 여섯 개 삭제
2) T를 stack에 push
3) goto[0][T] (==2) 를 stack에 push
18. action[2][$] 확인
이는 R2이므로 생성 규칙 2번에 따라 A는 E(E->T를 reduce하면, T->E) 이고, α는 1이다(심볼은 T로 1개).
1) 2α (여기서는 2) 만큼 stack에서 삭제 - T, 2 두 개 삭제
2) E를 stack에 push
3) goto[0][E] (==1) 를 stack에 push
19. action[1][$] 확인
이는 acc이므로 프로그램 정상적으로 종료
계산 결과는 값을 저장한 stack의 top 값인 9
'Compiler' 카테고리의 다른 글
| [compiler] c 언어의 문법 (0) | 2025.03.18 |
|---|