[Compiler Design] What is Top-Down Parsing

BFS 방식

하나의 Start NonTerminal Symbol에서 한번의 유도과정을 거치고 token stream과 일치할 시 종료 그렇지 않으면 유도된 과정을 worklist에 추가하고 제일 앞을 꺼냄.

예시를 보자

grammr이 아래와 같이 있을 때

E→T

E→T+E

T→int

T→(E)

worklist → E 를 먼저 넣는다.

그리고 E를 꺼내온다.

Start Symbol E는 T와 T+E로 유도가 가능하다. 이를 worklist에 넣는다.

worklist→T→T+E

그리고 T를 꺼낸다.

T는 int와 (E)로 유도가 가능하다. 이를 worklist에 넣는다.

worklist → T+E → int → (E)

T+E를 꺼낸다.

T+E는 int+E, (E)+E, T+T, T+T+E로 유도가 가능하다. 이를 worklist에 넣는다.

위와 같이 반복하다 보면 어느순간 int + T가 worklist에 넣어지게 되고 꺼내지게 되는데 이때 int+T를 유도하면 int + int가 되어 target string이 match한다.

단점으로는 시간과 memory의 사용이 크다 그리고 높은 분기점 요소를 만들어낼 수 있다.

시간을 줄일 수 있는 방법은 안될거같은건 아예 유도조차 하지 않는것이다 ㅎ

Leftmost BFS

이는 가장 왼쪽의 symbol을 expand한다는 것이다.

일반적인 BFS와 같이 위의 규칙이 있을 때 leftmost BFS는 오직 왼쪽만 다룬다.

예를 들어 위의 T+E 와 같은 규칙이 있을 떄 일반적은 BFS는

int + E, (E) + E, T+T, T+T+E 이렇게 모든 가능성을으로 유도를 하는데

leftmost BFS는 왼쪽만 유도하고 prefix가 target stream으로 유도가 될것인가를 파악한 뒤 되는건만 worklist에 삽입한다.

그럼 leftmost BFS는 T+E를 어떻게 유도할까

왼쪽만 유도하므로

int + E, (E) + E 로 유도된다. 여기서 보면 int + E 는 target stream으로의 유도 가능성이 보인다. 그럼 worklist에 넣는다. 하지만 (E) + E는 target stream int + int로 유도 가능성이 보이는가 보이지 않는다. 그렇기에 worklist에 삽입하지 않고 버린다.

즉, leftmost BFS는 왼쪽 Symbol에 대해 유도한 다음 해당 prefix가 target stream의 prefix와 유도가 될 수 있을 것인지 체킹하는 것이다.

그럼 기존 BFS의 단점인 시간과 공간의 크기, 높은 브랜치 요소를 제거할 수 있다.

하지만 leftmost BFS에도 치명적인 단점이 존재한다.

A → Aa | Ab | c 와 같은 문법이 존재할 시

leftmost BFS는 Aa에 대해 무한대의 recursive가 발생하게 된다.

Aa, Aaa , Aaaa , Aaaaa , Aaaaaa, Aaaaaaa, caaaaaa 이렇게 말이다....

이를 위해서는 left factoring이 필요하다. 즉, grammar의 모순을 고쳐주는 것이다.

Leftmost DFS

leftmost DFS는 먼저 낮은 메모리 사용양과 높은 성능(많은 grammar에서)을 보인다. 또한 구현이 쉽다. (재귀적으로 구현 가능)

E→T

E→T+E

T→int

T→(E)

위와 같은 문법이 있다고 생각하자. 이거를 leftmost DFS로 풀어보자

E → T → (E) :: (E)는 int + int로 파싱 불가능

E → T → int :: int는 int + int로 파싱 불가능 :: 더 이상 T에 대한 파싱이 불가능 하므로 T를 버림

E → T + E → int + E → int + T → int + int :: 파싱 성공

하지만 left recursive와 같은 grammar이 존재할 시 걍 ㅈ된다.

Predictive Parsing

앞서 BFS나 DFS를 보면 유도과정에서 실패시 Backtracking이 발생했던 것을 알 수 있다.

주어진 token stream을 보고 몇개를 lookahead한다음에 어떤 production을 사용하지 미리 예측하는 것이다. 이는 BackTracking이 필요하지 않는다.

lookahead 토큰의 개수를 몇개로 하느냐에 따라 구조가 복잡해질지 단순해질지 결정된다.

위의 파싱의 경우 속도는 빠르지만 파싱 가능한 grammar의 개수 제한이 생긴다.

그래서 이 예측파서는 Trade expressiveness for speed라는 말을 듣는다.

아래와 같은 grammar이 있다고 가정하자

E→T

E→T + E

T→int

T→(E)

Token Stream : int + (int + int)

그럼 시작은 Start Symbol인 E를 가져온다.

token stream에서 lookahead해보면 int + 가 있음을 알 수 있다. 그럼

