목차
📁 Yacc
Yacc은 Yet Another Compiler Compiler의 약자로, LALR 파서 생성기이다.
Lex와 함께 사용되는 유용한 도구이며, Confilxt 발생 시 대처하는 손쉬운 방법을 제공한다.
Lex와 함께 AT&T Bell Lab.에서 70년대 유닉스 운영체제 용으로 개발되어, 유닉스 표준으로 채택되었지만 최근에는 GNU Flex/Bison을 더 많이 사용하고 있다.
.y 파일 형태는 lex, flex 파일과 동일하며 다음과 같다.
예를 들어 Example.y 라는 파일이 있다고 가정할 때, 내부 형태는 다음과 같다.
📁 LR Conflict
모호한 문법은 파싱 테이블에 shift-reduce 나 reduce-reduce conflict를 야기한다.
이러한 conflict는 우선순위를 부여함으로써 제어할 수 있다.
1. reduce/reduce
- 생성 규칙 간의 우선순위로 제어
2. shift/reduce
- reduce 할 생성규칙의 우선 순위가 입력 토큰 보다 높으면 reduce, 입력 토큰이 더 높으면 shift
결합법칙도 우선순위로 제어가 가능하다.
1. 좌측 결합
- reduce 가 일어나도록 생성 규칙의 우선순위를 입력 토큰 보다 높이 둔다
2. 우측결합
- shift 가 일어나도록 입력 토큰의 우선순위가 생성 규칙보다 더 높다.
📁 Yacc에서의 Conflict 해결 방법
Yacc은 위와 같은 Conflict를 선언부에서 우선순위를 지정함으로써 해결한다.
선언부를 위와 같이 작성하는데, 이때 우선순위가 높을 수록 아래에 작성한다.
또한 선언부의 Precedence 부분에는.,,
예를 들어, 사칙연산의 선언부는 다음과 같이 정의되어 있다.
나열된 순서대로 +,-가 가장 낮고, UMINUS 가 가장 높다.
'-' expression은 UMINUS로 지정 된 우선순위를 사용하라는 의미이다.
두번째 예시로, If 문법에 대한 모호성은 가장 가까운 if로 else를 엮는 방법을 이용하여 제거한다.
Yacc의 선언부는 다음과 같이 정의되어 있다.
참고로 ANTLR에서는 우선순위를 다음과 같이 정의한다.
