skyjump's blog

Left to right scanning, Right parse.
 
파싱테이블 : 스택의 top과 현재의 입력 심벌에 따라 구문 분석 행동을 결정.
LR 파서의 네가지 행동 : Shift, reduce, accept, error
shift: 현재 상태에서 입력 심벌을 본 행동이 shift S이면 입력 심벌을 스택으로 이동하고 다음 상태 S도 스택에 넣는다.
reduce: 현재 상태에서 입력 심벌을 본 행동이 reduce A->α이면 스택에서  α 2배만큼 제거하고 A를 스택에 넣는다. 그리고 A에 대한 다음 상태를 스택에 넣는다.
accept: 주어진 입력이 올바른 스트링이다.

LR 파싱 테이블 만드는 방법 : Simple LR(SLR), Canonical LR(CLR), Lookahead LR(LALR)
SLR
LR(0) 아이템과 FOLLOW 집합을 이용하여 만든다.
LR(0) 아이템은 생성 규칙의 rhs에 .이 있는 생성규칙이다.
점 심벌 다음의 심벌을 mark 심벌이라고 한다.
CLOSURE 함수는 한 상태에서 보아야 되는 모든 LR(0) 아이템을 구하는 것.
마크 심벌이 논터미널일 경우 이 논터미널 생성규칙들을 LR(0) 아이템으로 만들어서 현재 상태에 추가 한다.
GOTO 함수는 한 상태에서 다른 상태로 가기 위해 사용. 
상태 I와 GOTO함수들이 파싱테이블을 구성한다.
CLOSURE로 한 상태를 구하고 그 상태의 GOTO함수를 만든다. GOTO함수의 결과가 이전 상태들하고 일치하는 것이 없을 때 새로운 상태가 된다. 
reduce 아이템에 대하여 그 생성 규칙의 lhs의 follow 심벌을 보고 reduce행동을 한다.  <- SLR의 특징.
한 상태에서 마크 심벌과 reduce 아이템의 follow가 같을 때, shift를 해야 할지, reduce를 해야 할지 결정할 수 없다. shift-reduce충돌
한 상태에서 두개 이상의 reduce 아이템의 follow 심벌이 같다면  어느 것을 reduce해야 할지 결정할 수 없다.  reduce-reduce충돌
문법이 모호하기 때문에 이러한 충돌이 발생한다.

CLR
Lookahead : 한 상태에서 어떤 논터미널 심벌 다음에 나올 수 있는 터미널. 상태 의존적인 follow. Follow가 lookahead를 포함.
reduce 아이템에 대한 reduce행동을 lookahead 심벌에 대해서 만드는 방법이 CLR.
CLOSURE구할 때 lookahead를 구해서 첨가한다. 한 아이템의 마크 심벌 다음에 오는 심벌의 FIRST가 그 심벌의 lookahead가 된다.  
lookahead때문에 파싱 테이블이 커진다. 그래서 lookahead를 이용하지만 테이블 크기는 작게 구성하는 LALR을 많이 사용한다.

LALR
방법1
core(아이템에서 lookahead를 제외한 부분)가 같은 것들끼리 묶는다.
SLR의 상태수랑 같게 된다. shift-reduce충돌은 일어나지 않지만  reduce-reduce충돌은 일어날 수 있다. 왜냐하면 shift는 코어에 따라 결정되는 것이지 lookahead에 의해 결정되는 것이 아니기 때문.
방법2
방법1은 lookahead 때문에 상태수가 많아지고 시간이 오래걸린다.
그래서 SLR에서 follow대신에 lookahead를 계산해서 사용한다.

모호한 문법
모호한 문법은 LR 문법이 될 수 없다.
하지만 연산순위나 결합 법칙 정보를 이용해서 하나의 행동을 선택하도록 함으로써 shift-reduce 충돌이나 reduce-reduce충돌을 해결한다.