Syntax Analyzer (Parser)

SLR parsing

input token을 어떻게 자동으로 검증할까?

1) top-down parsing

2) bottom-up parsing

 

Bottom-up parsing

input string의 parse tree를 만들 때, leaf node에서부터 시작하는 방식

=> right most derivation의 reverse 방향으로  "reduction"을 한다

 

Shift-Reduce parsing 

#1. string ω 을 구분자를 이용하여 두개의 substrings으로 나눈다 =>  ω = α | β

#2

1) shift : 구분자 | 를 오른쪽으로 옮긴다.

2) reduce : left substring의 suffix(right end substring)을 production과 매치되는 RHS로 변경한다.

 

Confilct

1) Shift-reduce confilct

=> 각 단계마다, shift를 할 수도 있고, reduce를 할 수도 있는 상황일 때 뭘 선택해야 할까?

 

2) Reduce-reduce conflict

=> reduce를 할 수 있는 production이 여러개일  때, 어떤 RHS를 선택해야 할까?

 

Solve => Handle & Viable priefix

 

Handle

handle은 production의 RHS랑 온전히 매치가 되어 reduction에 이용할 수 있는 substring이다.

id | * id  => Handle : id , Reduce by F=>id
F | * id

 

즉, handle은 항상 left substring의 suffix 이다.

 

Handle을 사용하여, 위의 shift-reduce conflict를 해결할 수 있다

=> handle이면, reduction을 하고, 그렇지 않다면 shift를 한다.

 

그렇다면, 해당 suffix가 handle 인지 아닌지, 어떻게 알 수 있을까?

=> viable prefix 이용

 

Viable prefix

viable prefix는 acceptable한 input string을 parsing 중일 때, left substring에 나타나는 모든 조합이다.

=> 즉, input string이 acceptable 하다면, left substring은 항상 viable prefix가 된다.

F * id |  => viable prefix : F * id, handle : id, Reduce by F -> id
F * id = a prefix of T -> F * T and a prefix of F -> id
F * F |

 

다시말해 viable prefix는 production의 RHS의 prefix들의 조합이다.

 

Viable prefix를 사용하여 handle인지 아닌지를 판단해보자.

 

α β | b ω 인 상황에서, α β가 viable prefix라면, 

1)  X ->  β인 production이 존재하고, αX가 viable prefix 라면

    => β 는 α β b ω 의 handle이고, reduction을 할 수 있다.

α β가 viable prefix라면 => 현재까지 상황이 옳은 인풋이고 문제 없을 때.

 X ->  β인 production이 존재하고 => left substring의 suffix가 RHS랑 매치되고

αX가 viable prefix => reduction을 하고 나서  left substring이 viable prefix (start symbol이 될 여지가 있다는 뜻)

==> 그러면 reduction을 하는 것이 맞는 방향이라는 판단을 할 수 있다. 

2) α β 의 어떤 suffix도 handle이 아니고, α β b가 viable prefix면 

   => shift를 할 수 있다.

α β 의 어떤 suffix도 handle이 아니고 => reduction을 할 수 없고,

 α β b가 viable prefix면 => shift를 진행 했을 때 left substring이 viable prefix (start symbol이 될 여지가 있다는 뜻)

3) 이것도 저것도 아니라면, reject

α β | b ω 인 상황에서, α β가 viable prefix가 아니라는 뜻

=> viable prefix는 RHS의 나올 수 있는 모든 prefix 조합이라, 옳은 인풋이라면 left substring은 viable prefix일 수밖에 없는데, 그게 아니라는 얘기는 애초에 input이 잘못됨 => 더 이어나가는 의미가 없으므로 reject

 

그렇다면 left substring이 viable prefix 인지 아닌지는 어떻게 판단할 수 있을까?

(옳은 input 이면, viable prefix라는데, parsing 도중에 그걸 어떻게 알아내냐 이말이야)

 

==> finite automata를 이용한다.

 

viable prefix의 집합은 regular language 이다.

=> 즉, viable prefix는 finite automata로 인식이 가능하다.

(여기서부터 어려움)

 

left substring은 여러 prefix들의 조합이다. prefix들의 조합 중, RHS와 매치된다면 그게 handle이 된다.

