[컴개/CI] Bottom-Up 구문 분석, YACC

YACC

YACC는 LALR 파서 생성기로, Yet Another Compiler Compiler의 약자이다.

Lex와 함께 AT&T Bell Lab.에서 70년대 유닉스 운영체제용으로 개발하였으며

유닉스 표준으로 채택되었는데, 요즘은 GNU Flex(Lex)/Bison(YACC)을 더 많이 사용한다.

 

위와 같은 흐름으로 진행된다.

foo.y 파일이 들어오면 yacc나 bison을 통해 y.tab.c파일로 만들어지고,

y.tab.c파일은 gcc를 통해 컴파일된다.

이때 .y 파일의 형태는 아래와 같은데, 해당 구조는 lex/flex와 동일하다.

 

LR Conflict

위와 같은 생성 규칙이 있다.

스택에 $ E * E 가 있고, 입력 버퍼에 + ... $가 있을 때,

reduce를 해야 할 것인지, shift를 해야 할 것인지 결정하기 어렵다.

 

위와 같이 모호한 문법은 파싱 테이블에 shift-reduce나 reduce-reduce conflict를 야기한다.

reduce-reduce conflict: yacc가 어느 쪽 문법으로 reduce 해야 하는지 모르는 상황

shift-reduce conflict: 입력 문자를 shift 해야 할 지, reduce를 해야 할지 모르는 상황

 

이때, 우선 순위를 통해 conflict를 제어할 수 있다.

1. reduce-reduce: 생성 규칙 간의 우선 순위로 제어

2. shift-reduce: reduce 할 생성 규칙의 우선 순위가 입력 토큰보다 높으면 reduce, 아니면 shift

 

결합 법칙을 우선 순위로 해결

위와 같은 생성 규칙이 있다. 이때 입력이 '1+2+3'이다.

여기까지 스택에 입력이 들어왔다고 했을 때,

E -> E + E로 reduce를 해야 할지, +를 push를 해야 하는지 고민해야 한다.

이때, 우선 순위를 도입할 수 있다.

 

- 좌측 결합: reduce가 일어나도록

생성 규칙의 우선 순위를 입력 토큰보다 높이 둠

- 우측 결합: shift가 일어나도록

입력 토큰의 우선 순위가 생성 규칙보다 높이 둠

 

이때 우리는 덧셈을 보통 좌측 결합한다. (1+2를 먼저 계산한다는 뜻)

따라서 좌측 결합을 채택하여 우선 순위를 두면 아래와 같다.

 

YACC에서 Conflict 해결 방법

YACC에서는 .y 파일의 선언부에서 우선 순위의 역순으로 토큰을 기술하며 우선 순위를 지정해 줄 수 있다.

즉, yacc은 LALR(1)에 더불어 추가적인 기능이 구현된 파서라고 할 수 있다.

이때, 좌측결합일 때 %left, 우측결합일 때 %right를 사용하여 결합법칙을 나타낼 수 있고,

결합 법칙이 성립하지 않을 때 %nonassoc를 통해 나타내 줄 수 있다.

이때, 우선순위가 높을 수록 아래에 둔다.

왼쪽이 결합법칙, 오른쪽이 토큰이다.

 

토큰을 나열하는 것으로 우선순위를 지정하는 것은 규칙과 맞지 않기 때문에

%prec를 통해 규칙의 우선순위도 함께 기술한다.

 

아래의 예시를 통해 자세히 이해해보자.

위 사진에서 우선 순위가 가장 낮은 +, -를 가장 위에 둔 것을 볼 수 있다.

이때 가장 아래에 있는 UMINUS는 실제 token은 아니지만 규칙에 임시로 토큰을 붙이고 싶을 때 사용하는 것으로, expression의 가장 아래에서 %prec UMINUS로 표현한 것을 볼 수 있다.

이는 '-' expression은 UMINUS로 지정된 우선 순위를 사용하라는 의미이다.

 

여담으로 ANTLR에서도 우선 순위를 나타낼 수 있다.

ANTLR에서는 위와 같이 우선순위를 나타낼 수 있으며 대표적인 LL parser이다.

이때, ANTLR는 yacc와 반대로 우선순위가 높을 수록 위에 적는다.

 

다른 예시를 보자.

위의 예시는 가장 가까운 if로 else를 엮는 방법이다.

문법을 바꾸거나 위와 같이 yacc을 구성할 수 있다.

 

위의 예시는 if-then까지 쌓은 후 token else가 등장하면 무조건 shift하여

if-then-else로 읽도록 만들어주는 우선 순위이다.

 

YACC 정리

lex와 비슷한 구조이며, conflict을 없애는 쉬운 방법을 제공하므로써 생산성을 높일 수 있다.