충남대학교 컴퓨터공학과 조은선 교수님의 "컴파일러 개론" 강의를 필기한 내용입니다.
다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.
yacc 의 구조
- yacc은 일단 Bottom-up방식의 구문분석기를 생성해주는 프로그램이라는 것을 알고 있을 것
- 그리고 LALR(1) 이라는 파싱 기법을 사용한다는 것 - LR(1)의 성능과 LR(0)의 가벼움을 적절히 취하는 파싱 기법
- yacc은 .y 확장자의 파일을 받아들인다
- 그리고 이놈으로 구문분석기를 생성하면 y.tab.c이라는 구문분석기가 탄생한다
- 그리고 여기에는 yyparse() 라는 함수가 있고 이놈이 중심적인 역할을 하게 된다
- .y파일은 lex와 비슷하게 위와 같은 구조로 되어있다
- 선언부는 lex마냥 # include나 여러 변수들의 선언이 들어가게 되고
- 그 중간에는 Rule(생성규칙) 들이 들어가게 되며
- 마지막에도 lex처럼 함수들이 들어가게 된다
- 생성규칙을 선언할때는 → 대신 :를 사용하게 되고
- 하나의 생성규칙이 끝날때 세미콜론으로 마감을 하게 된다 - OR로 연결할때는 당연히 생성규칙이 안끝난거니까 안씀
LR Conflict
Ambiguouty
- yacc은 모호한 문법에 대해서는 구문분석기 실행시에 에러를 낸다
- 즉, Reduce를 해야 할 지 Shift를 해야 할 지 알 수 없을 경우에 에러가 나게 된다는 것
- 구문분석기가 에러가 났을 때에는 구문분석기를 뜯어서 확인해야되지만 모호성의 경우에는 문법에 오류가 있을 확률이 아주 높으므로 문법을 고쳐야된다
- 이러한 경우에는 생성규칙간의 우선순위를 지정해서 해결이 가능하다
- reduce할 생성규칙의 우선순위가 token보다 높으면 reduce하고 아니면 shift하는 것
- 또한 결합법칙의 경우에도 모호성이 발생할 수 있기 때문에 결합법칙을 명시해서 모호성을 줄여줘야 한다
- 좌측 결합법칙의 경우에는 reduce를 더 우선순위를 높게 둬서 shift하지 않고 reduce를 하도록 유도
yacc에서의 해결법
- 일단 토큰의 우선순위를 정해줄때는 위처럼 우선순위가 높은 것을 아래에 두고, %어쩌고를 통해 결합법칙을 지정해줄 수 있다
- 그 다음으로는 생성규칙의 우선순위를 정해줄때는 위와 같이 해줄 수 있다
- 보면 일단 토큰의 우선순위를 정해줄때처럼 하되 이때의 이름은 임의로 지정해준다. 그리고 해당 우선순위를 지정할 생성규칙 옆에 %prec을 적어주면 해당 우선순위가 적용된다
- 약간 우선순위에 이름을 붙이고 그 이름을 생성규칙에 할당해준다고 생각하면 됨
- 위의 예제는 if then else 모호성 해결하는 예이다
- 위같은 방식으로 if만 있는 케이스에는 낮은 우선순위를 둬서 else가 나오면 무조건 shift해서 else까지 매핑되도록 하는거임