Compiler 4 - Shift Reduce Parser

 앞서 제작한 LL - parsing table은 stack을 이용한다. stack에 start symbol과 end marker를 push하고, input pointer를 통해 string을 읽는다. 그리고 stack과 input pointer가 가리키는 symbol을 table과 비교하여 이전 것을 pop하고, 결과를 push한다. (non-terminal일 때)
pop 한 결과가 terminal이라면 input pointer 가 가리키는 next input symbol과 비교하고, 동일하다면 input pointer를 다음으로 옮긴다.
이후 과정을 반복하며 end marker를 pop할 때 까지 반복하면 match or error 결과를 얻을 수 있다.
(가능한 production rule이 없을 때 rejected, end marker $도 non terminal이므로 production 안되면 실패)

* start symbol은 항상 end marker를 follow set으로 가짐

만약 CFG가 left factored 되어 있지만 않다면 table에서 하나에 대한 여러 개의 production rule이 명시될 수 있다. 따라서 이 경우에는 여전히 non-deterministic 하고, backtracking을 해야할 수 있다.


bottom up parsing (LR parsing)
input string을 통해 parse tree를 leaf node에서 root로 construct하는 방식. rightmost derivation을 reverse order로 따라감. (reduction - terminal을 non-terminal로 다시 되돌리는 과정)
따라서 input string에서 start symbol로 reduction 과정을 통해 parse tree를 만들 수 있다면, given string은 accept 된다.

Left to right scan of input (string을 왼쪽에서 오른쪽으로 읽음) & Rightmost derivation을 사용하므로 LR parser라 한다.
일반적으로 이 방법이 top-down parsing보다 더 선호되고, 많이 사용된다. 왜냐하면 CFG의 restriction이 좀 더 적어지기 때문이다. CFG가 non-ambiguous하기만 하면, left factoring, left recursive 등의 조건이 없어도 back tracking이 발생하지 않는다. (실제로 문법에서 완벽하게 left factoring 하는 것이 어렵기 때문에 LL(1) parsing은 이상적인 상황에서만 가능하다. 그러나 이런 제약사항이 없으므로 LR paring 방법이 조금 더 복잡함)

각 reduction에 대해 어느 sub string을 reduce 해야 할 지 결정해야함.
이를 복잡하게 선택하지 않으려면 backtracking이 가능한 bottom up parsing을 생각해볼 수 있다. 주어진 terminal(Sub string, SStr)에 대해 production rule을 확인해 가능한 non-terminal로의 변환을 진행하고, 틀리면 다시 돌아가는 방식이다.

그러나 back tracking이 존재하면 매우 비효율적이므로 어느 production rule을 선택할 지 알아야 한다.

Shift-Reduce
- sentinel form : start symbol에서 주어진 grammar로 0번 이상의 derivation을 통해 해당 string을 만들어 낼 수 있을 때 이를 grammar G의 sentinel form S라 한다.

만약 rightmost derivation이면 rm sentinel form이 된다. 이 경우, 어느 것이 non-terminal이고 terminal인 지를 분류하면 어느 것이 다음으로 production될 차례인지 확인할 수 있다.
즉, rightmost derivation인 경우, 가장 오른쪽에 처음으로 나오는 non-terminal을 terminal로 바꾸게 된다. 따라서 reduction step은 이 과정을 역으로 수행하면 되는 것이다. 그래서 reduction을 left to right로 읽어 가며 진행하면 된다. (LR parsing)

ex) shift - reduce example (reduction left to right)
w(sentinel form of G) = a(left substring)  | b(right substring)
| : splitter, input string을 두 부분으로 나눔.
a : 이미 parser에 의해 examine 된 부분, non-terminal과 terminal의 sequence
b : 아직 parser에 의해 확인되지 않은 부분. (no reduction done) 따라서 terminal로만 구성됨.

주어진 string에 대해 shift 혹은 reduce의 두 가지 선택지가 있고, 각각은 splitter |를 오른쪽으로 옮기거나 left의 right end(suffix)를 reduce하는 활동이 된다. splitter가 가장 오른쪽으로 가고, suffix가 start symbol이 되면 input string을 accept 하게 된다.

다만 여러 개의 가능한 reduce production이 존재하는 경우가 여전히 존재할 수 있기 때문에 이 모호함을 해결해야 한다.
shift reduce parser를 implement 할 때는 동일하게 stack을 사용한다.