E→ T+E 의 Production을 사용함을 알 수 있다. 그리고 T+E Production에서 lookahead해보니 E→T+E→int+E 로 변경됨을 알 수 있다. 이런식으로 lookahead 토큰을 기반으로 확장해 나가는 것이 Predict Parsing이다.

LL(1)

Top-Down, Predict parsing

L : Left-to-right scan of the tokens

L : Leftmost derivation

(1) : One token of lookahead

아래와 같은 grammar이 존재함을 가정해보자

E → int

E → ( E Op E )

Op → +

Op → *

token strean : (int + (int + int ))

E$ | (int + (int * int))$ :: $는 끝을 나타내는 기호이다. 여기서 lookahed해서 "(" 라는 것을 읽었을 때 Predict Table을 보면 ( E Op E ) 가 된다.

( E Op E )$ | (int + (int * int))$ 읽었으니

E Op E)$ | int + ( int * int))$가 된다. 그럼 다음

다음 token int을 읽으면 E→int에 대한 Production이 추측이 되므로

int Op E)$ | int + ( int * int))$가 된다. int을 읽었으니

Op E)$ | + (int * int))$가 된다.

다음 token은 "+"이니 table을 살펴보면 Op→+ 가 사용된다.

+E)$ | + (int * int))$

E)$ | (int * int))$가 된다.

다음 token을 읽으면 "("이니

(E Op E)) $| (int * int))$

E Op E))$ | int * int))$ 가 된다.

다음 token int를 읽으면 E→int이니

int Op E))$ | int * int))$

Op E))$ | * int))$ 가 된다. 이런식으로

*E))$ | * int))$

E))$ | int))$

int))$ | int))$

))$ | ))$

)$ | )$

$ | $ :: 이렇게 되어 syntax 체크가 끝이 나게 된다.

에러 탐지의 경우 $가 동시에 끝나는지 해당 논티미널을 유도할 때 token stream의 lookahead로 token으로 유도가 불가능할 때 에러를 탐지해낸다.

LL(1) Algorithm

1. Suppose a grammar has start symbol S and LL(1) parsing table T. We want to parse string w(오메가)

2. Initialize a stack containing S$

3. Repeat until stack is empty:

   • Let the next character of w be t.

   • if the top of the stack is a terminal r :

     • if r and t don't match, report error!
     • otherwise consume the character t and pop r from the stack.

   • Otherwise, the top of the stack is a nonterminal A:

     • if T[A,t] is undefined, report an error.
     • Replace the top of the stack with T[A, t]

     Predict Table 채우기

     First Sets

     First Sets을 형식화 할 수 있다.

     First(A) = { t | A ⇒ *tw for some w }

   • A라는 논터미널이 특정 논터미널 t로 시작하는지 알기를 원할때 우리는

A→Bw grammar이 존재할때 First(A) = First(A) 합집합 FIrst(B) 이다.

fixed-point iteration? transitive closure algorithm?

아래와 같은 grammar set이 있다고 가정하자

STMT → if EXPR then STMT | while EXPR do STMT | EXPR;

EXPR → TERM → id | zero? TERM | not EXPR | ++ id | — id

TERM → id | constant

일반적인 First Set은 아래와 같지만

위의 A→Bw일 때 First(A) = First(A) 합집합 First(B) 라고 정의내려져 있다.

• STMT ⇒ if, while, [ zero?, not, ++, —, id, constant ] 이 추가로 가능
• EXPR ⇒ zero?, not, ++, —, [ id, constant ] 이 추가로 가능
• TERM ⇒ id, constant

그럼 아래의 사진과 같이 Predict Tabe이 만들어진다.

예시를 하나 들자면 STMT → EXPR의 경우 EXPR의 First Sets을 보고 그의 First Set에 표를 넣으면 된다.

Epsilon-Production

위의 계획처럼 First Set을 구하고 Predict Table을 만들 시 한가지 문제가 발생한다. 만약 grammar이 epsilon을 포함하고 있면 어떤 행동을 취해야하는가이다.

Num → Sign Digits 일 때 Sign이 Epsilon에 도달하니 Num은 Digits의 FIrst Set을 얻을 수 있다. 그리고 Sign에는 epsilon이 First Set으로 들어간다.

A → Bt

B → epsilon 의 grammar이 있을 떄 t는 First(A)에 속한다.

First Computation with epsilon

1. 모든 Nonterminal A set, First(A) = { t | A → tw for some w }

2. A → epsilon일 때 epsilon도 First set에 포함

