룩어헤드란 예전에도 설명했듯이

어떤 LR 상태에서 

그 이후에 나올 수 있는 심볼을 말한다.


LR(1)과 같은 경우 핸들의 위치가 다 같더라도

룩어헤드가 다르면 서로 다른 LR 아이템이다 (강력하다!! 엄격하게 따진다)

하지만 LR(1) 을 구하면 테이블의 크기가 엄청나게 늘어나므로

공간상에 문제가 있다.


따라서 

LALR  을 대안으로 사용하는데 이는 LR(1)에서 공통적인 상태(핸들의 위치가 전부 같은 상태)

를 묶어서 LR(1) 의 룩어헤드를 합집합 하게 된다.


하지만 LALR을 구하기 위해서 LR(1)을 먼저 구해놓는것은

공간적으로나 시간적으로나 너무 안좋으므로


다른 방식을 사용한다.


1. 먼저 LR(0) 집합을 구하는데 reduce 는 제외한다.

2. reduce 가 되어야 할때 ( 핸들이 rule의 제일 마지막에 위치할 때)
그 rule의 기원(origin) 을 구한다.

3. 해당 rule의 기원을 알아냈으면 그 심볼( 기원) 의 뒤에 있는 심볼에 대해서 FIRST집합을 구한다.



개념적으로 LR(1)의 핸들의 위치가 같은 상태는 합쳐져 있으므로 해당 기원을 구한뒤에

그 뒤에 나올 수 있는 심볼을 구하는 것이나, 똑같은 셈이 된다.
Posted by 멍충한아싸

댓글을 달아 주세요