shift reduce parser는 shift step에서는 input pointer가 가리키는 terminal을 stack에 넣고 , reduce step에서는 해당 terminal을 pop하고 reduce 한 결과를 다시 push한다. 이후 stack에 start symbol이 들어있고, input pointer는 end marker를 가리키고 있다면 accept하면 된다.

Shift-reduce parsing은 right derivation을 reverse order로 trace 한다.

그러나 여전히 shift-reduce conflict가 존재한다. 매 스텝마다 shift 해야 할 지 reduce해야 할 지 선택해야 한다는 것이다.
또한 reduce-reduce conflict도 있는데, 이는 어느 reduction을 사용해야 하는지에 대한 선택이다.
나이브한 해결방법으로는 backtracking을 적용하여 먼저 둘 중 하나를 해보고 안되면 다시 돌아올 수 있다. 그러나 이러면 비효율적이므로 이를 해결하기 위해 handle & viable prefix 이라는 개념을 도입한다.

Handle
substring that matches the complete RHS of a production which used for reduction.
즉, production의 RHS 이면서 동시에 어떤 string의 reduction 과정에서 사용되는 것을 handle이라 한다. terminal/non-terminal 모두 handle이 될 수 있다.
handle은 shift-reduce parsing 과정에서 항상 left substring의 suffix이다.(왜냐하면 reduction은 left의 suffix에서 일어나고, handle은 reduction에 사용되는 것이므로 당연함)

따라서 left substring의 모든 suffix를 확인해보고 이 중에 handle이 존재한다면 이를 reduce하고, 아니면 shift 한다는 알고리즘을 통해 shift-reduce conflict를 해결할 수 있다.
(suffix 중에 production의 RHS가 있는지 확인하여 있으면 reduce하고, 아니면 shift 한다는 것. 왜냐하면 suffix에 RHS가 없으면 애초에 reduce 할 수가 없음.)

Viable prefix
left substring that can appear during shift reduce parsing of an acceptable input string.
이는 left substring이 viable prefix라면 해당 string이 accepted될 가능성이 남아있다는 것이다.
따라서 매 step마다 left substring을 보고 viable prefix인지 아닌지 확인하면 parsing 과정을 계속 진행할 지 reject할 지 결정할 수 있다.

viable prefix는 RHS of production의 concatenation of prefix 이다. 즉, incomplete part of production's RHS이다. 왜냐하면 production의 완전한 RHS는 handle이 되기 때문이다. 그리고 shift를 반복하여 어떤 prefix가 handle이 되어 reduce되면, 해당 non-terminal과 concate되어 그 앞의 prefix도 reduce될 수 있다. (reduction된 handle과 prefix를 합친 것이 완벽한 RHS가 되면(=handle) reduce될 수 있다.)

따라서 이 둘을 종합하여 handle을 reduction한 left substring이 viable prefix인 지 확인하고, 만약 맞다면 reduction 하고 계속 진행한다. 또한 handle이 없을 경우, shift 한 결과가 viable prefix인 지 확인하고 맞다면 shift 한다. 만약 두 경우 모두 viable prefix가 나오지 않는다면, 바로 reject할 수 있다.
(단, 여전히 두 경우 모두 만족하여 주어진 production rule이 여러 개 가능할 수도 있다.)

그렇다면 given left substring이 viable prefix인 지 아닌지 어떻게 알 수 있을까.

여러 개의 prefix가 있을 때 prefix1이 어떤 production rule의 viable prefix일 경우, 이를 handle로 만들수 있는 결과(prefix1의 남은 RHS)로 reduction 될 수 있는 prefix들이 prefix2의 가능한 set이 된다. (왜냐하면 prefix는 모두 concate되어 있고, 결국 handle로 reduce 되어야 parsing이 진행가능하므로)

따라서 n-1번째 prefix를 안다면 n번째 prefix를 찾을 수 있다. 이들과 가능한 handle을 조합하면 n번째에 가능한 prefix를 찾을 수 있다. 따라서 이를 통해 다음 shift or reduce의 결과가 viable prefix인지 아닌지 확인할 수 있다. (finite automata 형태로 표현가능)

 item : "." 표시로 왼쪽은 현재까지 관측한 substring, 오른쪽은 올 수 있는 것을 나타낸다. 따라서 다음에 어떤 것이 와야 해당 스트링이 handle이 될 수 있을 지를 표현한다.
