SLR and LR(1) Parsing - Update 진행중

 

• LR(0) Isn’t Good Enough

LR(0) is the simplest technique in the LR family.  Although that makes it the easiest to  learn, these parsers are too weak to be of practical use for anything but a very limited set  of grammars.  The examples given at the end of the LR(0) handout show how even small additions to an LR(0) grammar can introduce conflicts that make it no longer LR(0).  The  fundamental limitation of LR(0) is the zero, meaning no lookahead tokens are used.  It is  a stifling constraint to have to make decisions using only what has already been read,  without even glancing at what comes next in the input.  If we could peek at the next  token and use that as part of the decision­making, we will find that it allows for a much  larger class of grammars to be parsed.

 

요약  : LR(0) Parser는 Next input에 대한 Look Ahead token이 0이라서 못읽고 이미 읽은 token만을 가지고 shift와 reduce를 결정지어야 한다. => grammar적인 제약을 준다. 하지만 만약 Look Ahead Token이 있다면 더 많은 grammar을 허용할 수 있을 것이다. 

 

• SLR(1)

 

We will first consider SLR(1) where the S stands for simple .  SLR(1) parsers use the  same LR(0) configurating sets and have the same table structure and parser operation,   so everything you've already learned about LR(0) applies here.  The difference comes in  assigning table actions, where we are going to use one token of lookahead to help  arbitrate among the conflicts.  If we think back to the kind of conflicts we encountered in  LR(0) parsing, it was the reduce actions that cause us grief.  A state in an LR(0) parser  can have at most one reduce action and cannot have both shift and reduce instructions.   Since a reduce is indicated for any completed item, this dictates that each completed  item must be in a state by itself.  But let's revisit the assumption that if the item is  complete, the parser must choose to reduce.  Is that always appropriate?  If we peeked at the next upcoming token, it may tell us something that invalidates that reduction.  If the  sequence on top of the stack could be reduced to the non­terminal A, what tokens do we  expect to find as the next input?  What tokens would tell us that the reduction is not  appropriate?  Perhaps Follow(A) could be useful here!

 

SLR(1) Parser는 LR(0) Parser와 비슷하게 이미 읽은 Token에 대한 Table structure을 가지고 Parser operation을 가진다. 하지만 차이점으로는 table action을 배정하는것에 차이가 있다. SLR(1) Parser는 Look Ahead Token을 하나 가지고 있기 떄문에 Shift-Reduce Conflict와 Reduce-Reduce Conflict를 완벽하게는 아니지만 어느정도 해결할 수 있다. 

 

다시 돌아가서 Conflict가 발생하는 모든 원흉은 Reduce에서 발생했다. LR(0) Parser는 하나의 Action에 한가지의 행동만을 취해야 하기 떄문에 어떤 action을 취해야할지 매우 모호하다. 

그렇기에 Follow(A)는 이러한 Conflict를 해결하는데 도움을 준다. 

 

SLR(1) Parser의 기본적인 개선사항은 현재 Handle이라고 인식되는 지점에서 Reduce를 할때 next token이 축소되는 Non Terminal의 FOllow()의 Set에 포함된다면 Reduce를 하는것이다. 

 

 

 

위의 예제는 LR(0) Parser가 해결하지 못하는 grammar의 일부이다. 

 

shift-reduce conflict 발생 

 

그러나 SLR(1) Parser는 Follow(T)에 대해서 계산한다. Follow(T) = { +, ), ], $} 만약 id의 next input이 '['라면 이때 LR(0) Parser라면 Conflict를 일으킨다. 하지만 SLR(1)은 Follow를 계산하기한다. 이때 '['는 축소하려는 Non Terminal의 FOllow Set에 포함되지 않기 때문에 Reduce가 아닌 Shift를 Action으로 취해야 할것이다.  

 

 

다음은 Reduce Reduce Conflict가 발생하는 grammar의 일부이다. SLR(1)에서는 어떻게 해결하는지 확인해보겠다. 

 

이것또한 SLR(1) Parser는 해당 State에서 축소되는 Non Terminal의 Follow를 구한다. 

 

Follow(T) = { +, ), $ }

Follow(V) = { = } 

 

이때 Next Token이 만약 특정 Non Terminal의 Follow에 속한다면 그에 맞는 Non Terminal로 Reduce하면 된다. 

 

이렇게 Next Token에 의존해서 Reduction을 진행할지에 대해 구별할 수 있다. 그리고 이러한 수정된 grammar은SLR(1)이다. 

 

• SLR(1) grammar 

 

모든 LR(0) grammar은 SLR(1) grammar이지만 그 역은 성립되지 않는다.