3. 반복한다. 더이상의 변화가 없을 때 까지

   1. A → a라는 production이 있고 a는 Nonterminal일 때 First Set에 Epsilon이 포함될 경우 First(A) = First(A) 합집합 { epsilon }

   2. A → atw { a는 Nonterminal, epsilon을 포함할 때 } First(A) = First(A) 합집합 { t }이다.

   3. A → aBw, {a는 string of Nonterminal, first set contain epsilon } 일 떄 First(A) = First(A) 합집합 (First(B) - { epsilon } ) 이다 ?왜 엡실론을 빼지

      LL(1) Tables with epsilon

      Msg → Hi End

      Hi → hello | heya | yo

      End → world! | epsilon

      First Set

      Msg :: hello, heya, yo

      Hi :: hello, heya, yo

      End :: world!, epsilon

      ::: 현재 Nonterminal은 Msg이고 input은 hello이니 표를 디져서 Msg 와 hello에 해당하는 Msg→Hi End라는 Production을 사용한다.

      Msg $ | hello $

      Hi End $ | hello $

      hello End $ | hello $

      End $ | $ :: End가 남아서 Error!

      epsilon-production이 있는 LL(1) table을 만들 때 "$"에 대한 여분의 컬럼이 필요하다.

      즉, table은 아래와 같다.

      LL(1) Table

      그럼 아까 End $ | $에서 End가 epsilon으로 치환되면서

      $ | $가 된다.

      Follow Sets

      grammar이 epsilon-productions 일 때 현재의 논터미널 다음에 어떤 값이 오는지에 대해 알 수 있다.

      Follow(A) = { t | S ⇒ *aAtw for some a, w } S는 Start Symbol이다.

      그럼 Follow Sets은 왜 필요한가 따져보자.

      아래와 같은 grammar이 있다고 가정하자

      E → TE^

      E^ → +TE^ | epsilon

      T → FT^

      T^ → *FT^ | epsilon

      F → ( E ) | x | y

각 각의 First Sets을 구해서 Table을 채워넣고 있다가 First(E^)은 +와 Epsilon이 나오게 된다. + 의 경우 E^→+TE^를 table에 채워 넣으면 되지만 Epsilon의 경우에는 해당 문자가 사라진다는 뜻이므로 해당 문자 뒤에 나타나는 Symbol을 구해주면 되는것이다. 이를 우리는 Follow Set이라고 부른다. 그래서

Follow(E^)을 구하면 { ")", $ } 이 나오게 된다. 그래서 해당 input symbol에 값을 넣어주면된다.

")"에 E^ → epsilon 이렇게 , $ : E^ → epsilon

위의 grammar에 대해 first와 follow를 구하고 표에 대입하면 아래와 같은 표가 만들어지게 된다.

Summary & Why use First and Follow

즉, LL(1) 파서는 Lookahead라는 개념으로 해당 논터미널의 prefix를 찾아본다음(First Set) 이에 맞는 production rules을 Predict Table에 넣고, 만약 해당 논터미널의 First Set이 Epsilon이라면 해당 논터미널 다음에 오는 Symbol을 찾게 된다. 이를 Follow Set이라고 부른다.

Limits of LL(1)

여전히 left recursive한 grammar의 경우 Parse Table을 만들 수 없다는 점이 있다.

First First Conflict

아래와 같은 grammar이 있다고 가정하자.

A → Ab | c

First(A) = { c } 이다 어필보면 Conflict가 발생하지 않을거 같은데 A → Ab에서

Ab는 left recursive에 해당해서 Ab, Abb, Abbb, Abbbb, cbbbb 가 되어 c에 대해 2개의 production이 생기고 만다. predict production에 대해 UNIQUELY하지 않기 때문에 이를 FIRST-FIRST CONFLICT라 부른다.

First Follow Conflict

아래와 같은 grammar이 있다고 가정하자.

S→aAb

A→b | epsilon

First(A) = { b } , Follow(A) = { b }

input 값 b에 대해 A→epsilon, A→b 2가지의 production이 생겨 conflict가 발생한다.

Follow Follow Conflict

https://stackoverflow.com/questions/53774877/can-a-follow-follow-conflict-exist-in-a-grammar

Elimination Left Recursion

일반적으로 left recursion은 right recursion으로 변환될 수 있다.

그리고 LL(1)의 grammar이 아닌것중에 아래의 grammar도 있다.

E → T

E → T + E

T → int

T → (E)

First(E) = { int , ( }

First(T) = { int, ( } 이렇게 존재한다. 이상해 보이지 않는다 왜 LL(1)의 grammar이 아닐까 생각 해보면 '(' 에 대해 Nonterminal E는 E→T인지 E→T+E인지 알 수 없기 때문에 Conflict가 발생한다. 그래서 이는 LL(1)의 grammar이 아니다.

이를 Left-Factoring을 하면

E → Tε

E → T + E

T → int

T → (E) 로만들고

E → TY

T → int

T → (E) 로 변경한다. 즉, Conflict가 발생하는 부분을 없앤다.

그리고

Y에 대한 Production을 만들어준다.

Y → +E

Y → ε 그럼 최종본은

E → TY

T → int

T → (E)

Y → +E

Y → ε 이 완성된다.

Summary

LL(1)은 Fast하다. 그리고 구현이 쉽다.

속도의 경우 O(n |G|)의 시간을 갖는다. |G|이란 grammar의 크기 n은 input string의 길이

Top-Down Parsing이 끝이났다.