이를 통해 input symbol에 따라 가능한 transition과 state을 나타내 NFA를 구성할 수 있다. (모든 state이 final state, 해당 left substring이 viable prefix인지 확인하는 것이 목적이므로)

따라서 어떤 상태에서 left substring을 DFA에 넣었을 때 어떤 state에 있다면 이는 viable prefix라는 것이고, 해당 item 중에 reduction 가능한 것이 있다면( . 이 가장 오른쪽에 있는 것) reduce 한다. 만약 reduction 가능한 item이 없지만 다음 input symbol로의 transition이 있다면, shift 한다.
만약 둘  다 불가능한 accept 불가능한 string이라면 DFA에서 어떤 state에 있지 못할 것이므로 이 두 가지 경우만 발생하게 된다. (이외에는 모두 reject)
그러나 여전히 conflict가 존재한다.

SLR parsing
LL(1)과 비슷하게 follow set을 고려하여 reduce/shift 판단을 내린다.
상기의 reduce 경우에서 해당 state에서 rule이 존재하는 동시에 다음 문자가 reduce 한 terminal의 follow set인 지 까지 확인한다. 따라서 이 두 조건이 만족되면 reduce하고, 하나라도 만족되지 않으면 shift 한다. (가능한 경로가 있을 때) 만약 conflict가 존재한다면, CFG가 ambiguous 한 것이다.

주어진 NFA에 대해 prefix를 travel 하여 다음 production을 찾고, 조건을 따져 shift/reduce를 결정할 수 있다.
이런 SLR parsing process를 효율적으로 구현하는 프로그램을 만들기 위해서는 SLR-parsing table이 필요하다. (GOTO & ACTION table)

DFA의 state에 번호를 매기고 terminal과 non-terminal을 가로 축에, state들을 세로 축에 놓아 table을 만든다. 그리고 action part에서는 state transition에서 필요한 shift/reduce를 , goto part에서는 필요한 state으로 이동하도록 명령을 채워 넣으면 된다. (DFA를 보고)
그리고 S/R 등의 명령이 없는 table의 칸은 모두 error field이다. 따라서 string이 해당 상태에 들어서면 reject 하면 된다. (no action to perform = error)

target symbol이 non-terminal이면 아직 left substring이 viable prefix인지 확인하는 중이므로 DFA를 순회하게 된다. (GOTO part) 그러나 non-terminal을 만나면 shift나 reduction 등의 action을 결정하게 된다. (ACTION part) 따라서 GOTO는 left substring의 non-terminal을, ACTION은 right substring의 첫 symbol을 보고 결정해야 한다.

매 스텝 마다 start state에서 left substring이 만들어지는지 확인하고 (DFA의 state에 있는지) 해당 상태와 next input symbol을 확인해 다음 행동을 결정하면 된다. 최종적으로 input string이 dummy start symbol S'으로 reduce되면 accept한다.

그러나 해당 과정은 매 스텝마다 left substring을 가지고 DFA를 반복적으로 travel 해야 하므로 비효율적이다. 따라서 이런 방식보다 stack을 이용하여 해당 과정을 좀 더 효율적으로 만들 수 있다.
stack에 start state 부터 번호를 push하고, Shift(n)이면 state n을 push하고, reduce(n)이면 top을 pop한다. 이 때 production의 RHS의 개수만큼 state을 pop해야 한다. (T->E+T 라면 3개 pop)

이렇게 stack을 사용하면 given left substring에 대한 DFA travel sequence를 stack이 계속 가지고 있기 때문에 left substring이 viable prefix라는 것을 알 수 있고, 매 스텝마다 이를 확인할 필요가 없다. (dummy start symbol로 결과가 reduce 되기만 하면 stack에 state가 남아있어도 상관없다)
error field에 도달했을 때 할 수 있는 action이 없으므로 error. 그 외에 어떤 행동을 할 수 있다면 아직 accept할 가능성이 있음.

syntax analyzer는 결과로 AST를 내고, semantic analyzer는 이 AST를 travel 하며 오류를 찾아낸다.

만약 ambiguous grammar를 사용하면 parsing table에서 두 개 이상의 action이 있을 수 있다. 이러면 priority rule을 설정하여 이를 해결할 수 있다.