α | β 인 상황에서, α = prefix1prefix2prefix3 .... prefixn 이라고 해보자.

prefixn이 handle이 된다면, prefix1 ~ prefixk 는 handle이 되면 안되겠지 (handle이었으면 reduce 됐을테니)

즉, 특정 handle (RHS와 온전히 match 되는) 이 나오기 전까지의 각 prefix 들은, 다음 prefix가 handle이면 안됨

 

다음 에시를 보자

 

prefix1이 T+ 일 때, handle이 되려면 뭐가 나와야 할까? => E가 나와야 한다.

이 말인 즉, prefix1 의 다음 , prefix2 부터 prefixn까지의 조합이 E가 되어야 한다는 소리다.

그렇다면, prefix2부터 prefixn까지의 도중에, 어느 한 조합이라도 E가 될 수 없는 handle이 되면, T+는 영원히 방치된다.

이런식으로 따졌을 때, prefix1이 T+ 면, prefix2는 T+, F*, ( 만이 올 수 있는 것이다.

 

* prefix2에 T가 와도 E가 될 수 있지 않나요?

=> E -> T 라면 T 자체가 handle이 되어 버려서 안됨.

=> E ->  T+E의 prefix로서의 T라면, 어차피 뒤에 +가 붙어야 derive가 가능하다

(+가 오지 않는다면 그것은 handle로서의 T)

 

즉, production의 RHS의 prefix들은

1) handle이 아닌 prefix1 뒤에 나타날 수 있고,

2) prefix n-1 다음에 나와서, handle이될 수 있다.

 

예시를 보자

prefix1 = T+ 일 때

 

다음 prefix로 나올 수 있는 것 : T+, F*, (

 

 

prefix n-1 = T+ 일 때

 

 

 

다음 prefix 로 나올 수 있는 여러 prefix 들이 state로 나타난다.

 

이런 식으로 finite automata를 이용하여 viable prefix의 set을 나타낼 수 있다.

즉, prefix n 이 correct RHS 까지 prefix의 concatenation이 잘 이어지면, viable prefix라고 판단하는 것이다.

( 잘 이어진다 or not 은, finite automata가 돌아가면서 해준다. )

 

NFA recognizing viable prefixes

1) 각 production에 "item"을 만든다.

=> "."을 사용하여 production 어딘가에 둠 => 이걸 "item" 이라고 한다. (ex E -> T. + E)

2) CFG에  dummy production을 추가한다. => S' => S  (이것도 item으로 만든다)

3) NFA 구성 

=> Alphabet : CFG의 non-ter, ter의 집합

=> state : CFG의 item

=> start state : S' -> .S , 그리고 모든 state가 accepting state 이다.

4) "." 오른쪽으로 한칸씩 옮기고 item 생성

5) 만약 derive 되는게 있으면 derive 되는 것 까지 item 생성

 

ex)

=> S'에서 E를 읽으면, S' -> E.

=> S'에서 입실론을 읽으면,  E로 reduction 될 수 있는 각 RHS 

 

=> 만약 어떤 symbol을 앞에 두고 입실론을 읽었는데, 이거로 derive 되는 state가 이미 있다? => 거기로 연결 

***** 무조건 읽어서 점 옮기는거랑 입실론 읽는거 둘 다 state 만들어 줘야 함 ****************

=>  만약 점이 끝에 찍혀 있다 => 그것은 Handle이 된다.

 

이런 식으로 NFA를 만든걸 잘 만지면

 

이런 DFA를 얻을 수 있다.

 

LR(0) parsing with DFA

α | b ω 인 상황에서, DFA가 α를 읽고, state qi에서 종료 되었다면

(말이 종료지 모든 state가 다 accepting이라 하나 읽을 때마다 조건 다 따져주는거)

 

1) qi 가 X -> α 를 포함하고 있으면 Reduce

2)  qi가 다음 input symbol b로 가는 길을 포함하고 있으면 Shift

2) 이것도 저것도 아니면 reject

 

근데???????? 여기서도 conflict가 발생한다.

shift와 reduce가 둘 다 가능한 상황이 생긴다.

대체 어떻게 해야할까나...

==> 그래서 위의 reduce 조건을 살짝 변경해준다,

 

 

