PL6. Syntax Analysis - top down parsing

Syntax analysis는 lexical analyzer (based on regular grammar),  syntax analyzer(or parser (based on CFG, BNF)) 두 부분으로 구성된다.

BNF(context free grammar)에 기반해서 특정 string이 해당 문법으로 생성될 수 있음을 검사한다.

두 부분으로 나누었을 때 장점이 세가지가 있다.

1. lexical analysis는 상대적으로 syntax analyzer보다 간결하기 때문에 따로 분리해서 단순함을 제공한다.

2. 분리하게되면 각각 최적화가 가능해서 효율성을 제공한다.

3. 어떤 lexical analyzer는 machine에 dependent하므로 분리해서 portability를 제공한다.

 

1. lexical analyzer

parser의 front-end 부분이다.

int age = 20; 이라는 character strings에서 일정한 pattern을 따라 lexeme들로 분해한다. 각 lexeme은 특정 카테고리, token에 속한다. (ex, int의 token은 TYPE)

보통 lexical analyzer는 함수 형식으로 token을 반환하는 형태로 구현된다.

1. string input에서 getChar로 한 글자씩 가져와서 검사한다.

2. 그 글자가 letter, digit, space인지 charClass를 검사하고 lexeme에 addChar로 추가한다.

3. identifier는 reserved word와 겹치면 안되므로 최종 반환 전에 lookup(lexeme)을 거친다.

4. int value는 숫자로만 구성되어야 하므로 digit만 lexeme에 addChar할 수 있다.

25는 identifier를 의미한다.

2. Parser

이제 여기서 모든 syntax error를 탐지한다. 분리한 lexeme(token)을 가지고 parse tree를 생성하는 단계이다.

parser는 모든 모호성 검사를 O(n^3) 으로 마칠 수 있다. 너무 느리기 때문에 실제로는 O(n)으로 처리할 수 있게 모호성의 일부 subset만 검사한다.

 

xAα

1. A, B, C : Nonterminal

2. a, b, c : terminal

3. W, X, Y : terminal or nonterminal

4. w, x, y, : strings of terminal

5. α, β : mixed strings

 

3. Parser - top down

parsing algorithm에는 크게 두가지 방식이 있다. top-down 방식은 leftmost, preorder(root->left->right) 순으로 Parse tree를 만든다.

S -> aAd
S -> aB
A -> b
A -> c
B -> ccd

라는 문법이 있을 때 accd가 올바른 sentence인지 top-down 방식으로 검사해보자.

선택한 RHS의 첫번째와 next token을 비교해서 ok인지 fail인지 판단하며 백트래킹을 수행한다

 

1. S -> aAd    pointer : (a)ccd : ok

 

2. A -> b , S -> abd   pointer : a(c)cd : fail, backtrack

 

3. A -> c, S -> acd    pointer : a(c)cd : ok

 

4. A -> c, S -> acd    pointer : ac(c)d : fail, backtrack

acd의 d와 accd의 c는 다르다. 더 이상 expand할 nonterminal이 존재하지 않는다.

 

5. S -> aB  : (a)ccd : ok

 

6. B -> ccd  S -> accd  pointer : a(c)cd : ok

적합으로 종료

 

top-down 방식은 초기 nonterminal에서 시작해서 점차 트리가 증식되어간다. 이를 Production이라고 한다.

backtracking 과정을 보면 중간에 틀리다는 걸 발견하면 해당 path를 포기하고 처음부터 탐색을 이어가야 한다. 구현이 쉬운 반면 비효율 적이다.

 

 

4. Left recursion problem

S -> Aa|b
A -> Ac|Sd|e

-------remove indirect recursion-----

A -> Ac | Aad | bd | e  // S를 치환해서 소거

top-down방식에서 이런 문법에서는 A에서 다시 Sd로 변환되므로 간접적인 indirect recursion이 발생한다. 전개 과정에서 무한 루프에 빠지게 되므로 이를 제거해야 한다. 하지만 여기서 여전히 A가 앞에 붙는 (direct )recursion이 발생한다. 

A → A α | β

------remove direct recursion ----

A → βA'
A' -> αA' | ε    // ε는 empty string를 의미한다. ε를 선택하면 아무것도 추가하지 않는다.

결국 저 문법은 A -> βα*를 만들지만 계속해서 Aααα....가 전개되어 검사를 할 수 없는 infinite loop를 발생시킨다.

이런걸 direct recursion이라고 하는데 이것도 제거해서 문법을 변화시켜야 한다. 이때는 left recursion을 right recursion으로 변환해서 해결한다.

아래 알고리즘을 통해 direct recursion을 해결한다.

E -> E + T | T
T -> T * F | F
F -> (E) | id

-------remove direct recursion ------

E -> TE'
E'-> +TE' | ε 
T -> FT'
T'-> *FT' | ε 
F -> (E) | id


-------remove indirect recursion -----

E → TE′
E → (T)E′|ε
T → FT′
T′ → (F)T′|ε
F → id

 

 

5. Pairwise disjointness test

left recursion 문제를 제거한 non left recursive grammar가 top down parsing이 가능한지 검사할 수 있는 테스트이다.

parser가 start token으로부터 다음에 올 올바른 RHS를 선택하지 못하는 문제를 검사한다.

각 nonterminal (예를들면 A)에 대해서 RHS들에 대해 First()를 검사한다.

A : a B
A : b A b
A : B b
B : c B
B : d

First sets for the RHS of A-rules

First(aB) = {a}

First(bAb) = {b}

First(Bb) = First(cBb) + First(db) = {c, d}

이 세 set은 disjoint하기 때문에 Pass

 

First sets for the RHS of B-rules

First(cB) = {c}

First(d) = {d}

이 두 set은 disjoint하기 때문에 Pass

 

A : a B
A : B A b
B : a B
B : b

First sets for the RHS of A-rules

First(aB) = {a}

First(BAb) = First(aBAb) + First(bAb) = {a, b}

이 세 set은 joint하기 때문에 Fail

 

First sets for the RHS of B-rules

First(aB) = {a}

First(b) = {b}

이 두 set은 disjoint하기 때문에 Pass

----> 따라서 topdown으로 parsing 불가

 

6. Left factoring

top-down parsing에서 생기는 또 다른 문제로 grammar with common prefixes가 있다.

A -> αβ1 | αβ2 | αβ3

---------- left factoring ---------

A -> αA'
A' -> β1 | β2 | β3

 

위 같은 문법이 있을 때, 앞에 공통된 symbol때문에 어떤 production을 선택해야 하는지 parser가 모르는 상황이다.

left factoring을 적용해서 문법을 수정할 수 있다.

 

S → iEtS | iEtSeS | a
E → b

---------- left factoring ---------

S -> iEtSS' | a
S' -> ε | eS
E -> b

A → aAB / aBc / aAc

---------- left factoring ---------

A -> aA'
A' -> AD | Bc
D -> B | c

S → bSSaaS / bSSaSb / bSb / a

---------- left factoring ---------

S → bSS' / a
S' -> SaA / b
A -> aS / Sb

S → a / ab / abc / abcd

---------- left factoring ---------

S → aS'
S' -> bA / ε
A -> cB / ε
B -> d / ε

S → aAd / aB
A → a / ab
B → ccd / ddc

---------- left factoring ---------

S → aS'
S' -> Ad / B
A → aA'
A' -> b /  ε
B → ccd / ddc