α | b ω 인 상황에서, DFA가 α를 읽고, state qi에서 종료 되었다면,

 

1) qi 가 X -> β ( β 는 α 의 suffix ) 를 포함하고 있고, b 가 Follow(x)에 포함되면  Reduce

2)  qi가 다음 input symbol b로 가는 길을 포함하고 있으면 Shift

2) 이것도 저것도 아니면 reject

즉, 기존 reduce 조건을 강화해서 reduce 후에 오는 prefix도 viable prefix일 때 reduce를 선택한다.

 

이건 그냥 직접 여러번 해보는게 좋을 듯. 아무튼, 

 

 

1) qi 가 X -> β ( β 는 α 의 suffix ) 를 포함하고 있고, b 가 Follow(x)에 포함되면  Reduce

2)  qi가 다음 input symbol b로 가는 길을 포함하고 있으면 Shift

2) 이것도 저것도 아니면 reject

이게 최종 조건인데, 만약 이럼에도 conflict가 나면, 그건 애초에 CFG가 잘못된 것 (ambiguous 하다거나..)
그렇지만?! CFG를 non-ambiguous 하게 만들기는 어려움. So?!
=> precedence declaration 을 하자.
==> shift를 먼저 하게 priority를 주는 방식

 

 

SLR parsing table construction 

 

1) 각 state q 와 각 non terminal에 대한 goto table을 생성

 

state 1이 E를 읽는다면 state 2로, T를 읽는다면 state 3으로 간다. 

즉, GOTO(1, E) = 2, GOTO(1, T) = 3 이런 식으로 goto table을 작성 할 수 있다. 

 

 

2) 각 state q 와 각 terminal에 대한 action table을 생성

 

(1) state qi가 X -> α. a β 를 가지고 있고, δ(q, a) = qj가 있다면, shift를 한다.

=> state 1은  T->.(E)를 가지고 있고, ( 를 읽어  state 4로 갈 수 있다.

=> state 1은 T->.id를 가지고 있고, id를 읽어 state 5로 갈 수 있다. 

=> 즉, ACTION(1, ( ) = 4, ACTION(1, id) =5  => shift & goto qj

 

(2) state qi가 X -> α. 를 가지고 있고, a(다음 input symbol)가 Follow(X)에 속해있다면 X-> α 로 reduce 한다.

=> state 5가 T->id. 를 가지고 있을 때, Follow(T) = {*, ), $} 이므로, 다음 input symbol a가 *이거나 )이거나 $ 이면, 

T -> id로 reduce, 즉 left substring과 right substring은 ...T | * ... or ...T | ) ... 이런 꼴이 될 것이다.

(reduce 되는 LHS 뒤에 다음 input symbol이 붙어도 start symbol으로 갈 수 있는지 확인하는 것)

 

Shift도 Reduce도 하지 못하는 상황에서는, table을 비워두어 reject 처리를 할 수 있게 한다. 

 

위의 DFA로 이런 parsing table을 도출 할 수 있다. 

 

하지만 이런 parsing table을 따라갈 때, 매 순간 DFA를 따라가며 매번 결정을 내리는 것은 비효율적이다.

==> Stack을 이용해서 해결한다. 

==> Top of stack == current state, 즉, check를 반복할 필요가 없어진다.

 

Shift를 하는 상황을 보자

S ==> Shift

5 ==> 가야할 state == 즉 current state로서 stack에 push 한다.

 

 

Reduce 하는 상황을 보자.

reduce 대상이 되는 production의 RHS의 symbol의 개수만큼 stack에서 pop을 시킨다.

(왜냐면 해당 RHS 조합이 될 때까지 shift 하면서 stack에 push 했을테니까)

pop한 후 top of stack(current state)와, reduce 한 LHS 의 조합을 GOTO table에서 찾고, 해당 state를 stack에 넣는다.

(left substirng의 suffix가 T가 되었으니, 이제 T를 읽고 갈 수 있는 state에서 시작해야지)

 

이런식으로 쭉 이어가다가, dummy start symbol인 S'를 만나면, accept 한다

( stack에 뭐가 남았는지는 관계 없이 처음 시작 노드를 만나면 끝)